Deep dive into optimization : Duality (1) - Updated

 

usechatgpt init success

모바일 앱 환경에서는 latex 수식이 깨져 나타나므로, 가급적 웹 환경에서 봐주시길 바랍니다.

 

수학에서 "Duality principle"은 매우 중요하고 수학의 각 분야별로 다양하게 응용/확장되는 개념이다. 

그 중 Convex optimization에서 이야기하는 Duality는 기존의 최적화 문제 (primal problem)을 다른 문제 형태 (dual problem)로 푸는 것을 의미하는데, 이에 대해서 살펴보도록 하자. 

 

다음과 같은 constrained optimization problem을 고려해보자.

 

이렇게 constrained condition이 있는 optimization problem을 푸는 방법은 크게 두 가지가 있다.

하나는 Lagrangian function을 도입해서 푸는 방법이고, 다른 하나는 Dual problem으로 바꿔 푸는 방법이다.

하지만, 이 두 가지는 전혀 다른 것이 아니라 서로 긴밀하게 연결되어져 있다.

이 중 후자가 Duality를 의미하며, 이는 하나의 optimization problem을 두 가지 관점, 즉 Primal problem과 Dual problem으로 바라보고 푸는 것이다.

 

먼저 Lagrangian function을 도입해서 푸는 방법에 대해 간단하게 설명하고, Duality로 들어가자.

Lagrangian은 학부 미적분학 수업에서 많이 다루므로 배웠다면 복습하는 느낌으로 보면 될 것이다.

위 문제를 Lagrangian function을 도입하면 다음과 같이 바뀐다. 

 

Lagrangian function

 

여기서 $\lambda_i \ge 0$은 Lagrange multiplier라고 부른다.

마지막 등식은 모든 $\lambda_i$와 $g_i$를 vector로 표현한 것이다.

 $\lambda$ vector의 모든 성분이 $0$보다 커야 함은 일종의 조건이다. 

 

그렇다면 만약 등호가 있는 제약식이 존재하는 optimization problem이라면 어떻게 될까? 새로운 Lagrange multiplier 하나를 더 추가해주면 된다.

 

Primal problem은 다음과 같이 될 것이다.

 

물론 꼭 $0$일 필요는 없다. 하지만 지금은 설명의 편의를 위해 $0$으로 설정하였다.

 

위 문제의 Lagrangian function은 다음과 같다.

 

여기서 앞서 $\lambda$처럼, 벡터 $u$의 모든 성분은 0 이상의 값을 가져야 한다.

 

그렇다면 $\mathcal{L}(x, u, v)$는 항상 $f(x)$보다 작거나 같다. 왜냐하면 $v^T h(x) =0$이고, $u^T g(x) \le 0$이기 때문이다. 

그렇다면 $\mathcal{L}(x, u, v) \le f(x)$가 성립한다.

$f^* := f(x^*)$라고 해보자. 여기서 $x^*$는 Primal problem의 optimal solution이다.

 

$f^* \ge \min_{x \in C} \mathcal{L}(x, u, v) \ge \min_x \mathcal{L}(x, u, v)$

 

$\mathcal{L}(x, u, v)$는 항상 $f(x)$보다 작거나 같으므로, $f(x)$의 최솟값 $f^*$보다 작거나 같다.

여기서 $C$는 feasible set, 즉 primal problem의 constraint condition을 만족하는 $x$의 집합이다.

이는 결국 제약조건이 있는 것보다는 없는 상황에서 식을 더 작게 만들 수 있다는 의미이다.

위 부등식에서 마지막 항을 $g(u, v)$라 하자. 이때 $g(u,v)$를 우리는 Lagrange dual function이라 부른다.

 

Lagrange dual function $g(u,v)$는 정의가 $\min_x \mathcal{L}(x, u, v)$이기 때문에 $\mathcal{L}$의 최소값이다. 

그렇다면 $\mathcal{L}$을 $x$에 대해서 편미분하여 $0$이 되는 지점을 찾으면 된다.

