koosaga's profile image

koosaga

July 1, 2023 00:00

2021년 발표된 Minimum Cost Flow가 Almost-Linear Time에 풀린다는 결과는 현대적인 Convex Optimization 기법들이 전통적인 알고리즘 문제를 해결하는 아주 강력한 도구를 제공함을 보여주는 상징적인 순간이라고 할 수 있다. 요즘은 기계 학습의 인기가 워낙 엄청나기 때문에 Convex Optimization은 대개 기계 학습의 관점에서 다뤄지지만, Convex Optimization은 현대 전산학 전반에 있어서 중요도가 아주 높으며, 그래프 알고리즘적인 관점에서 Convex Optimization을 다뤘을 때 얻어갈 수 있는 것이 아주 많다.

최근 관심 있는 학생들과 함께 ETH Zurich의 Advanced Graph Algorithms and Optimization 강의를 스터디하고 있는데, 이 강의의 Chapter 15인 Convexity and Second Derivatives, Gradient Descent and Acceleration 를 정리해서 소개하려고 한다.

Chapter 15는 Convex Optimization에서 다루는 주제들 중 집합의 Convexity 에 대해 직접적으로 탐구하는 내용들로 이루어진다. PS에서 다루는 LP Duality, Lagrange multipliers, Minkowski Separation Theorem 등의 내용과 직접적 연결이 있다. 알고리즘 문제 해결을 중점적으로 공부한 사람들은, PS의 내용들이 어떻게 Convex Optimization의 영역에 접목되는지, Convex Optimization에서 왜 이러한 PS적인 내용들이 필요하게 되었는지를 생각해 보면서 이 글을 읽으면 도움이 될 것이라고 생각한다.

1. Separating Hyperplane Theorem

2차원 평면에 겹치지 않는 두 원이 있을 때, 두 원을 분리하는 직선을 찾을 수 있을까? 다시 말해, 직선의 한 쪽에 첫 번째 원이, 직선의 다른 쪽에 두 번째 원이 존재하게 직선을 그을 수 있을까? 어렵지 않게, 두 원의 공통 접선을 적절히 그어서 나누면 될 것이다. 같은 원리로, 겹치지 않는 두 볼록 다각형이 있을 때 둘을 분리하는 직선 역시 찾을 수 있다. 조금 더 복잡하지만, 3차원 공간에서도 겹치지 않는 두 볼록 다면체를 분리하는 평면이 존재할 것 같다. 즉, 평면의 한 쪽에 볼록 다면체 하나가, 다른 한 쪽에 볼록 다면체 하나가 있는 것이다.

이를 $n$ 차원으로 일반화하면 다음과 같다. 두 개의 Disjoint한 ($A \cap B = \emptyset$) Convex subset $A, B \subseteq \mathbb{R}^n$ 이 주어질 때, 이 두 집합을 분리하는 Hyperplane $H$ 가 존재할까? 정답은 그렇다 이다. 위 논의를 Formal하게 정리한 후 증명해 보자.

Definition 1.1 (Hyperplane). $n$ 차원 Hyperplane (초평면) $H$ 는 $H := {x \in \mathbb{R}^n = \langle \textbf{n}, \textbf{x} \rangle = \mu$} 이다. 이 때 $H$ 는 Normal $n \in \mathbb{R}^n \setminus {\textbf{0}}$ 과 Threshold $\mu \in \mathbb{R}$ 로 정의된다.

Definition 1.2 (Separating Hyperplane). Hyperplane $H$ 가 두 집합 $A, B$ 를 separate한다는 것은 다음을 뜻한다:

• $\forall \textbf{a} \in A: \langle \textbf{n}, \textbf{a} \rangle \geq \mu$
• $\forall \textbf{b} \in B: \langle \textbf{n}, \textbf{b} \rangle \leq \mu$ 부등식에서 등호를 빼면 $H$ 는 $A, B$ 를 strictly separate 한다고 한다.

