[최적화] Strong duality and KKT conditions

이우준·2021년 11월 2일

Dual problem KKT conditions Lagrange function Strong duality optimization 최적화

Optimization

목록 보기

5/6

Recap

지금까지 우리는 convex optimization problem을 위한 여러 방법들에 대해 공부했다: (이전 포스팅에서 전부 다루지는 못했지만) LP, LS, QP, SOCP, SDP.

하지만 이 외에도 convex 문제를 다루기 위해 사용되는, 유명한 방법이 하나 더 존재한다: Cone program (CP)

그러나 CP를 본 강의에서 다루기에는 너무 복잡하고, 이해에 필요한 것에 비해 얻는 것이 적어 이러한 방법론은 더 이상 다루지 않을 것이다.

대신 본 포스팅에서는 일반적인 QP와 SOCP, SDP에 대해 어떠한 algorithm을 적용할 수 있을지 strong duality 와 KKT conditions 을 기반으로 알아보자. (강의 자료의 표현을 빌리면, 이 두 가지 개념은 algorithm의 설계에 insights를 제공한다.)

참고로, 앞으로의 main contents 를 정리하면 다음과 같다.

Algorithms for general convex optimization (이번 포스팅)
Non-convex optimization

Strong duality

Primal & dual problems

Strong duality는 primal problem과 dual problem을 기반으로 하기 때문에, 먼저 이 둘이 뭔지를 알아봐야 한다.

이에 앞서 convex optimization의 standard form을 생각해보자.

\begin{aligned} \min f(x) : \textrm{ } &f_i(x) \leq 0 \quad (i=1,\cdots,m) \\ &Ax-b = 0 \\ \end{aligned}

이때 $f(x)$ 와 $f_i(x)$ 들은 모두 convex function 이고, equality constraint에서 $A \in \mathbf{R}^{p \times d}$ 이다. 우리는 그 중 $p<d$ 인 경우에 관심이 있고, $\textrm{rank}(A) = p$ 라고 가정하자. (더 정확히, 우리는 항상 $A$ 의 $\textrm{rank}$ 가 $p$ 인 full-rank 행렬을 만들 수 있으니 그렇다고 가정할 수 있다.)

Primal problem 이란 우리가 시작하는 problem을 지칭한다. 즉, 위의 식 자체가 곧 primal problem 이다.

다음으로 dual problem 을 알기 위해서는 두 가지 function에 대해 알아야 한다: 하나는 Lagrange function 이고, 다른 하나는 dual function 이다.

지금까지의 내용을 정리하면 다음과 같다.
Primal problem:
A problem that we start with
Dual problem:
Another problem which is closely related to the primal problem

Lagrange function

Lagrange function은 $\mathcal{L}(x,\lambda,\nu)$ 와 같이 표현된다. 식은 총 세 가지 arguments로 표현되는데, 여기서 $x$ 는 interested optimization variable이고 $\lambda$ 는 size $m$ , $\nu$ 는 size $p$ 의 real-valued vector 이다: $\lambda := [\lambda_1, \cdots, \lambda_m]^{\intercal}$ , $\nu := [\nu_1, \cdots, \nu_p]^{\intercal}$

참고로 $\lambda$ 와 $\nu$ 의 size는 각각 inequality, equality constraint의 개수와 같다.

이들을 종합한 Lagrange function의 꼴은 다음과 같다.

