프라이멀 문제와 듀얼 문제의 유도

제약조건을 갖는 최적화 문제는 지시함수(indicator function)를 이용하면 제약조건이 없는 최적화 문제로 바꿀 수 있다.

 

 

지시함수는 어떤 집합에 어떤 값이 속하는지를 표시하는 함수로서 어떤 집합 $\mathcal{X}$ 의 지시함수 $I_{\mathcal{X}}$ 는 다음과 같이 정의된다.

 

$$\begin{array}{}\text{(1)}& I_{\mathcal{X}}(\mathbf{x})=\{\begin{array}{ll}0,& \text{if }\mathbf{x}\in \mathcal{X}\\ \mathrm{\infty },& \text{if }\mathbf{x}\notin \mathcal{X}\end{array}\end{array}$$

 

 

 

다음과 같은 제약조건을 갖는 최적화 문제가 있을 때,

 

$$\begin{array}{r}\text{(2)}& & \underset{\mathbf{x}\in {\mathbb{R}}^n}{min}f(\mathbf{x})\\ \text{subject to: }& \mathbf{x}\in \mathcal{X}\end{array}$$

 

지시함수를 이용하면 위 최적화 문제를 다음과 같이 제약조건이 없는 형태로 변환할 수 있다.

 

$$\begin{array}{}\text{(3)}& \underset{\mathbf{x}\in {\mathbb{R}}^n}{min}f(\mathbf{x})+I_{\mathcal{X}}(\mathbf{x})\end{array}$$

 

구체적으로 등식 제약조건과 부등식 제약조건이 있는 최적화 문제에 대해서 지시함수를 이용하여 제약조건이 없는 최적화 문제로 변환해 보자. 먼저 등식 제약조건이 있는 경우다.

 

$$\begin{array}{r}\text{(4)}& & \underset{\mathbf{x}}{min}f(\mathbf{x})\\ \text{subject to: }& h_j(\mathbf{x})=0,j=1,...,k\end{array}$$

 

등식 제약함수의 지시함수는 다음과 같이 함수의 max 연산으로 표현 가능하다.

 

$$\begin{array}{r}\text{(5)}& I_j(h_j(\mathbf{x}))& =\{\begin{array}{ll}0,& \text{if }{h}_j(\mathbf{x})=0\\ \mathrm{\infty },& \text{if }{h}_j(\mathbf{x})\ne 0\end{array}\\ & =\underset{{\lambda }_j}{max}{\lambda }_j{h}_j(\mathbf{x})\end{array}$$

 

여기서 ${\lambda }_j$ 는 일종의 패널티 함수(penalty function)에서의 패널티 항이라고 볼 수 있다. 식 (5)를 (3)에 대입하면 등식 제약조건이 있는 최적화 문제 (4)를 다음과 같이 minmax 문제로 바꿀 수 있다.

 

$$\begin{array}{}\text{(6)}& \underset{\mathbf{x}}{min}\underset{{\lambda }_j}{max}f(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})\end{array}$$

 

식 (6)은 등식 제약조건이 있는 최적화 문제를 minmax 문제로 정식화한 것이다. 한편, 라그랑지 곱수법(Lagrange multiplier)을 이용하면 등식 제약조건이 있는 최적화 문제를 다음과 같이 정식화 할 수 있었다.

 

$$\begin{array}{}\text{(7)}& \underset{\mathbf{x},{\lambda }_1,{\lambda }_2,...,{\lambda }_k}{min}f(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})\end{array}$$

 

식 (6)과 (7)은 동일한 최적화 문제에 대한 두가지 관점으로 해석할 수 있다. 식 (6)에 있는 ${\lambda }_j$ 도 식 (7)에서와 같이 라그랑지 곱수라고 한다.

 

 

부등식 제약조건이 있는 최적화 문제는 다음과 같다.

 

$$\begin{array}{r}\text{(8)}& & \underset{\mathbf{x}}{min}f(\mathbf{x})\\ \text{subject to: }& g_i(\mathbf{x})\le 0,i=1,...,m\end{array}$$

 

마찬가지로 부등식 제약함수의 지시함수도 다음과 같이 함수의 max 연산으로 표현 가능하다.

 

$$\begin{array}{r}\text{(9)}& I_i(g_i(\mathbf{x}))& =\{\begin{array}{ll}0,& \text{if }{g}_i(\mathbf{x})\le 0\\ \mathrm{\infty },& \text{if }{g}_i(\mathbf{x})>0\end{array}\\ & =\underset{{\mu }_i\ge 0}{max}{\mu }_i{g}_i(\mathbf{x})\end{array}$$

 

 

 

위 식에서 식 (5)와 차이점은 라그랑지 곱수 ${\mu }_i$ 가 음수(마이너스)가 아니라는 조건이 있다는 것이다. 이것은 식 (9)를 지시함수로 만들기 위해 필요한 조건이다. 식 (9)를 (3)에 대입하면 부등식 제약조건이 있는 최적화 문제 (8)을 다음과 같이 minmax 문제로 바꿀 수 있다.

 

$$\begin{array}{}\text{(10)}& \underset{\mathbf{x}}{min}\underset{{\mu }_i\ge 0}{max}f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})\end{array}$$

 

최종적으로 식 (6)과 (10)을 이용하면 등식과 부등식 제약조건이 있는 일반적인 최적화 문제를 다음과 같이 제약조건이 없는 minmax 문제로 바꿀 수 있다.

 

$$\begin{array}{}\text{(11)}& \underset{\mathbf{x}}{min}\underset{{\lambda }_j,{\mu }_i\ge 0}{max}f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})\end{array}$$

 

식 (11)의 함수를 라그랑지안(Lagrangian)이라고 한다.

 

$$\begin{array}{}\text{(12)}& L(\mathbf{x},{\mu }_1,...,{\mu }_m,{\lambda }_1,...,{\lambda }_k)=f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})\end{array}$$

 

식 (11)에서 min과 max의 순서를 바꾸면 다음과 같이 maxmin 문제가 된다.

 

$$\begin{array}{}\text{(13)}& \underset{{\lambda }_j,{\mu }_i\ge 0}{max}\underset{\mathbf{x}}{min}f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})\end{array}$$

 

식 (13)을 듀얼 문제(dual problem)라고 하고, 식 (11)을 프라이멀 문제(primal problem)라고 한다. 이 둘은 최적화 문제에 대한 두가지 관점을 보여주는데 어떤 문제에서는 프라이멀 문제보다도 듀얼 문제로 바꾸어서 푸는 것이 효과적일 수 있다. 프라이멀 문제와 듀얼 문제에 대한 논의는 다음 게시글을 참고하기 바란다.

 

[KKT 조건 - 3] 프라이멀 문제와 듀얼 문제