2차원 평면에 겹치지 않는 두 볼록 다각형이 있을 때, 두 볼록 다각형을 strictly separate 하는 직선이 존재한다. 일반적인 경우에도 그게 가능할까? 다음 경우가 반례가 된다:

• $A = {(x, y) : x \leq 0}$
• $B = {(x, y) : x > 0, y \geq \frac{1}{x}}$

$A, B$ 는 disjoint convex subset이지만, 유일한 separating hyperplane은 $x = 0$ 이고, 이는 $A$ 와 교차한다. 해결하는 방법은 두 가지이다. Strict를 요구하지 않거나, 아니면 추가 조건을 부여하는 것이다. 여기서는 추가 조건을 부여하여 이 문제를 해결한다.

• 어떠한 집합 $A \in \mathbb{R}^n$ 이 닫혀있다 (closed) 라는 것은, 여집합이 열려있다 (open) 이라는 것이다.
• 어떠한 집합 $A \in \mathbb{R}^n$ 이 열려있다 (open) 라는 것은, 임의의 $x\in A$ 에 대해, 어떠한 실수 $\epsilon > 0$ 이 존재하여 $x - y_2< \epsilon$ 인 모든 $y$ 가 $A$ 에 속한다는 것을 뜻한다.
• 어떠한 집합 $A \in \mathbb{R}^n$ 이 유계 (bounded) 라는 것은, $\forall s, t\in \mathbb{R}^n$ 에 대해 $s - t_2 < r$ 인 $r \in \mathbb{R}$ 이 존재한다는 것이다.

이렇게 쓰면 너무 어려운데, 그냥 Closed는 대충 집합이 그 경계선을 포함하고 (예를 들어 2차원에서는 변을 포함하고), Bounded는 크기가 무한하지 않다 - 정도로 이해해도 될 것 같다. Clarification을 위해 엄밀하게 썼다. 이제 본론으로 들어가자.

Theorem 1.3 (Separating Hyperplane Theorem). 두 Closed/Bounded disjoint convex sets $A, B \in \mathbb{R}^n$ 에 대해 strictly separating hyperplane $H$ 가 존재한다. $c \in A, d \in B$ 가 $A, B$ 간의 거리 $dist(A, B) = \min_{a \in A, b \in B}a - b_2 > 0$ 을 최소화한다면, $\textbf{n} = d - c, \mu = \frac{1}{2}(d_2^2 - c_2^2)$ 인 hyperplane이 이러한 $H$ 의 예시이다.

Remark. 위에서 봤다시피 여기서 Closed/Bounded 조건을 빼면 strictly 조건도 빠진다. 사실 두 집합 중 하나는 Bounded가 아니어도 되지만, 귀찮은 얘기는 이미 충분히 했으니 너무 열심히 알아보지는 말자.

Proof of Theorem 1.3. $A, B$ 가 Disjoint, Closed, Bounded이기 때문에 $dist(A, B) = \min_{a \in A, b \in B}a - b_2 > 0$ 을 만족한다 (증명 생략). 이제 우리는 $\forall b \in B, \langle \textbf{n}, \textbf{b} \rangle > \mu$ 임을 증명한다 ($A$ 의 경우는 반대로 똑같이 하면 됨). 다음을 관찰하자.

$\langle \textbf{n}, \textbf{d} \rangle - \mu = \langle \textbf{d} - \textbf{c}, \textbf{d} \rangle - \frac{1}{2} (\textbf{d}_2^2 - \textbf{c}_2^2)$ $= \frac{1}{2} (\textbf{d}_2^2 + \textbf{c}_2^2 - 2 \langle \textbf{d}, \textbf{c} \rangle)$ $= \frac{1}{2}\textbf{d}-\textbf{c}_2^2 > 0$

