[Computer-Assisted Proofs in Optimization] Operator Splitting Performance Estimation Problem - 1

글 3개에 걸쳐서 arxiv.org/pdf/1812.00146.pdf 논문을 간단하게 정리한다.

저번 글과 비슷한 제목과 비슷한 아이디어를 갖고 있으나, 그 context가 약간 다르다.

 

저번 글에서는 Gradient Descent라는 거의 모두가 아는 context가 있어서 설명이 쉬웠으나, 이번에는 약간 다르다. 

일단 Operator Splitting이 무엇인지를 알아야 context를 이해할 수 있다. 그러니 이번 글에서는 이를 빠르게 설명한다.

• Disclaimer : 사실 아래에서 $\mathbb{R}^n$으로 말하는 것은 Real Hilbert Space로 보는 것이 맞는 것으로 알고 있다. 굳이 $\mathbb{R}^n$으로 쓰는 이유는 내가 실해석도 모르고 함수해석도 모르고 여러모로 모르는 게 많기 때문. 올해 공부를 하면 어떻게 해결할 수 있지 않을까 기대중이다.
• 아래 내용의 대부분은 www.math.snu.ac.kr/~ernestryu/courses/optimization.html의 6, 7강에서 공부할 수 있다.

 

set-valued operator는 $\mathbb{R}^n$의 한 점을 $\mathbb{R}^n$의 subset으로 보내는 operator이다.

만약 set-valued operator의 값이 empty set이거나 크기가 1인 집합이라면, 이를 single-valued operator라고 한다.

 

Example (Subgradient) : $f : \mathbb{R}^n \rightarrow \mathbb{R} \cup \{\pm \infty\}$가 convex 함수이고 모든 $y \in \mathbb{R}^n$에 대하여 $$f(y) \ge f(x) + \langle g, y-x \rangle$$이 성립하면 $g$를 $f$의 subgradient at $x$라고 부르며, subgradient의 모음을 $\partial f(x)$라고 쓴다. 이는 set-valued operator.

• $0 \in \partial f(x)$라면 $x$가 $f$의 값을 최소화하며, 그 역도 성립한다. 
• $\partial (f+g)(x) \supseteq \partial f(x) + \partial g(x)$임은 자명. 단, 집합끼리의 덧셈은 Minkowski Sum.
• $\text{dom} f \cap \text{int } \text{dom} g \neq \emptyset$이면 $\partial (f+g)(x) = \partial f(x) + \partial g(x)$. 증명은 여기. 단 domain은 $f(x) < \infty$인 점들의 집합.

 

함수에 대하여 Convex, $L$-smooth, $\mu$-strongly convex 등을 정의하는 것을 operator에도 비슷하게 할 수 있다.

operator $A$가 있다. 각 $x, y \in \mathbb{R}^n$와 $u \in Ax$, $v \in Ay$에 대하여 ($A(x), A(y)$를 $Ax, Ay$라고 간단하게 표기한다)

• $\langle u-v, x-y \rangle \ge 0$이면, $A$를 monotone operator라 한다.
• $\langle u-v, x-y \rangle \ge \mu ||x-y||^2$이면, $A$를 $\mu$-strongly monotone operator라 한다.
• $\langle u-v, x-y \rangle \ge \beta||u-v||^2$이면, $A$를 $\beta$-cocoercive라 한다.
• $||u-v|| \le L||x-y||$라면 $A$를 $L$-Lipschitz라 한다. 물론, $\mu, \beta, L > 0$.
• 특히, $1$-Lipschitz인 operator를 nonexpansive operator라고 한다.

 

operator $A$에 대응되는 graph를 $\{(x, u) : u \in Ax\}$라고 정의하자.

또한, operator $A$가 다음 조건을 만족하면, $A$를 maximal monotone 하다고 정의한다.

• $A$는 monotone operator
• operator $B$가 다음 조건을 만족하면, $A = B$
• $B$는 monotone operator이며, $B$의 graph는 $A$의 graph를 포함한다.

 

operator $A$의 inverse를 $\{(u, x) : u \in Ax\}$를 graph로 갖는 operator라고 정의하자.

$A$의 resolvent operator를 $J_A = (I+A)^{-1}$로 정의한다. 물론, $I$는 identity operator이다.

또한, reflected resolvent operator를 $R_A = 2J_A - I$로 정의한다. resolvent는 뒤에서 중요한 역할을 한다.

 

 

최적화 문제와의 관련성을 본격적으로 논의해보자. 기본적으로, 다음과 같은 세팅을 거친다.

