[최적화] 부등식 제약 최적화와 KKT 조건
부등식 제약 최적화 (Inequality Constrained Optimization)
부등식 제약 조건을 만족하면서, 목적 함수 $f(x)$의 값을 최소화하는 변수 $x$를 찾는 최적화 문제이다.
\[\begin{aligned} \mathbf{x}^*=\min_{\mathbf{x}}f(\mathbf{x})~~~~\\ \text{subject to}~g(\mathbf{x})\leq0 \end{aligned}\]이때의 라그랑주 함수는 일반적으로 아래와 같이 정의한다.
\[\mathcal{L}(\mathbf{x},\lambda)=f(\mathbf{x})+\mu g(\mathbf{x})\]이 경우는 아래의 조건을 모두 만족하는 점을 찾아야 한다.
\[\begin{equation}\nabla_{\mathbf{x},\lambda}\mathcal{L}=0\end{equation}\] \[\begin{equation}\mu g(\mathbf{x}^*)=0\end{equation}\] \[\begin{equation}\mu\geq0\end{equation}\]$(2)$번과 $(3)$번의 의미
1. $g(\mathbf{x})\leq0$ 제약 조건 내에 전역 최소점 (Global Minimum) $\mathbf{x}^*$이 있는 경우
이 경우에는 제약 조건 없이 $f(\mathbf{x})$에 대해서만 최소점을 찾아도 된다.
즉, 제약 조건이 있으나마나한 경우이기 때문에, $\mu=0$로 표현할 수 있다.
2. $g(\mathbf{x})\leq0$ 제약 조건 내에 전역 최소점 (Global Minimum) $\mathbf{x}^*$이 없는 경우
이 경우에는 제약 조건 밖에 전역 최소점이 존재한다.
즉, 전역 최소점이 제약 조건의 밖에 있기 때문에, 최적점은 제약 조건의 경계 $g(\mathbf{x})=0$에 존재하게 된다.
최적점에서 $f$의 그라디언트 방향은 안으로 들어가는 방향 ($f$가 커지는 방향)이고, $g$의 그라디언트 방향은 밖으로 나가는 방향 ($g$가 커지는 방향)이다.
즉, 최적점에서 $f$의 그라디언트와 $g$의 그라디언트의 방향은 다르다. 따라서, 아래 식이 만족하기 위해서는 $\mu\geq0$이어야 한다.
\[\nabla f(\mathbf{x})+\mu\nabla g(\mathbf{x})=0 ~~\to~~\nabla f(\mathbf{x})=-\mu\nabla g(\mathbf{x})\]
Example 1
점 $(x, y)$가 $x+y\geq1$ 영역에 있을 때, 원점 $(0,0)$으로부터 가장 가까운 점은 어디인가?
1. 목적 함수와 제약 조건 식 세우기
원점으로부터의 거리를 L2 norm의 제곱으로 가정한다.
\[\begin{aligned} \max_{x,y}~x^2+y^2~~~~~~\\ \text{subject to}~x+y\geq1 \end{aligned}\]2. 라그랑주 함수 정의
제약 조건을 $g(x)\leq0$의 형태에 맞게 변환한다.
\[g(x,y)=1-(x+y)\leq0\] \[\mathcal{L}(x,y,\lambda)=x^2+y^2+\mu(1-x-y)\]3-1. KKT (1)번 조건
\[\nabla_x\mathcal{L}=2x-\mu=0~\to~x=\frac{\mu}{2}\] \[\nabla_y\mathcal{L}=2y-\mu=0~\to~y=\frac{\mu}{2}\]3-2. KKT (4)번 조건
$\mu=0$인 경우
$x=y=0$이 되기 때문에 (2)번 조건 $x+y\geq1$에 위배된다.
$g(x,y)=0$인 경우
$x+y=1$이 되며, (1)번 조건에서 계산한 식에 의해 $x=y=\frac{1}{2}$이 된다.
이때 $x=y=\frac{1}{2}$이므로, $\mu=1$이다.
따라서, 해당 제약 조건에서 원점에서 가장 가까운 점은 $(\frac{1}{2},\frac{1}{2})$이다.
4. 연립 방정식 풀기
\[\begin{cases} x=\lambda\\y=\lambda\\x+y=10 \end{cases}~~~~\to~x=y=5\]따라서 최대 넓이는 $25$, 그때의 가로와 세로의 길이는 각각 $5, 5$이다.
제약 조건이 여러 개인 경우
등식 최적화 문제와 비슷하게, 부등식 최적화 문제에서도 아래의 라그랑주 함수를 풀면 된다.
\[\mathcal{L}(\mathbf{x}^*,\boldsymbol\mu)=f(\mathbf{x})+\sum_{k=1}^M\mu_k g_k(\mathbf{x})\] \[\nabla\mathcal{L}(\mathbf{x}^*,\boldsymbol\lambda)=\nabla f(\mathbf{x})+\sum_{k=1}^M\mu_k \nabla g_k(\mathbf{x}) ~~,~~\mu_kg(\mathbf{x}^*)=0~~,~~\mu_k\geq0\]KKT 조건 (Karush-Kuhn-Tucker conditions)
KKT 조건은 등식 제약 조건과 부등식 제약 조건을 모두 가진 일반적인 최적화 문제의 해가 만족해야 할 필요조건이다.
등식 제약 조건에 대한 승수를 $\lambda$, 부등식 제약 조건에 대한 승수를 $\mu$로 표현했을 때, 최적점 $\mathbf{x}^*$는 아래의 네 가지 조건을 만족해야 한다.
1. 정상성 (Stationarity)
라그랑주 함수의 그라디언트가 $0$이 되어야 한다는 조건이다.
\[\nabla f(\mathbf{x}^*)+ \sum_{i=1}^m\lambda_i\nabla_\mathbf xg_i(\mathbf x^*)+ \sum_{j=1}^p\mu_j\nabla_\mathbf xh_j(\mathbf x^*)=0\]2. 원문제 제약 적합성 (Primal Feasibility)
최적해는 주어진 모든 제약 조건을 만족해야 한다는 조건이다.
\[g_i(\mathbf x^*)\leq0~~,~~h_j(\mathbf x^*)=0\]3. 쌍대문제 제약 적합성 (Dual Feasibility)
부등식 제약 조건에 해당하는 라그랑주 승수는 항상 0보다 크거나 같아야 한다.
\[\vphantom{\Big(} \mu_j\geq0\]4. 상보적 여유성 (Complementary Slackness)
부등식 제약 함수와 그에 해당하는 승수의 곱은 항상 0이어야 한다.
\[\vphantom{\Big(} \mu_j g_j(\mathbf x^*)=0\]라그랑주 승수의 의미
부등식 제약 조건에 대한 라그랑주 승수 $\mu$를 그림자 가격 (shadow price)이라고 부른다.
이는 목적 함수의 최적값이 제약 조건에 대해 얼마나 민감한지를 나타내는 값이다.
즉, 제약 조건을 완화했을 때 목적함수의 최적값이 얼마나 변하는가를 나타내며, $\mu$가 크다는 것은 제약 조건을 조금만 완화해도 최적값이 크게 향상된다는 뜻으로 해석할 수도 있다.
공장에서의 물건 생산에서 아래의 조건이 있을 때, 원자재 1kg을 더 사용할 수 있다면 이윤이 얼마나 증가하는가?
- 제약 조건: 원자재는 최대 100kg 사용 가능
- 현재 최적 상태: 이윤 500달러, 원자재는 딱 100kg 사용 중
1kg 더 주었더니 이윤이 5달러 증가했다면, 이 5달러가 바로 shadow price이다.