이제 귀류법을 사용한다. $\textbf{u} \in B, \langle \textbf{n}, \textbf{u} \rangle - \mu \leq 0$ 인 $\textbf{u}$ 가 존재한다고 하자. 전략은, 원래 거리를 최소화하는 $\textbf{d}$ 와 $\textbf{u}$ 를 잇는 직선을 구성한 후, 이 직선 상에서 $\textbf{c}$ 와의 거리를 최소화하는 점이 $\textbf{d}$ 가 아님을 보이는 것이다. $\textbf{b}(\lambda) = \textbf{d} + \lambda(\textbf{u} - \textbf{d})$ 라고 정의하고, $\textbf{b}(\lambda) - \textbf{c}_2^2$ 의 도함수를 취하면:

$\frac{d}{d \lambda} \textbf{b}(\lambda) - \textbf{c}_2^2 = 2\langle \textbf{d} - \lambda \textbf{d} + \lambda \textbf{u} - \textbf{c}, \textbf{u} - \textbf{d} \rangle$

$\lambda = 0 (\textbf{b}(\lambda) = \textbf{d})$ 에서 이는 $2\langle \textbf{d} - \textbf{c}, \textbf{u} - \textbf{d} \rangle$ 이다. 그런데

$\langle \textbf{n}, \textbf{u} \rangle - \mu = \langle \textbf{d} - \textbf{c}, \textbf{u} - \textbf{d} \rangle + \langle \textbf{d} - \textbf{c}, \textbf{d} \rangle - \mu$ $= \langle \textbf{d} - \textbf{c}, \textbf{u} - \textbf{d} \rangle + \textbf{d}_2^2 - \langle \textbf{c}, \textbf{d} \rangle - \frac{1}{2} (\textbf{d}_2^2 - \textbf{c}_2^2)$ $= \langle \textbf{d} - \textbf{c}, \textbf{u} - \textbf{d} \rangle + \frac{1}{2}\textbf{d}-\textbf{c}_2^2 \leq 0$

고로 $\textbf{b}(\lambda) - \textbf{c}_2^2$ 의 도함수가 $\lambda = 0$ 일 때 음수이다. 이는 $\textbf{d}$ 가 $\textbf{c}$ 와의 거리를 최소화한다는 가정에 모순이다. $\blacksquare$

2. Lagrange multiplier

Lagrange multiplier는 보통 $g(x) = c$ 라는 제약 조건 하에 $f(x)$ 를 최대화하는 문제를 뜻한다. 일단은 간단한 motivating example을 짚고 넘어간다.

모든 $\textbf{x} \in \mathbb{R}^n, p \in [1, 2]$ 에 대해 $\textbf{x}_p \le n^{\frac{1}{2} - \frac{1}{p}} \textbf{x}_2$ 가 성립한다는 걸 증명한다고 하자. 만약 $\textbf{x}_2 = 1$ 로 고정하면, 위 문제는 $\textbf{x}_p$ 의 최댓값이 $n^{\frac{1}{2} - \frac{1}{p}}$ 이하인지를 결정하는, 다시 말해 $\textbf{x}_p$ 의 최대화 문제가 된다. 즉, $\textbf{x}_2 = 1$ 은 $g(x) = c$ 꼴의 제약 조건 이고 $f(x) = \textbf{x}_p$ 이다.

충분히 작은 $\textbf{d}$ 에 대해 $\textbf{x}$ 에서 $\textbf{x} + \textbf{d}$ 로 움직인다고 하자. 만약 $\textbf{d} \cdot \nabla_x (\textbf{x}_2) = 0$ 를 만족하게 움직였다면 $\textbf{x}_2$ 는 그대로 유지될 것이고, $\textbf{x}_p$ 는 그대로일수도 있고 변할 수도 있다. 그런데 $\textbf{x}_p$ 의 극대점이면 $\textbf{x}_p$ 도 충분히 작은 $\textbf{d}$ 에 대해 그대로 유지된다. 즉

$\textbf{d} \cdot \nabla_x (\textbf{x}_2) = 0$ $\textbf{d} \cdot \nabla_x (\textbf{x}_p) = 0$

이러면 둘이 평행하니 어떠한 $\lambda \in \mathbb{R}$ 이 존재하여

$\nabla_x (\textbf{x}_p - \lambda \textbf{x}_2) = 0$