이를 $\mathcal{L}$에 대입하여 정리하면, $g(u,v)$를 구할 수 있고, $f^* \le g(u, v)$이므로, 결국 $f^*$를 찾는 것은 $g(u, v)$를 최대화하는 문제와 동일하다.

즉, 원래의 primal problem은 $g(u, v)$, Lagrange dual function을 maximize하는 dual problem으로 바뀌게 된다.

 

이때 중요한 특징이 dual problem은 항상 'convex problem'이다. 

 

위 내용을 요약하여 정의를 내리면 다음과 같다.

 

위와 같은 원래의 primal problem이 있고 이 때 $x$는 primal variable이라 부른다.

이에 대한 Lagrange dual problem은 아래와 같이 정의된다.

 

이 때 $\mathcal{D}(\lambda)$은 Lagrangian dual function, 즉 $\min_x \mathcal{L}(x, \lambda)$이다.

 

앞서 이야기한대로, 위와 같이 문제를 바꿔 풀 수 있는 이유는 primal problem의 lower bound가 dual problem의 upper bound이기 때문제, primal problem을 minimize하는 것을 dual problem을 maximize하는 것으로 바꿔 풀 수 있다.

 

---

* 추가적으로 이는 minmax inequality와도 관련 있는데 두 변수를 가진 임의의 함수가 있을 때 다음 부등식이 항상 성립한다.

$\max_y \min_x f(x, y) \le \min_x \max_y f(x,y)$

 

Lagrangian dual function은 그 정의가 $\min_x \mathcal{L}(x, \lambda)$이다. 이를 maximize하는 dual problem은 

$\max_{\lambda} \min_x \mathcal{L}(x, \lambda)$이다. 이는 위 minmax inequality에 의하여 $\min_x \max_{\lambda} \mathcal{L}(x, \lambda)$보다 항상 작거나 같다. 즉 다음이 성립한다.

 

$\min_x \max_{\lambda} \mathcal{L}(x, \lambda) \ge \max_{\lambda} \min_x \mathcal{L}(x, \lambda)$

 

여기서 $\max_{\lambda \ge 0} \mathcal{L}(x, \lambda)$는 $f(x)$로 볼 수 있고, 결국 정리하면, $\min_x f(x, \lambda^*) \ge \max_{\lambda} \mathcal{L}(x^*, \lambda)$이다.

$x^*$는 primal problem의 optimal solution, $\lambda^*$는 dual problem의 optimal solution이다.

이를 통해 다시 한 번 primal problem의 lower bound가 dual problem의 upper bound가 됨을 알 수 있다. *

 

---

그리고 Lagrangian dual function은 concave하기 때문에 global maxima = local maxima이고, 이는 원래의 primal problem의 convexity와는 상관없이 성립하기 때문에, dual problem을 푸는 것이 더 쉬워질 수 있다.

 

그리고 앞서 primal problem의 lower bound가 dual problem의 upper bound라는 사실을 거듭 언급하였고,

여기서 한 가지 개념을 추가적으로 언급하면 primal problem의 lower bound와 dual problem의 upper bound가 같은 경우는 'Strong duality', 다른 경우는 'Weak duality'라고 한다.

수식으로 표현하면 다음과 같다.

 

여기서 등호관계만 성립하는 경우를 우리는 'strong duality'라 하고, 이는 $f^*$와 $g^*$의 차이가 존재하지 않는 것인 반면에, $f^*$와 $g^*$ 사이의 차이가 존재하는 일반적인 경우를 'Weak duality'라 하고, 이때의 차이를 'duality gap'이라 한다.

 

그렇다면 언제 Strong duality가 성립하는가? 'Slater's condition'이 만족할 때 성립하는데 이는 다음과 같다.

 

* Slater's condtion

만약,

$1$. Primal problem이 convex problem이고,

$2$. 적어도 하나의 'strictly' feasible solution이 존재한다면,

Strong duality가 성립한다.

 

이번 글에서는 duality의 아주 기초적인 개념들을 Lagrangian function과 연결지어서 이야기하였다.

다음 글에서는 구체적 예시를 통해 다시 한 번 이를 살펴보자.

Linear programming과 Quadratic programming에 오늘 이야기한 내용들을 적용해보고자 한다.