목표: 원점에서 가장 가까운 $x$ 를 찾고 싶은데 단, $x$ 는 무조건 3보다 크거나 같아야 한다.
원 문제와 제약조건.png
$\min_{x} f(x) = x^2$
s.t. $x \ge 3$

먼저 눈으로 풀어보면, $x^2$ 을 가장 작게 만들고 싶은데 $x$ 가 3이상이어야 하니, 정답은 $x^{*}=3$ 이고, 그때 최솟값은 $p^{*} := 9$ 이다. 이제 이 9라는 값을 미분과 라그랑주 승수를 사용하여 유도할 수 있다.

제약 조건을 다음과 같이 정의할 수 있다.
$g(x) := 3 - x \le 0$

제약 조건을 $g(x) \le 0$ 형태를 맞추는 이유는, $\lambda \ge 0$ 으로 설정했기 때문이다. 이는 어떤 $x$ 가 제약 조건을 지키지 못했을 경우에 $\lambda$ 만큼 패널티를 준다는 의미이다. 만약 $g(x) \ge 0$ 으로 제약 조건을 설정했다면, $\lambda \le 0$ 로 설정하면 똑같은 결과를 얻을 수 있다. 여기서는 $g(x) \le 0, \lambda \ge 0$ 로 두고 문제를 풀이하겠다.

제약 조건을 목적 함수로 올리고, 라그랑주 승수 $\lambda$ 를 사용하여 다음과 같이 라그랑지안 함수를 정의한다. 이는 3차원 공간에서 안장점을 가진다.
라그랑지안 함수.png

$$ \mathfrak{L}(x, \lambda) := x^2 + \lambda(3 - x) $$
$$ \mathfrak{L}(x, \lambda) = x^2 - \lambda x + 3\lambda $$

이로써 $x$ 가 무조건 3보다 커야한다는 제약은 사라졌지만, 대신 원래 제약( $x \ge 3$ )을 지키지 않는다면 양수 $\lambda$ 를 곱해 $\mathfrak{L}$ 을 최소화하는데 패널티를 준다는 뜻이다.

어떤 $x$ 가 제약 조건을 만족한다면 $g(x) \leqslant 0$ 이고, $\lambda$ 는 양수이므로 $\mathfrak{L}$ 의 값은 원 함수 $f(x)=x^2$ 보다 항상 작거나 같다. 이는 $\mathfrak{L}$ 가 $f$ 의 하한(lower bound)임을 뜻한다.

$$ \mathfrak{L}(x, \lambda) = x^2 + \lambda g(x) \le x^2 = f(x) $$
$$ \mathfrak{L} \le f $$

만약 어떤 $x$ 가 제약 조건을 만족하지 않았다면, $g(x) > 0$ 이며, $\lambda$ 또한 양수이므로 최소화하려는 목적 함수 $f(x)$ 에 강한 패널티를 주게 된다. 앞서 제약 조건과 라그랑주 승수를 $g(x) \le 0, \lambda \ge 0$ 으로 설정하는 이유는, 패널티 항이 어떤 $x$ 가 제약 조건을 지키지 못했을 경우 벌금(양수)으로 작동하도록 맞추는 작업이다.

입력 변수 $x$ 에 대한 제약 조건이 없을 경우 주어진 함수의 미분함수를 0으로 만드는 점(임계점: 기울기=0)에서 최적해(최소값)가 나온다는 것은 쉽게 알 수 있다.

라그랑지안 함수의 최소값을 구하기 위해 $x$ 또는 $\lambda$ 에 대해 미분하여 0이 되는 지점을 찾아야 한다. 이때 보다 일반적인 상황을 생각하므로 고려하여 $x$ 에 대해 미분할 것이다(이는 이후 KKT 조건으로 다루겠다).

$$ \frac{\partial \mathfrak{L}}{\partial x} = 2x - \lambda = 0 $$
$$ \implies x = \frac{\lambda}{2} $$

이는 기하학적으로 3차원 직교 좌표공간에 비스듬하게 있는 평면이다. 이를 라그랑지안에 대입하여 $x$ 를 소거한다는 것은 그 비스듬한 평면위에 3차원 궤적을 남긴 후 기존 직교좌표계의 $\lambda \times$ 함숫값 평면에 정사영하는 것과 같다. 결과적으로 오목(위로 볼록, concave)한 쌍대 함수 $\mathfrak{D}(\lambda)$ 를 얻는다.
대입과 정사영.png
desmos로도 시각화해봤다. 빨간 지형이 라그랑지안 함수이며, 파란 평면이 $x = \frac{\lambda}{2}$ 를 만족하는 평면이다(y축이 람다축이다).
desmos시각화.png

$$ \mathfrak{D}(\lambda) := \left(\frac{\lambda}{2}\right)^2 + \lambda\left(3 - \frac{\lambda}{2}\right) $$
$$ = \frac{\lambda^2}{4} + 3\lambda - \frac{\lambda^2}{2} $$
$$ \mathfrak{D}(\lambda) = 3\lambda - \frac{\lambda^2}{4} $$

이 하한 $\mathfrak{D}(\lambda)$ 는 원래 참값보다 항상 아래에 있다(약한 쌍대성). 따라서 이 쌍대 함수를 최대화하기 위해 극대점을 찾아야 하므로 미분하여 0이 되는 $\lambda$ 를 찾아야 한다.

$$ \frac{d\mathfrak{D}}{d\lambda} = 3 - \frac{2\lambda}{4} = 3 - \frac{\lambda}{2} = 0 $$
$$ \implies \lambda^* = 6 $$

이를 쌍대 함수에 대입해 쌍대 최적해 $d^{*}$ 를 구한다.

$$ d^* = \mathfrak{D}(6) = 3(6) - \frac{6^2}{4} = 18 - 9 = 9 $$

쌍대 문제 최대화.png
관련 코드는 깃허브를 참고하길 바란다.

L을 람다에 대해 미분하면 3-x=0을 만족하는 x가 3이어서 문제 푸는게 아닌가.
이건 현재 예제에서 최적해서 제약 조건 바깥에 있기 때문에. 최적해가 제약조건 내에 존재한다면 제약 조건을 고려하지 않아도 되는게 아닌가?

Reference

최적 의사결정을 위한 경영과학, 권수태외 5인, 청람, 2018