제약 최적화와 라그랑주 승수법
Chapter 2 : Constrained Optimization and Lagrange Multipliers
Edited by / 임수형 (sulogc) 
제약 최적화
이전 7.1 장에서 $ f : \mathbb{R}^d \rightarrow \mathbb{R} $ 에서 정의되는 함수의 최소값을 찾는 문제를 보았다. 이번 장에서는 제약이 추가된 최적화를 푸는 법을 소개할 것이다. $ i = 1, …, m $ 에 대해, $ g_i : \mathbb{R}^d \rightarrow \mathbb{R} $ 일 때,
함수 $ f \text { 와 } g_i $ 가 일반적인 경우 볼록 함수가 아닐 수 있다. 볼록 함수인 경우는 7.3 장에서 다루겠다. 제약 문제를 비제약 문제로 바꾸는 명확한 방법은 지시함수를 사용하는 것이다. 다음은 지시함수 infinite step function이다.
이를 활용하여, 다음과 같은 새로운 함수의 최소값을 구하는 문제로 바꿀 수 있다.
제약으로 0보다 작아야하는 $ g $ 가 0 이상일 경우 $ J(x) $가 발산해 버린다. 물론 infinite step function 또한 최적화 하기가 까다롭다.
라그랑주 승수법
여기서 라그랑주 승수법을 소개한다. 라그랑주 승수는 step function을 선형 함수로 대체할 수 있다.
각 부등 제약식에 $ \lambda_i \ge 0 $ 를 도입하여 식 (7.1)을 라그랑지안으로 바꿀 수 있다. 다수의 부등 제약식 $ g_i(x) $ 와 그에 각각 대응하는 라그랑지안 승수 들은 벡터 $ g(x), \lambda \in \mathbb{R} $ 으로 표현 가능하다.
이제, 라그랑주 쌍대성(Lagrangian duality)에 대해 알아보자. 일반적으로 최적화에서 쌍대성이란, 원시변수 x에 대한 최적화 문제를 쌍대 변수 $ \lambda $ 에 대한 최적화 문제로 바꾸는 것을 말한다. 쌍대성에 대한 두 가지 다른 접근 방법으로, 먼저 라그랑주 쌍대성에 대해 알아보고 7.3에서 르장드르-펜첼 쌍대성에 소개하겠다.
정의 7.1 다음과 같은 원시문제가 주어졌을 때,
\[\begin{matrix} \min\limits_{x} & f(x) & \\ \text {subject to } & g_i(x) \leqslant 0 & \text { for all i = 1, ..., m } \end{matrix}\]
원시 문제의 쌍대 문제는 다음과 같이 주어진다.
$ \lambda $ 를 쌍대 변수로, $ \mathfrak D (\lambda) = \min _{x \in \mathbb R^d} \mathfrak L (x, \lambda) $ 인 라그랑주 쌍대 문제가 주어진다.
두 가지 전제:
7.1에서 다음 두 가지 전제가 있었다. 첫 번째는, minimax inequlaity로, 두 변수를 받는 어떤 함수 $ \varphi (x, y) $ 에 대해 maximin이 minimax보다 작다는 것이다.
이 부등식은 다음의 부등식을 필요로한다.
\[\begin{align} \text{ for all } x, y \min \limits _{x} \varphi(x, y) \leq \max \limits _{y} \varphi(x ,y) && ...(b) \end{align}\](b)식에서 모든 $ x, y $ 에 대해 성립 하므로, 좌변을 최대로 하고, 그 변수를 유지한 채로 우변을 최소로 하여도 성립한다.
두 번째는, 약 쌍대성으로 식 (a)룰 통해 원시값이 쌍대값보다 크거나 같음을 보일 수 있다.
식 (7.2)의 $ J(x) $와, (7.3)의 Lagrangian의 차이는 indicator function이 선형함수가 되도록 제약을 풀어준 것이다. 그러므로 $ \lambda $ 가 양수일 때 Lagrangian $ \mathfrak L (x, \lambda) $ 는 $ J(x) $의 하한이 된다. 따라서 $ \lambda $ 에 대한 $ \mathfrak L (x, \lambda) $ 의 최댓값은 다음과 같이 표현된다.
\[\begin{align} J(x) = \max \limits _{\lambda \geq 0} \mathfrak L (x, \lambda) \end{align}\]
원래 문제는 $ J(x) $ 를 최소화 하는 것이므로,
위에서 본 minimax inequality를 통해,
\[\begin{align} \min \limits _{x \in \mathbb R^d} \max \limits _{\lambda \geq 0} \mathfrak L (x, \lambda) \geq \max \limits _{\lambda \geq 0} \min \limits _{x \in \mathbb R^d} \mathfrak L (x, \lambda) \end{align}\]
이는 약 쌍대성으로 알려져 있다. 우변의 max 안쪽 항은 쌍대 목적함수 $ \mathfrak D (\lambda) $ 이다.
제약조건을 갖던 원래 최적화 문제를 $ \lambda $ 에 대한 비제약 최적화 문제 $\min \limits _{x \in \mathbb R^d} \mathfrak L (x, \lambda)$ 로 바꾸었다. $\min \limits _{x \in \mathbb R^d} \mathfrak L (x, \lambda)$ 를 푸는 것이 쉽다면, 전체적으로 문제도 풀기 쉬운 문제가 된다. 이는 식 (7.3)에서 $\min \limits _{x \in \mathbb R^d} \mathfrak L (x, \lambda)$이 $ \lambda $ 에 대한 affine임을 통해 알 수 있다. 그러므로 $\min \limits _{x \in \mathbb R^d} \mathfrak L (x, \lambda)$은 $ \lambda $의 affine function에 대한 minimum이 되고, $\mathfrak D (\lambda)$는 $ f(\cdot) $과 $ g(\cdot) $의 형태에 상관없이 concave하다. 바깥쪽 항에 대한 문제(maximization over $ \lambda $)는 concave function에 대한 최대화 문제이므로 효율적으로 계산할 수 있다.
$ f(\cdot) $ 과 $ g(\cdot) $ 가 미분가능하다고 가정하면, 라그랑지안을 $ x $에 대해 미분하여 라그랑지안 쌍대 문제를 찾을 수 있고, 이를 0 으로 놓으면 최적해를 구할 수 있다.