2차원으로 생각하면, $x^2 + y^2 = 1$ 이면서 $3x + y$ 를 최소화하는 점은 기울기가 $-3$ 인 직선의 접점이다. 와 같은 식으로 생각할 수 있다. 기울기가 $-3$ 인 직선은, $3x + y$ 함수의 Gradient vector과 수직하다.

$x^2 + y^2 = 1$ 대신 볼록 다각형을 상상하면, LP Duality와 유사하다고 볼 수도 있다. 실제로도 그렇고, 앞으로 관련된 이야기를 할 것이다. Alien’s Trick과 관련이 있는지는 잘 모르겠다. 접선이 있다는 사실이 어려운 게 아니라 $\lambda$ 를 조정해서 $g(x)$ 를 맞춘다는게 어려워 보이기 때문이다. 이 글 을 읽고 직접 판단해 보면 좋을 것 같다.

3. KKT Condition

Convex duality에 대해서 아주 formal하게 논의하기 위해서는 최댓값이 없거나 (inf, sup..) 해가 없는 경우들도 다뤄야 한다. 일단 여기서는 위와 같은 상황은 다루지 않는다.

일반적인 Convex Optimization 문제는 다음과 같이 서술된다:

• $\min_{y \in S} \mathcal{E}(y)$, subject to
• $Ay = b$
• $c(y) \leq 0$

여기서

• $\mathcal{E}(y) : S \rightarrow \mathbb{R}$ 은 convex subset $S \subseteq \mathbb{R}^n$ 에 대해 정의된다.
• $A \in \mathbb{R}^{m \times n}$ 은 행렬이다.
• $c(y)$ 는 제약 조건 $c_1, c_2, \ldots$ 들의 벡터이며, $c_i : S \rightarrow \mathbb{R}$ 은 convex하다. 달리 말해 ${y : c_i(y) \leq 0}$ 가 convex set이다.

용어 정의:

• $c_i(y) = 0$ 이면 $c_i$ 는 $y$ 에 대해 tight 하다.
• $y \in S$ 가 $Ay = b, c(y) \leq 0$ 을 만족하면 $y$ 를 primal feasible 하다고 한다.

이제 Karush-Kuhn-Tucker (KKT) Condition에 대한 설명을 할 준비가 되었다.

어떠한 Convex program의 최적해가 $y^{\ast}$ 라고 하고, $y^{\ast}$ 가 $S$ 의 경계선에 있지 않다고 하자. 만약에 어떤 충분히 작은 벡터 $\delta$ 에 대해 $\delta \cdot \nabla \mathcal{E}(y^{\ast}) < 0$ 을 만족한다면 이 방향으로 살짝 움직여서 더 좋은 해를 얻을 수 있기 때문에, 이러한 경우는 항상 불가능해야 한다. $y^{\ast}$ 가 경계선에 있지 않다고 했으니, 이것이 불가능한 경우의 수는 정확히 두 가지인데

• 어떠한 row $j$ 에 대해 $a_j \cdot \delta \neq 0$
• 어떠한 tight 한 $c_i$ 에 대해 $\nabla c_i(y^{\ast}) \cdot \delta > 0$, 즉 $\nabla c_i(y^{\ast}) \cdot \delta \neq 0$

이 중 하나가 $\delta \cdot \nabla \mathcal{E}(y^{\ast}) < 0$ 을 만족하는 모든 방향 $\delta$ 에 대해 성립하는 것이다. 약간, $\delta \cdot \nabla \mathcal{E}(y^{\ast}) < 0$ 인 Halfplane 방향으로 움직이다가, Polytope의 끝에 도달했다는 느낌으로 생각하면 된다.

다음과 같은 Lemma가 있다.

