제한조건이 있는 최적화 문제는 연립 방정식과 연립 부등식의 풀이 방법이 다르다.
연립 방정식은 라그랑주 승수법으로, 연립 부등식은 라그랑주 승수법에 KKT 조건을 만족하도록 푸는데 풀이가 거의 비슷하다.
라그랑주 승수법
원리는 두 가지 조건을 동시에 만족시키는 공통 접선을 찾는다. 즉, 제약 조건을 만족하며 최솟값, 최댓값을 찾는 것이다.
라그랑주 승수법은 목적함수 $f(x)$와 제약조건 $g(x)$가 있을 때, 하나의 식으로 만든다. 따라서, 제약조건이 달려있는 목적함수의 경우 라그랑주 승수법을 이용해 식을 간단하게 전개할 때도 사용한다.
공식
$h(x, \lambda) = f(x) + \sum_{j=1}^M\lambda_j g_j(x)$
예시
$f(x_1, x_2) = x_1^2 + x_2^2$를 최소화하며,
$g(x_1, x_2) = x_1 + x_2 - 1 = 0$ 제약조건을 만족해야 할 때 $h(x_1, x_2, \lambda)
= f(x_1, x_2) + \lambda g(x_1, x_2)
= x_1^2 + x_2^2 + \lambda ( x_1 + x_2 - 1 )$로 식을 전개할 수 있다.
최저점을 구하기 위해선 위의 식에서 각 변수에 대해 편미분을 진행하면 된다.
$\dfrac{\partial h}{\partial x_1}
= 2{x_1} + \lambda = 0 \\
\dfrac{\partial h}{\partial x_2}
= 2{x_2} + \lambda = 0 \\
\dfrac{\partial h}{\partial \lambda}
= x_1 + x_2 - 1 = 0$
위의 해를 풀면
$x_1 = x_2 = \dfrac{1}{2}, \;\;\; \lambda = -1$
최소점을 찾을 수 있다.
최소점을 찾는 것이 목표기 때문에 라그랑주 승수값은 필요 없다.
KKT 조건
연립 부등식인 경우 라그랑주 승수법을 그대로 사용해주면 된다. 하지만, 연립 방정식과는 다르게 KKT 조건이 붙는다.
- 모든 변수 $x_1,...,x_n$에 대한 미분 값이 0이다.
- 모든 라그랑주 승수 값과 제한조건 부등식(라그랑주 승수 값에 대한 미분 값)의 곱이 0이다.
- 라그랑주 승수는 음수가 아니어야 한다.
맨 첫 번째 조건은 라그랑주 승수의 조건에도 포함되어있다. 최소점을 찾기 위해 미분 값이 0이 되는 지점을 찾기 때문이다.
두 번째 조건은 라그랑주 승수에 대한 미분 값이 0이거나, 라그랑주 승수가 0이 되어도 된다.
세 가지의 조건이 모두 만족하지 않으면, 나온 값이 결국 정답이라고 할 수 없다.
즉, 최소점일 수는 있으나 제약조건에 만족하지 못한다는 문제가 생긴다. 이 문제에 대해서는 아래의 문제 풀이 링크를 참조하면 될 것이다.
라그랑주 승수 법과 KKT 조건의 문제 풀이는 다음 영상을 참고하라.
'수학 > 데이터 사이언스 스쿨' 카테고리의 다른 글
비선형 상관관계: 스피어만 상관계수, 켄달타우 (2) | 2020.05.14 |
---|---|
뉴턴 방법, 준 뉴턴 방법 (0) | 2020.04.23 |
테일러 급수, 헤시안 행렬 (1) | 2020.04.17 |
3-1. 고급 선형대수: 선형대수와 해석기학의 기초 (0) | 2020.03.25 |
3-2. 고급 선형대수: 좌표와 변환 (0) | 2020.03.23 |