11-3 Lagrange dual problem

다음과 같이 문제가 주어졌다고 하자.

$$\begin{array}{rl}\underset{x}{min}& f(x)\\ \\ s.t.& h_i(x)\le 0,i=1,\dots ,m\\ \\ & l_j(x)=0,j=1,\dots ,r\end{array}$$

Dual function $g(u,v)$는 모든 $u\ge 0$와 $v$에 대해 $f^{\ast }\ge g(u,v)$를 만족한다. 따라서, 모든 feasible한 $u$, $v$에 대해서 $g(u,v)$를 최대화함으로써 가장 좋은 lower bound를 구할 수 있다. 이를 Lagrange dual problem 이라 한다.

$$\begin{array}{rl}\underset{u,v}{max}& g(u,v)\\ \\ s.t.& u\ge 0\end{array}$$

여기서, dual 최적값을 $g^{\ast }$라고 하면 $f^{\ast }\ge g^{\ast }$이다. 이를 weak duality라 한다. 이 성질은 primal 문제가 convex가 아니어도 항상 성립한다. 또한, dual problem은 primal problem이 convex가 아니더라도 항상 convex optimization problem이 된다.

정의에 의해 $g$는 $(u,v)$에 대해 concave 하고, $u>0$는 convex 제약조건이다. 따라서, dual 문제는 concave maximization 문제에 해당된다.

$$\begin{array}{rl}g(u,v)& =\underset{x}{min}\{f(x)+\sum _{i=1}^m{u}_i{h}_i(x)+\sum _{j=1}^r{v}_j{l}_j(x)\}\\ & =-\underset{\text{pointwise maximum of convex functions in }(u,v)}{\underbrace{\underset{x}{max}\{-f(x)-\sum _{i=1}^m{u}_i{h}_i(x)-\sum _{j=1}^r{v}_j{l}_j(x)\}}}\end{array}$$

Example: nonconvex quartic minimization

다음 함수 $f(x)=x^4-50x^2+100x$를 $x\ge -4.5$에 대해 최소화 해 보자.

이 때, Dual 함수 $g$는 아래와 같다.

$$g(u)=\underset{i=1,2,3}{min}\{F_i^4(u)-50F_i^2(u)+100F_i(u)\}$$

여기서, $i=1,2,3$에 대해,

$$\begin{array}{rl}{F}_i(u)=& \frac{-a_i}{12\cdot 2^{1/3}}{(432(100-u)-({432}^2(100-u{)}^2-4\cdot {1200}^3{)}^{1/2})}^{1/3}\\ \\ & -100\cdot 2^{1/3}\frac{1}{{(432(100-u)-({432}^2(100-u{)}^2-4\cdot {1200}^3{)}^{1/2})}^{1/3}}\end{array}$$

그리고, $a_1=1,a_2=(-1+i\sqrt{3})/2,a_3=(-1-i\sqrt{3})/2$이다.

함수만 보면 $g$가 concave인지 알기어렵지만, duality의 convexity 하에 $g$가 concave라는 것을 알 수 있다.