• 최적화 문제를 operator에 대한 문제로 바꾼다. 예를 들어, $f$의 최솟값을 구하는 문제는 $\partial f$의 zero를 찾는 문제가 된다.
• 이를 operator $T$의 fixed point를 찾는 문제로, 즉 $z \in Tz$인 $z$를 찾는 문제로 바꾼다. 이를 fixed point encoding이라고 부른다.
• operator $T$의 fixed point를 찾기 위해서, $z^{k+1} = Tz^k$를 반복한다. 이것이 수렴하면 성공이다.

operator $T$가 identity operator $I$와 nonexpansive operator $N$의 convex combination이라면 (단, $I$에 대응되는 비율이 nonzero) $T$를 averaged operator라고 부른다. 이 경우, $T$가 fixed point를 가진다면 $z^{k+1} = Tz^k$가 잘 수렴함을 증명할 수 있다. 증명 방식은 나중에 다루도록 하겠다.

특히, $T$가 $L$-Lipschitz고 $L<1$이라면, 수렴 속도가 기하급수적으로 빠르다는 것은 쉽게 증명할 수 있는 사실이다.

 

이제 fixed point encoding의 예시를 몇 개 보이는 것으로 이론적인 준비를 마치도록 하겠다.

 

Proximal Point Method : $A$가 maximal monotone이면 다음이 성립한다.

• $J_A$가 averaged operator : $R_A = 2J_A - I$가 nonexpansive 함을 쉽게 보일 수 있다. 특히, $J_A$는 single-valued.
• Minty Surjectivity Theorem : $J_A$의 domain은 $\mathbb{R}^n$이다. 즉, 모든 $x \in \mathbb{R}^n$에 대하여 $J_Ax$는 nonempty.

또한, $f$가 convex, closed, proper (CCP) function이라면, $\partial f$가 maximal monotone operator임을 보일 수 있다.

• Convex : $f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$ for $\theta \in [0, 1]$
• Closed : $\{(x, \alpha) \in \mathbb{R}^n \times \mathbb{R} : f(x) \le \alpha\}$ is closed
• Proper : $f(x) \neq -\infty$ always, and $f(x) < \infty$ somewhere

이제 준비를 할 수 있다. $f$가 CCP function이라고 하면, 

• $f$의 최솟값을 구하는 문제를 $\partial f$의 zero를 찾는 문제로 바꿀 수 있다.
• 이를 $J_{\alpha \partial f} = (I + \alpha \partial f)^{-1}$의 fixed point를 찾는 문제로 바꿀 수 있다. 단, $\alpha > 0$.
• 그러니 $x^{k+1} = J_{\alpha \partial f}(x^k)$를 반복하여 문제를 해결할 수 있다. 이것이 Proximal Point Method.

 

Douglas-Rachford Splitting (DRS) : 이번에는 maximal monotone operator $A, B$가 있다고 가정하고, $$ 0 \in (A+B)x$$인 $x$를 찾는 문제를 생각하자. 열심히 계산하면, 이는 결국 $$x = J_{\alpha B}z, \quad R_{\alpha A}R_{\alpha B} z = z$$인 $(x, z)$를 찾는 문제와 같음을 알 수 있다. ($\alpha > 0$) 그러니 fixed point encoding을 얻는다.

그런데 $R_{\alpha A} R_{\alpha B}$는 nonexpansive 하지만 averaged operator는 아닐 수 있다. 그러므로, 이 문제를 해소하기 위하여 $$z^{k+1} = \left( \frac{1}{2} + \frac{1}{2} R_{\alpha A} R_{\alpha B} \right) z^k$$라고 하면 이는 averaged operator를 사용하였으니 수렴이 보장되는 fixed point iteration이 된다. 이를 통해서 문제를 해결할 수 있다.

이처럼 operator 여러 개가 섞인 문제를 쪼개서 푸는 것을 operator splitting이라고 한다.

 

예고 : 목표는 Operator Splitting Method에 대해서 Performance Estimation을 하는 것이다. 예를 들어, DRS에서는 iteration을 averaged operator $$ \frac{1}{2} I + \frac{1}{2} R_{\alpha A} R_{\alpha B}$$를 이용하여 했었다. $A, B$가 단순히 maximal monotone이 아니라 추가적인 성질을 가지고 있다면, 이 operator가 $L$-Lipschitz가 ($L<1$) 될 수도 있을 것이다. 이때, 우리가 보장할 수 있는 최선의 $L$ 값은 얼마일까? 그리고 이러한 문제를 어떻게 응용할 수 있을까? 다음 글에서 알아보도록 하자.