11-1 Lagrangian

다음은 다음 최적화 문제에 대한 Lagrangian 형태를 살펴본다. 여기서, 최적화 문제는 반드시 convex일 필요는 없다.

$$\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}$$

이 때, Lagrangian은 아래와 같이 정의한다.

$$L(x,u,v)=f(x)+\sum _{i=1}^m{u}_i{h}_i(x)+\sum _{j=1}^r{v}_j{l}_j(x)$$

여기서, $u\in {\mathbb{R}}^m$, $v\in {\mathbb{R}}^r$, $u\ge 0$ (implicitly, $L(x,u,v)=-\mathrm{\infty }$ for $u<0$).

위 Lagrangian에서, $h_i(x)\le 0$, $l_j(x)=0$ 이므로,

$$L(x,u,v)=f(x)+\sum _{i=1}^m{u}_i\underset{\le 0}{\underbrace{h_i(x)}}+\sum _{j=1}^r{v}_j\underset{=0}{\underbrace{l_j(x)}}\le f(x)$$

즉, Lagrangian은 다음의 중요한 성질을 갖는다.

모든, $u\ge 0$, $v$에 대해, $f(x)\ge L(x,u,v)\text{ at each feasible }x$

예를 들면, 아래 그림에서,

• Solid line은 함수 $f$를 의미
• Dashed line은 함수 $h$를 의미함. 여기서 feasible set 대략 $[-0.46,0.46]$임
• 각 Dotted line은 $u\ge 0$, $v$에 대한 함수 $L(x,u,v)$를 의미