Lemma 3.1. 벡터 $a_1, a_2, \ldots, a_n, v\in \mathbb{R}^n$ 이 주어진다. $w \cdot v \neq 0$ 인 모든 $w \in \mathbb{R}^n$ 에 대해, $w \cdot a_i \neq 0$ 인 $i$ 가 존재한다면, $v \in span(a_1, \ldots, a_n)$ 이다. Proof. $a_1, \ldots, a_n$ 이 선형 독립이라고 가정하자. 이것이 일반성을 잃지 않는 이유는, span은 당연히 변하지 않고, $w \cdot (a^{old}_i = \sum c_j a_j) \neq 0$ 인 $i$ 가 존재한다는 것은 $w \cdot a_i \neq 0$ 인 $i$ 가 존재한다는 것과 동일하기 때문이다. 귀류법을 사용하자. $v \notin span(a_1, \ldots, a_n)$ 이면, $v = \sum c_i a_i + k$ 로 표현할 수 있고, 이 때 $\forall_i (k \cdot a_i) = 0$ 이다. $v \cdot k = (\sum c_i a_i + k) k = k \cdot k + \sum c_i a_i k = k \cdot k > 0$ 이다. 이제 $k \cdot v \neq 0$ 인데, $w \cdot a_i \neq 0$ 인 $i$ 는 존재하지 않는다. 가정에 모순이다. $\blacksquare$

고로 $\nabla \mathcal{E}(y^{\ast})$ 을 $A$ 의 행 벡터 $a_j$ 와 tight한 constraint $c_i$ 들의 gradient $\nabla c_i(y^{\ast})$ 의 선형 결합으로 표현할 수 있다. 또한, 이 선형 결합에서 $\nabla c_i(y^{\ast})$ 의 계수는 $0$ 이하여야 한다. 계수가 양수여도 아무 문제가 없었다는 것은, 해당 constraint 자체가 필요가 없다는 뜻이기 때문에 (not tight), 계수를 $0$ 으로 만들어 줘도 충분하다.

다시 말해, 어떠한 계수 $x \in \mathbb{R}^m, s \in \mathbb{R}^k$ 가 존재하여

• $s(i) \geq 0$ if $c_i(y^{\ast}) = 0$, $s(i) = 0$ otherwise
• $-\nabla_y \mathcal{E}(y) = \sum x(j) a_j + \sum s(i) \nabla c_i(y)$

첫 번째 조건은, $s(i) \geq 0$ 이고, $s(i)$ 혹은 $c_i(y^{\ast})$ 가 $0$ 이어야 한다는 것으로 해석할 수 있다. 다시 쓰면

• $s \geq 0$
• $s(i) \cdot c_i(y) = 0$ for all $i$

이제 다 왔다. 이름들을 붙이자.

• $s$ 를 slack variable 이라 부른다.
• $s(i) \cdot c_i(y) = 0$ for all $i$ 조건을 complementary slackness 라고 부른다.
• $(x, s)$ 가 $s \geq 0$ 일 경우 $(x, s)$ 가 dual feasible 하다고 한다.
• 여기에 $y$ 가 primal feasible 할 경우 $(y, x, s)$ 가 primal-dual feasible 하다고 한다.

Definition 3.2. 맨 위에서 정의한 것과 같은 Convex program이 주어지고, $S$ 가 open이라고 하자. $y, x, s$ 가 다음 조건을 만족하면, $(y, x, s)$ 가 Karush-Kuhn-Tucker (KKT) Condition 을 만족한다고 한다:

• $Ay = b$, $c(y) \le 0$
• $s \geq 0$
• $\nabla_y \mathcal{E}(y) + A \cdot x + \nabla c(y) \cdot s = 0$
• $s(i) c_i(y) = 0$ for all $i$

$y$ 가 최적해일 경우 Karush-Kuhn-Tucker Condition을 만족한다는 게 지금까지의 우리의 논의였지만, 사실은 반례가 있다. 예를 들어 $\min_{x \in \mathbb{R}} x$ s. t $x^2 \le 0$ 인 경우, $x$ 를 감소시키는 방향으로 갔을 때 tight constraint의 gradient가 $0$ 이지만, 사실은 $x$ 를 감소시킬 수 없다. 다행이도 논의의 근간이 깨지지는 않았고, 약간의 technical assumption을 넣으면 웬만하면 최적해가 KKT Condition을 만족한다.