\mathcal{L}(x,\lambda,\nu) := f(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \nu^{\intercal} (Ax - b)

이때, 각 ( $i$ 번째) constraint에 곱해져 있는 상수 $\lambda_i$ 와 $\nu_i$ 를 Lagrange multiplier 라고 한다. ( $\nu_i$ 가 안 보이게 equality constraint와 관련된 식을 왜 vector form으로 쓰는지 궁금할 수 있는데, 그냥 통상적으로 vector form으로 잘 정리되니 그렇다는 것 같다.)

Dual function

Dual function $g(\lambda, \nu)$ 는 다음과 같이 정의된다.

\begin{aligned} g(\lambda,\nu) &:= \min_{x\in \textcolor{blue}{\mathcal{X}}} \mathcal{L}(x,\lambda,\nu) \\ &= \min_{x\in \textcolor{blue}{\mathcal{X}}} f(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \nu^{\intercal} (Ax - b) \end{aligned}

여기서 주목할 점은 두 가지 이다.

$x$ 가 entire space $\mathcal{X}$ 에 속해 있다. Entire space는 곧 ( $x$ 가 존재할 수 있는) valid space 이다. 이는 정의역 (혹은 domain) 과 같고, problem에서의 optimization variable $x$ 를 생각해보면 $\mathcal{X} := \textrm{dom} f \cap \textrm{dom} f_1 \cap \cdots \cap \textrm{dom} f_m$ 으로 정의할 수 있다.
$\Rightarrow$ Primal problem에서 inequality, equality constraint들에 의해 결정되었던 feasible set 과는 다르다. Search space가 조금 더 확장됐다고 보면 된다.

일반적으로 $\mathcal{L}(x,\lambda,\nu)$ 는 $x$ 에 대한 convex가 아닐 수 있다. 만약 모든 $i$ 에 대해 $\lambda_i \geq 0$ 이면, $\mathcal{L}(x,\lambda,\nu)$ 는 단순히 convex function과 affine function의 합이므로 이때는 convex function이 맞다. 하지만 $\lambda_i$ 에 대한 조건은 없으므로, 이는 negative 일수도 있고 이 경우 $g(\lambda,\nu)$ 는 $-\infty$ 가 될 수 있다.
(e.g., $\lambda_1 = -1$ , $f_1(x) = e^x \textrm{ (convex)}$ , $\mathcal{X} \in \mathbf{R}$ . 이때, $x=+\infty \rightarrow g(\lambda,\nu) = -\infty$ )

다시 본론으로 돌아가 dual problem 을 마저 정의해보자.

Dual function은 $f(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \nu^{\intercal} (Ax - b)$ 에 대한 minimization의 solution 이다. 이때 특정 $x$ 를 고정하여 생각해보자. 그렇다면 앞서 언급한 식은 $\lambda$ 와 $\nu$ 에 대한 함수이다. 더 구체적으로 $x$ 가 고정되었으니 그에 대한 term은 상수로 볼 수 있고, 이는 $\lambda$ 와 $\nu$ 에 대한 affine function 이다.
$\Rightarrow$ Affine in $(\lambda,\nu)$

여기서 알아낼 수 있는 중요한 point가 있다. 다음의 질문을 생각해보자. 두 affine function의 minimum은 convex 일까, concave 일까? 답은 concave 이다.

즉, $\min(\mathcal{L}({x_1, \lambda, \nu}), \mathcal{L}({x_2, \lambda, \nu}))$ 은 concave 이다. (두 직선의 minimum을 생각해보면, concave 형태임을 알 수 있다.)

그런데 $g(\lambda, \nu)$ 는 두 개의 minimum이 아닌 무수히 많은 모든 $x$ 에 대한 minimum 이다. 여기서 우리는 $g(\lambda, \nu)$ 가 concave 라는 것을 알 수 있다. $\Rightarrow$ Concave in $(\lambda, \nu)$

Dual problem은 그러한 concave (오목) 함수 $g(\lambda, \nu)$ 에서 maximum을 찾는 것으로, 식은 다음과 같다.

\textrm{(Dual problem): }\textrm{ } \max_{\lambda, \nu} g(\lambda, \nu): \lambda \geq 0

주목할 점은 $\nu$ 가 아닌 $\lambda$ 에 대한 constraint 만 존재한다는 것이다. 이유는 추후에 다뤄보도록 하고, 이를 식에 반영하여 아래와 같이 표현할 수 있다.

\max_{\lambda, \nu} \min_{x \in \mathcal{X}} f(x) + \sum_{i=1}^{m} \lambda_i f_i (x) + \nu^{\intercal} (Ax-b) : \lambda \geq 0

Strong duality

Strong duality는 primal problem과 dual problem의 optimal solution 간 관계이다. 각각을 $p^*$ 와 $d^*$ 로 두자.

\begin{aligned} \textrm{(Primal): }\textrm{ } p^* &:= \min f(x): \textrm{ } f_i(x) \leq 0, \textrm{ } i=1,\cdots,m, \textrm{ } Ax-b = 0 \\ \textrm{(Dual): }\textrm{ } d^* &:= \max_{\lambda, \nu} \min_{x \in \mathcal{X}} f(x) + \sum_{i=1}^m \lambda_i f_i(x) + \nu^{\intercal} (Ax-b): \textrm{ } \lambda >= 0 \end{aligned}

Strong duality는 $p^*$ 와 $d^*$ 에 대해 다음의 관계식이 성립하는 경우이다.

\textbf{(Strong duality): }\textrm{ } p^* = d^*

당연히, 일반적으로 둘은 다르다. 하지만 흥미롭게도 mild condition 하의 convex optimization에 대해서는 strong duality가 성립하고, 우리는 이를 strong duality theorem 이라 한다.

Mild condition? It says that,
There $\exists \textrm{ } x$ such that strict inequality $f_i(x) < 0$ holds for all $i$ subject to $Ax = b$ .

그나저나 strong duality theorem이 algorithm 설계에 있어서 왜 중요한 것일까?

이는 strong duality 가 만족할 때 필요충분 조건으로 얻을 수 있는 성질이, algorithm 적 insight를 제공할 수 있기 때문이다. 이번 포스팅에서는 그 필요충분 조건이 무엇인지 까지만 다뤄볼 예정이다.

KKT conditions

이전에 equality-constrained LS problem의 closed form solution을 다루면서 KKT equation에 대해 다룬적이 있다. KKT condition은 그와 관련 있는데, 보다 자세히 설명하면 (convex로 제한되지 않은) 일반적인 optimization problem의 optimality에 대한 필요 조건이다.

그런데 KKT conditions에 대한 자세한 공식들을 다루기에 앞서, 왜 strong duality와 KKT conditions가 algorithm 적 insight를 주는지에 대해 알아보자.

Algorithmic insights

\textbf{KKT conditions} \quad \& \quad \textbf{Strong duality}

Convex optimization에 대해 다음의 세 가지 성질이 성립한다.

Strong duality holds: $p^* = d^*$

KKT conditions $\Leftrightarrow$ $p^* = d^*$ (위에서 언급한 필요충분 조건 이다.)

KKT conditions를 보장하는 natural algorithm이 존재한다.

따라서, general convex optimization에 대한 algorithm을 만들기 위해서는 KKT condition을 만족하는 것으로 충분하다.

Algorithm에 대한 자세한 내용은 다음에 보기로 하고, 이번 포스팅에서는 위의 성질들 중 두 번째에 집중해 볼 것이다.

\textrm{KKT conditions}\Leftrightarrow p^* = d^*

( $\Leftarrow$ )

증명에 앞서서 다음을 가정하자.

Strong duality 만족, $p^* = d^*$
$x^*$ 는 primal problem의 minimizer 이다. 즉, $x^*$ 로 $p^*$ 를 얻을 수 있다.
$(\lambda^*, \nu^*)$ 는 dual problem의 maximizer 이다. 똑같이, $(\lambda^*, \nu^*)$ 로 $d^*$ 를 얻을 수 있다.

즉 가정으로부터 우리는 $f(x^*) = p^* = d^* = g(\lambda^*, \nu^*)$ 임을 알 수 있으므로, 다음을 유도할 수 있다.

\begin{aligned} f(x^*) &= g(\lambda^*,\nu^*) \\ &\overset{(a)}{=} \min_{x\in \mathcal{X}} f(x) + \sum_{i=1}^{m} \lambda_i^* f_i(x) + \nu^{*\intercal} (Ax - b) \\ &\overset{(b)}{\leq} f(x^*) + \sum_{i=1}^{m} \lambda_i^* f_i(x^*) + \nu^{*\intercal} (Ax^* - b)\\ &\overset{(c)}{\leq} f(x^*) \\ \end{aligned}

여기서 $(a)$ 는 dual function과 Lagrange function의 정의, $(b)$ 는 $x^*$ 에 대한 가정으로 인해 성립한다. ( $x^*$ 는 feasible point 중에서 선택된 primal problem의 minimizer 이므로, entire space에서의 Lagrange function에 대해서는 $(b)$ 가 성립하는 것이다.)

마지막으로 $(c)$ 는 $x^*$ 가 feasible point 임을 가정했기 때문에, constraint 들을 고려하면 성립함을 알 수 있다.
$(\because \lambda^*_i \geq 0$ , $f_i(x^*) \leq 0 \textrm{ } \textrm{ } \forall i$ , $Ax^* - b = 0)$

참고로 $\lambda^*$ 도 feasible 한데, 이것이 dual problem에서 $\lambda$ 에 대한 constraint가 존재하던 이유이다.

다시 본론으로 돌아가 전체 식을 보면, 왼쪽의 첫 번째 항과 오른쪽 마지막 항은 $f(x^*)$ 로 같다. 즉, 이는 두 부등식 $(b)$ 와 $(c)$ 가 tight 하다는 것을 의미하는데, 그 중에서 $(b)$ 에 주목하면 우리는 $x^*$ 가 실제로 $x$ 에 대해 $\mathcal{L}(x, \lambda^*, \nu^*)$ 를 최소화 한다는 것을 알 수 있다.

한편 $\lambda$ 가 non-negative 하다는 전제 조건만 있다면, $\mathcal{L}$ 은 $x$ 에 대한 convex 이고, unconstrained 하므로 아래의 식이 성립한다.

\nabla_x \mathcal{L}(x^*, \lambda^*, \nu^*) = 0

이번에는 $(c)$ 에 주목해보자. 여기서는 (어차피 0 값인) equality constraint를 생각하지 않아도 되니, 모든 $i$ 에 대해 $\lambda_i^* f_i(x^*) = 0$ 임을 알 수 있다. 해당 condition에는 흥미로운 점이 있는데, 만약 $\lambda_i^* > 0$ 라면 $f_i(x^*) = 0$ 이다. 반대로 $f_i(x^*) < 0$ 이면 $\lambda_i^* = 0$ 이다.

\begin{aligned} f_i(x^*) < 0 &\Rightarrow \lambda^*_i = 0 \\ \lambda^*_i > 0 &\Rightarrow f_i(x^*) = 0 \end{aligned}

정리하면 둘 중 하나가 부등식을 strict 하게 만족하면 다른 하나는 0 값을 가질 수 밖에 없는데, 이러한 특징으로 인해 $\lambda_i^* f_i(x^*) = 0$ 를 complementary slackness 라고 부른다.

Why?
Slack은 곧 gap을 의미하는데, 이 gap은 $(c)$ 를 의미한다.
Complementary 라는 말은 앞서 말한 것처럼 $\lambda_i^*$ 와 $f_i(x^*)$ 가 서로의 조건을 상대적으로 결정해 줄 수 있다는 특징에서 나왔다.

정리해보자. 우리는 $p^* = d^*$ 라는 가정으로부터 아래의 관계식을 유도할 수 있었다.

\begin{aligned} \nabla_x \mathcal{L}(x^*, \lambda^*, \nu^*) &= 0 \\ \lambda^*_i f_i(x^*) &= 0 \quad \forall i \\ \end{aligned}

이 외에도 기존의 primal 및 dual problems에 있는 constraints를 합쳐 보면, 최종적으로 아래의 condition을 얻을 수 있는데 이게 KKT condition 이다.

KKT conditions:

\begin{aligned} \nabla_x \mathcal{L}(x^*, \lambda^*, \nu^*) &= 0 \\ \lambda^*_i f_i(x^*) &= 0 \quad \forall i \\ f_i(x^*) &\leq 0 \quad \forall i\\ Ax^*-b &= 0 \\ \lambda^* &\geq 0 \end{aligned}

따라서, KKT condition 은 strong duality를 만족하기 위한 필요 조건 이다.

( $\Rightarrow$ )

\textrm{KKT conditions } \Rightarrow p^* =f(x^*) = g(\lambda^*, \nu^*) = d^*

이번에는 다음을 가정하자.

$(x^*, \lambda^*, \nu^*)$ 가 KKT condition을 만족한다. (=respects the KKT condition)

우리는 여기서 $p^* \leq d^*$ 와 $p^* \geq d^*$ 임을 모두 보일 것이다.

먼저 $p^* \leq d^*$ 이다. 이는 곧 $f(x^*) = g(\lambda^*, \nu^*)$ 임을 보이는 것과 같다. 왜냐하면 $p^* \leq f(x^*)$ 이고, $g(\lambda^*, \nu^*) \leq d^*$ 이기 때문이다.

KKT conditions를 이용하면, 우리는 $\lambda^*_i f_i(x^*) = 0$ 과 $Ax^*-b = 0$ 임을 알기 때문에 $f(x^*)$ 를 다음과 같이 표현할 수 있다.

f(x^*) = f(x^*) + \sum_{i=1}^{m} \lambda_i^* f_i(x^*) + \nu^{* \intercal} (Ax^*-b)

그렇다면 $f(x^*)$ 는 $\mathcal{L}(x^*, \lambda^*, \nu^*)$ 와 같다. 다음으로는 Lagrange function과 dual function의 관계를 보자.

\begin{aligned} g(\lambda^*, \nu^*) &:= \min_{x\in \mathcal{X}} \mathcal{L}(x, \lambda^*, \nu^*) \\ &= \min_{x\in \mathcal{X}} f(x) + \sum_{i=1}^{m} \lambda_i^* f_i(x) + \nu^{*\intercal} (Ax - b) \\ &\overset{(a)}{=} f(x^*) + \sum_{i=1}^{m} \lambda_i^* f_i(x^*) + \nu^{*\intercal} (Ax^* - b)\\ &= \mathcal{L}(x^*, \lambda^*, \nu^*) \\ \end{aligned}

여기서 $(a)$ 가 성립하는 이유는 KKT condition에 의해 $x^*$ 가 minimizer 이기 때문이다.

따라서 $f(x^*) = g(\lambda^*, \nu^*)$ 임을 알 수 있다.

이제 $p^* \geq d^*$ 임을 보이겠다.

시작에 앞서 $p^*$ 값을 얻게 하는 primal optimal point를 $\tilde{x}$ 라 두자. 또한 dual optimal point $(\tilde{\lambda},\tilde{\nu})$ 로 $d^*$ 를 얻을 수 있다 가정하자. (이러한 가정을 하는 이유는 $x^*$ , $\lambda^*$ , $\nu^*$ 가 primal 및 dual problem에 대한 optimal point라고 할 수 없기 때문이다; 저들은 그저 KKT condition을 만족하고 있을 뿐이다.)

\begin{aligned} p^* &= f(\tilde{x}) \\ &\overset{(a)}{\geq} f(\tilde{x}) + \sum_{i=1}^{m} \tilde{\lambda}_i f_i(\tilde{x}) + \tilde{\nu}^{\intercal} (A\tilde{x} - b) \quad (=\mathcal{L}(\tilde{x}, \tilde{\lambda}, \tilde{\nu}))\\ &\geq \min_{x\in \mathcal{X}} f(x) + \sum_{i=1}^{m} \tilde{\lambda}_i f_i(x) + \tilde{\nu}^{\intercal} (Ax - b)\\ &\overset{(b)}{=} g(\tilde{\lambda}, \tilde{\nu}) \\ &= d^* \\ \end{aligned}

여기서 $(a)$ 가 성립하는 이유는 $(\tilde{\lambda},\tilde{\nu})$ 가 feasible point 라 $\tilde{\lambda}_i f_i(\tilde{x}) \leq 0$ , $A\tilde{x} - b=0$ 이기 때문이다. $(b)$ 는 dual function의 정의에 의해 성립한다.