Deep dive into Optimization : Duality (2) -Updated

 

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

 

 

오늘은 지난 글에 이은 Duality 두 번째 글이다.

https://kyteris0624.tistory.com/47

Deep dive into optimization : Duality (1)

 

다음과 같은 Linear programming 문제를 보자.

 

$A \in \mathbb{R}^{m \times d}, b \in $\mathbb{R}^m$이라 하자.

위와 같은 optimization problem을 Linear programming이라고 한다. 

 

위 문제의 Lagrangian은 다음과 같이 정의될 것이다.

 

 

여기서$\lambda$는 Lagrangian multiplier이다.

위 식을 $x$에 대해서 정리하면 아래와 같다.

 

Lagrangian function을 $x$에 대해서 미분해서 $=0$으로 두고 풀면 다음과 같이 나온다.

$c + A^T \lambda = 0$

 

또한 Lagrangian dual function은 $\mathcal{D}(\lambda) = - \lambda^T b$이므로 우리는 dual problem을 다음과 같이 정의할 수 있다.

 

이것이 앞선 Linear programming의 dual problem이며 역시나 Linear programming에 속한다.

 

그럼 다음으로 Quadratic programming을 알아보자.

 

 

위와 같은 문제를 Quadratic programming이라 하는데, 여기서 $Q$는 Symmetric matrix이다.

위의 Lagrangian function을 정의하고 $x$에 대해 정리하며 다음과 같다.

 

 

역시나 동일하게 $x$에 대해 미분하고 $0$으로 설정하면

 

$Qx + (c + A^T \lambda) = 0$

 

그리고 $Q$가 역행렬이 존재하는 invertible matrix라고 가정하면 우리는 $x$를 얻을 수 있다.

 

$x = -Q^{-1}(c + A^T \lambda)$

 

이걸 Lagrangian function에 대입하여 다시 정리하면, Lagrangian Dual function을 얻을 수 있고 

우리는 Dual problem을 다음과 같이 정의할 수 있다.

 

 

 

여기까지는 Lagrangian dual function을 활용해 primal problem을 dual problem으로 바꾸어보았다.

앞선 글에서 이야기한대로 Fenchel conjugate (convex conjugate)을 활용해서도 우리는 dual problem을 유도해볼 수 있다.

한번 그것에 대한 예시를 살펴보자.

 

 

 

 

다음과 같은 문제를 생각해보자.

 

이 문제를 $Ax = b$라 하여 다음과 같이 바꿔 표현해보자.

 

 

conjugate function을 이용하면 위 문제의 dual problem을 유도할 수 있다.

conjugate function은 다음과 같이 정의된다.

 

 

$f^*(s) = \max_x (s^T x - f(x)) = \min_x (f(x) - s^T x)$

 

 

primal problem의 Lagrangian form은 다음과 같다. Lagrangian multiplicity를 $v$로 표기하자.

 

 

우리는 $x, z$에 대해서는 $\min$를 구해야 하고, $v$에 대해서는 $\max$를 구해야 한다.

즉 위 Lagrangian function의 saddle point를 찾는 문제로 볼 수 있다.

(saddle point의 정의는 하나의 변수에 대해서는 global 또는 local minima, 다른 변수에 대해서는 global 또는 local maxima인 지점이다.)

 

이를 활용해서 문제를 정리해나가서 dual problem을 유도해보자.

 

$\max_v \min_{x, z} \mathcal{L}(x, z, v)$

$= \max_v \min_{x, z} v^Tz + g(z) - (A^T v)^T x + f(x)$

$= \max_v -f^*(A^T v) - g^*(-v)$

 

첫 번째에서 두 번째 등식은 Lagrangian function을 대입하며 z에 대한 term과 x에 대한 term으로 나누어 정리하였고,

마지막 등식은 Fenchel duality의 정의를 활용하여 식을 바꿔 표현하였다.

 

따라서 원래의 primal problem에 대한 Fenchel dual problem은 다음과 같이 표현된다.

 

 

 

 

이로써 Duality의 기본적인 개념, 그리고 그 개념을 활용해 Linear programming, Quadratic programming의 dual problem을 유도해보았다.

 

다음 글에서는 Mirror descent에 대해 이야기해보도록 하겠다.