Definition 3.3 (Relative Interior). Convex set $S \subseteq \mathbb{R}^n$ 이 주어질 때 이의 relative interior $relint(S) = {x \in S \text{ for all } y \in S \text{ there exists } \epsilon > 0 \text{ s.t } x - \epsilon (y - x) \in S}$ 로 정의한다. 즉, $x \in relint(S)$ 라는 것은, $x$ 에서 임의의 $y \in S$ 의 반대 방향으로 조금 움직일 수 있다는 뜻이다. Example. $S = {(x, y) \in \mathbb{R}^2 x \geq 0, y = 0}$ 이라고 할 때, $(0, 0) \notin relint(S), (1, 0) \in relint(S)$ 이다.

Definition 3.4 (Slater’s condition). 맨 위에서 정의한 것과 같은 Convex program이 주어질 때, $\tilde{y}$ 가 $A\tilde{y} = b, c(\tilde{y}) < 0$ 을 만족하면 $\tilde{y}$ 를 strictly feasible 하다고 한다. 만약 $relint(S)$ 안에 strictly feasible point $\tilde{y} \in relint(S)$ 가 존재한다면, 이 Convex program이 Slater’s condition 을 만족한다고 한다.

Proposition 3.5. $S$ 가 open set이고 Slater’s condition을 만족하는 convex program이 주어질 때, $y$ 가 최적해이고, $(y, x, s)$ 가 KKT condition을 만족하는 $(y, x, s)$ 가 존재한다.

이제 다음 장에서 Convex Duality의 개념을 소개하면서 Proposition 3.5의 증명을 완성한다.

3.1. Recap: LP Duality

Convex program은 꽤 일반화된 형태의 최적화 문제이고, 복잡한 이야기를 빠르게 했기 때문에 직관을 얻을 충분한 시간이 없었을 것이라 생각한다. LP Duality라는 익숙한 개념을 위의 논의를 사용해서 다시 유도해 보자. 어쨌든 LP도 Convex optimization의 Special case이다.

일반적인 LP 문제를 Convex optimization에 맞춰 서술한다면 다음과 같다:

• $\min_{y \in \mathbb{R}_{\geq 0}^n} (c \cdot y)$, subject to
• $c_i(y) = b_i - a_i \cdot y \leq 0$ for all $i \in [m]$

$Ay = b$ 는 일반적으로 $Ay \leq b, Ay \geq b$ 와 같이 풀어쓰는 것이 LP의 관례이다. 고로 여기서 $A$ 는 빈 행렬로 생각한다. 앞에서 그렇게 쓰지 못한 이유는 저렇게 쓰면 Slater’s condition이 깨지기 때문이다. Convex program에서는 저 경우를 예외처리처럼 빼 주어야 한다.

앞에서는 최적해를 $\delta$ 방향으로 움직이면서 $\delta \cdot \nabla \mathcal{E}(y^{\ast})$ 를 줄이다가 그것이 불가능해지는 상황에 도달한다. 여기서는 $\nabla \mathcal{E}(y^{\ast}) = c$ 가 만족된다. 그러니까 $\delta \cdot c < 0$ 방향으로 움직이다가, Polytope의 끝에 도달했다는 것이다. 앞에서 이러한 경우 tight constraint들의 선형 결합으로 나타낼 수 있다는 이야기를 했다. 그 이후의 논의를 LP에 대응시키면 다음과 같다.

어떠한 계수 $s \in \mathbb{R}^m$ 가 존재하여

• $s(i) \geq 0$ if $c_i(y^{\ast}) = b_i - a_i \cdot y^{\ast} = 0$, $s(i) = 0$ otherwise
• $c= \sum s(i)a_i$

용어들을 되돌아 보면

• $s$ 를 slack variable 이라 부른다.
• $s(i) \cdot c_i(y) = 0$ for all $i$ 조건을 complementary slackness 라고 부른다.
• $s \geq 0$ 일 경우 $s$ 가 dual feasible 하다고 한다.
• 여기에 $y$ 가 primal feasible 할 경우 $(y, s)$ 가 primal-dual feasible 하다고 한다.

