비선형계획
이제, 목적함수와 제약식이 선형이 아닌 경우도 생각해볼 수 있다.
\begin{align*}
\min~~ &~f(x)\\
\text{s.t. } &~g(x) = 0\\
\end{align*}
단, 먼저 짚어봐야 할 것이 있다.
선형이 아닌 함수에서 어떻게 x값을 구했는지 보자.
비선형함수
f(x) = x^2 + 2x
만약 이러한 함수가 있을 때, 그 최솟값은 어떻게 구하는가?
- 표준형 꼴로 정리한 후, 그 해를 구한다.
- 미분을 해서 최솟값을 구한다.
f(x) = x^2 + e^x
그렇다면 이러한 함수가 있는 경우, 어떻게 최솟값을 구하는가?
미분을 해도 끝이 없기 때문에, 컴퓨터의 도움을 받는다.
주로, 뉴튼-랩슨 방법을 사용한다.
비선형계획과 편미분
이제 목적함수와 제약식이 비선형함수일 경우를 생각해 볼 수 있다.
- 연립방정식, 즉 행렬 형태로는 정리가 쉽게 안 된다.
- 그림을 그리는 것 또한 어려운 경우가 많다.
즉 비선형계획에서는 어쩔 수 없이 미분을 알아야 한다.
특히, 변수가 여러개인 경우가 많으므로 편미분이 굉장히 중요하다.
라그랑주 승수법
- 비선형계획법에서 쓰는 알고리즘
- 편미분을 이용한다.
- 목적함수와 제약조건을 적는다.
\begin{align*}
\min~~ &~f(x)\\
\text{s.t. } &~g(x) = 0\\
\end{align*}
- 목적함수와 제약조건을 이용해 새로운 방정식을 만든다.
L(\bold{x},~\lambda) =
f(\bold{x})-\lambda(g(\bold{x})-b)
- 방정식에 등장한 모든 변수로 편미분을 한다.
\frac{d}{d\bold{x}} L(\bold{x},~\lambda) =
\frac{d}{d\bold{x}}f(\bold{x}) -
\lambda~\frac{d}{d\bold{x}}g(\bold{x}) = 0
\\[10pt]
\frac{d}{d\bold{\lambda}}
L(\bold{x},~\lambda) =
- \{g(\bold{x}) - b\} = 0
- 조건에 맞게 정리 후 답을 구한다.
case 1 : 등호만 있을 때
\begin{align*}
\min~~&x^2 + y^2 \\
\text{s.t.}~~&x^2 + y^2 = 10\\
&x+2y=4
\end{align*}
L(x, y, \lambda_1, \lambda_2)
= x^2 + y^2
- \lambda_1(x^2 + y^2 - 10)
- \lambda_2(x+2y-4)\\[15pt]
\dfrac{\partial}{\partial x}L
= 2x-2x\lambda_1-\lambda_2 = 0
\\[10pt]
\dfrac{\partial}{\partial y}L
= 2y-2y\lambda_1-2\lambda_2 = 0
\\[10pt]
\dfrac{\partial}{\partial\lambda_1}L
= -(x^2 + y^2 - 10) = 0
\\[10pt]
\dfrac{\partial}{\partial\lambda_2}L
= -(x+2y-4) = 0
x = -2y+4를 이용. 다른 식들에 대입
\begin{align*}
&~2(4-2y)-2(4-2y)\lambda_1-\lambda_2\\
=~&~(8-4y)(1-\lambda_1)-\lambda_2\\
=~&~0
\end{align*}
\\[20pt]
y(1-\lambda_1)-\lambda_2 = 0
\\[30pt]
(1-\lambda_1)(8-4y) = 0 \\
(1-\lambda_1)(8-5y) = 0
지금까지 계산한 것을 가지고 정리하면 다음과 같이 나온다.
- \lambda_1 = 1, \lambda_2 = 0
- y = 8/5
- 2번 조건으로 계산했을 때, 조건에 아예 맞지 않다.
x = 4 - 2\cdot\frac{8}{5} =
\frac{4}{5} \\[10pt]
\bigg(\frac{4}{5}\bigg)^2 +
\bigg(\frac{8}{5}\bigg)^2 =
\frac{80}{25} \not = 10
- 1번 조건으로 계산했을 때가 최소값.
x^2 + y^2 = 10,~~~ x + 2y = 4.
(4-2y)^2 + y^2 = 10 \\
5y^2 - 16y + 6 = 0 \\[10pt]
y = \frac{8 \pm \sqrt{34}}{5}
\\[10pt]
x = 4 + \frac{16\pm2\sqrt{34}}{5}
case 2 : 부등호 1개
case 3 : 조건과 안 맞을 때
case 4: 부등호 여러 개
case 5: 부등호 많을 때
쿤-터거 조건(KKT)
개요
연립부등식인 경우
- 모든 변수의 미분값은 0이다.
- 모든 라그랑주 승수 값과 제한조건 부등식의 곱이 0이다.
- 라그랑주 승수는 음수가 아니어야 한다.
- stationarity
- primal constraints (원 제약조건)
- dual constraints (쌍대 제약조건)
- complementary slackness
예시
\begin{align*}
\min_{x, y}~~&x^2+y^2 \\
s.t.~~&x^2+y^2-5\le0 \\
~~&-x\le0 \\
~~&-y\le0 \\
~~&x+2y-4=0
\end{align*}
우선 함수방정식 L을 만든다.
1. stationarity
\dfrac{\partial L}{\partial x}
= 2x + 2x\mu_1 - \mu_2 + \lambda
\\[15pt]
\dfrac{\partial L}{\partial y}
= 2y + 2y\mu_1 - \mu_3 + 2\lambda
2. primal constraints
3. dual constraints
4. complementary slackness