$(y, s)$ 가 Karush-Kuhn-Tucker (KKT) Condition 을 만족하는건 다음을 의미한다:

• $Ay \leq b$ (Primal feasibility)
• $s \geq 0$ (Dual feasibility)
• $c - As = 0$ (Dual variable should be a correct interpolation of primal linear equations of tight constraint)
• $s(i) c_i(y) = 0$ for all $i$ (Complementary slackness)

LP Duality를 회상해 보면, 우리는 $c \geq \sum s(i) a_i$ 형태의 계수 $s(i)$ 들을 찾아서, 최적해를 끼워맞추고 Lower bound와 Upper bound를 찾았다. 즉, $s(i)$ 의 본질은 우리가 각각의 inequality에 부여할 계수임을 알 수 있다. 이후 논의가 $s$ 에 대한 어떠한 maximization 문제를 풀 것이라는 것도 예상할 수 있다. (정확히는 $(x, s)$ 일 것이다. LP 관점에서 보면 $x$ 라는 벡터의 존재도 technical한 hurdle이고, 본질은 $s$ 라는 것을 이해할 수 있다.)

4. Convex Duality

Convex Duality를 소개하기 위해 일단 Lagrangian을 소개한다.

Definition 4.1. Convex program이 주어질 때, 이의 Lagrangian을 $L(y, x, s) = \mathcal{E}(y) + x \cdot (b - Ay) + c(y) \cdot s$ 라 한다.

일단, Lagrangian을 사용하여 Primal problem 을 간단하게 표현할 수 있다. $\alpha^{\ast}$ 를 primal problem의 최적해라고 하면:

$\alpha^{\ast} = \min_y \max_{s \geq 0, x} L(y, x, s)$

왜 이렇게 쓸 수 있을까? Convex program의 초기 정의를 생각해 보면, $c(y) \leq 0, Ay = b$ 에 대해 $\mathcal{E}(y)$ 를 최소화하는 것이 우리의 문제였다. 만약 $y$ 가 $c(y) \leq 0, Ay = b$ 를 만족한다고 하면, $x = s = 0$ 인게 함수를 최대화하는 유일한 방법이다. 하지만 $b - Ay \neq 0$ 이면, $x$ 의 부호를 맞추는 식으로 Lagrangian을 무한히 크게 할 수 있고, $\nabla c(y)$ 에 $0$ 초과의 컴포넌트가 있으면 대응되는 $s(i) = \infty$ 로 두어서 Lagrangian을 무한히 크게 할 수 있다.

이 관점에서 보면 Lagrangian은 결국 $c(y) \leq 0$ 을 표현하는 방법이라고 볼 수 있다. 즉, $(x, s)$ 와 같은 Slack variable은 맨 처음에 얘기했던 $\lambda$ 와 동일한 역할을 하는 것이다.

Definition 4.2. Convex program의 dual problem 을 $\max_{s \geq 0, x} \min_y L(y, x, s) = \max_{s \geq 0, x} L(x, s)$ 로 정의한다. Dual problem의 최적해를 $\beta^{\ast}$ 라고 하자.

$L(y, x, s)$ 가 $(x, s)$ 에 대한 선형 함수이고, $L(x, s)$ 는 선형 함수들의 최솟값이기 때문에 위로 볼록 (concave) 하다. $\max L(x, s)$ 가 Concave maximization이니, $\min -L(x, s)$ 는 Convex minimization이 되고, 고로 Dual problem 역시 Convex program임을 관찰할 수 있다.

Theorem 4.3 (Weak Duality) 임의의 Convex program에 대해 $\beta^{\ast} = \max_{x, s \geq 0} \min_y L(y, x, s) \leq \min_{y} \max_{x, s \geq 0} L(y, x, s) = \alpha^{\ast}$ 이다. Proof of Theorem 4.3.

• 임의의 $y_0, x_0, s_0 \geq 0$ 에 대해서 $\min_y L(y, x_0, s_0) \leq L(y_0, x_0, s_0) \leq \max_{x, s \geq 0} L(y_0, x, s)$
• 거짓을 가정하면 $\min_y L(y, x_0, s_0) > \max_{x, s \geq 0} L(y_0, x, s)$ 인 $(y_0, x_0, s_0)$ 이 존재해야 한다. 즉시 모순. $\blacksquare$

Theorem 4.3의 증명은 아주 쉽고, Convex optimization 자체와 크게 상관이 없다. 고로 임의의 Optimization 문제에 대해 Theorem 4.3이 성립한다. $\alpha^{\ast} - \beta^{\ast} \geq 0$ 라는 항을 흔히 Duality Gap 이라고 한다. 만약 이 항이 $0$ 이면, Strong Duality 가 성립한다고 할 수 있다. LP에서는 Strong Duality가 성립한다. Convex Program에서는 어떨까?

Theorem 4.4 (Strong Duality) Slater’s condition을 만족하는 Convex program에 대해서 $\alpha^{\ast} = \beta^{\ast}$ 이다.

Separating Hyperplane Theorem에 기반한 Theorem 4.4의 증명은 AGAO 책 171 - 175페이지에서 찾아볼 수 있다. 안 그래도 글이 길어서 여기서는 증명을 따로 소개하지는 않는다.

Proposition 3.5. $S$ 가 open set이고 Slater’s condition을 만족하는 convex program이 주어질 때, $y$ 가 최적해이고, $(y, x, s)$ 가 KKT condition을 만족하는 $(y, x, s)$ 가 존재한다. Proof. Strong Duality가 성립하게 된다면, $\min_y L(y, x_0, s_0) = L(y_0, x_0, s_0) = \max_{x, s \geq 0} L(y_0, x, s)$ 가 성립하는 $(y_0, x_0, s_0)$ 이 존재한다. 여기서 $y_0$ 이 최적해임은 명확하다. 이제 KKT Condition을 확인해 보자.

• $Ay_0 = b, c(y_0) \leq 0$ ($y_0$ 은 primal feasible함 - 그렇지 않으면 세번째 항의 $\max$ 를 무한으로 보낼 수 있음)
• $s_0 \geq 0$ (정의역에 의해 자명)
• $\nabla_y \mathcal{E}(y_0) + A \cdot x_0 + \nabla c(y_0) \cdot s_0 = 0$ (첫번째 항에 따라서 $\nabla_y L(y_0, x_0, s_0) = 0$ 이 성립하고 이는 $\nabla_y L(y_0, x_0, s_0) = 0$ 과 동치)
• $s_0(i) c_i(y_0) = 0$ for all $i$ ($\mathcal{E}(y_0) = \alpha^{\ast} = L(y_0, x_0, s_0) = \mathcal{E}(y_0) + x\cdot (b - Ay_0) + s\cdot c(y_0)$, 고로 $s_0(i) > 0$ 이면 $c_i(y_0) = 0$ 이어야 함.) $\blacksquare$

마지막으로, 위와 같은 Lagrangian의 개념을 LP에 적용시키면 다음과 같은 결과를 얻을 수 있다:

• $L(y, s) = c \cdot y + (b - Ay) \cdot s = c \cdot y + b \cdot s - A \cdot y \cdot s$
• (Primal) $\min_{y \geq 0} \max_{s \geq 0} L(y, s) = \min \max (c\cdot y + (b - Ay) \cdot s)$
• (Dual) $\max_{s \geq 0} \min_{y \geq 0} L(y, s) = \max \min (c \cdot y + (b - Ay) s) = \max \min (b \cdot s + (c - As) \cdot y)$
• $s \geq 0$ 을 고정하면 $y$ 는 자명하게 정해지니, $As \leq c$ 하에서 $b \cdot s$ 를 최대화하는 문제

우리가 아는 LP Duality의 개념과 완전히 일치한다.

참고 자료

• Advanced Graph Algorithms and Optimization
• Lagrangian Duality and Convex Optimization
• Theoretical grounds of lambda optimization