Local Minimum, Local Maximum

그림 및 예제들은 KMOOC 수업자료에서 가져왔습니다.

local minima, local minimum, global minima, global maximum

Satationary Point

단변수 함수 f(x)에서의 점 x0의 미분값이 0이라면 그 점을 stationary point, 정상점이라 정의합니다.

정상점이 주어졌을 때,

1. 2차 미분값이 양의 값을 가지면 국부 최소해가 됩니다.

2. 2차 미분값이 음의 값을 가지면 국부 최대해가 됩니다.

3. Hessian 행렬이 positive definite(convex)일 경우, 국소 최솟값이 됩니다.

4. Hessian 행렬이 negative definite(concave)일 경우, 국소 최댓값이 됩니다.

그림을 보면 Local minimum과 Local maximum을 정상점 및 2차미분값을 통해 알 수 있습니다. 

하지만 가운데 점은 최솟값인지 최댓값인지 구분하기가 어렵습니다. 

이를 안정점(saddle point)라고 부릅니다.

안정점이란, convex도 concave도 아닌 정상점을 뜻합니다.

여기서 알 수 있는 것은, 어떤 정상점에서 2차미분값이 0이거나 Hessian행렬이 영행렬일 경우에는 안장점 일수도 있고, 아닐 수도 있습니다.

(예시 확인)

binding & active

어떤 제약식이 있습니다. 그 제약식에 x0를 넣었더니 등식이 만족한다.(좌/우변이 같다)

이를 x0의 입장에서 제약식을 속박(binding)한다라고 표현합니다.

또한, 제약식의 입장에서는 x0의 지점에서 active(활성화) 또는 속박적이 된다고 표현하게 됩니다.

잠시! 우리가 convex와 concave를 따져가며 문제를 푸는 이유는 여러 가지가 있지만!

일반적으로 비선형 계획법은 두 가지 이유때문에 해를 구하기가 쉽지 않습니다.

1. convex, concave가 아닐경우

2. 실현가능한 해집합이 볼록집합이 아닐경우

하지만 위의 두 이유는 식의 특성만 잘 찾는다면 바로 풀리는 문제들입니다. 당연히 수학을 조금만 알아도 왜 우리가 convex와 concave가 

좋은지를 알 수 있습니다.

Lagrangian Function (Simple)

라그랑지안 승수법을 간단히만 설명하고 넘어가겠습니다. 다음 사진을 보시면 쉽게 이해가 가실 것입니다.

말 그대로 패널티를 주고싶다는 것입니다. 사실 panalty term의 b-g(x)는 제약식에 해당합니다.

하지만 우리가 가진 목적식이 이 제약식을 만족할 수 없다는 것이죠. 하지만 문제는 풀어야하고....

그 방법으로 제약식을 목적식으로 옮겨주는 것입니다. 

즉 제약선형계획법을 비제약선형계획법으로 변형하겠다는 것이지요.

목적식으로 옮겨서 제약을 없애는 대신에 패널티 값을 주게 됩니다. 

위의 예시는 최대화 문제이며 b-g(x)가 음의 값을 가지므로

패널티 변수인 람다가 0보다 크거나 같은 숫자를 가지게 되겟죠?

이때, 람다를 '라그랑지안 승수' 라고 부릅니다. 

라그랑지안 승수는 식변형에도 많이 사용하게 됩니다 ^^

KKT 조건(Karush-Kuhn-Tucker Conditions)

KKT에 대해서도 간단히 알아보고 넘어가도록 하겠습니다!

x0의 점이 KKT조건을 만족한다면

1. x0에 대한 라그랑지안 함수의 Gradient가 0이어야 합니다.

2. x0에서 라그랑지안 승수가 0이거나 제약식 b-g(x)가 0이어야 합니다. (쌍대이론에서의 상보여유정리와 비슷함)

3, 4. 실행 조건

그렇다면 KKT는 비선형계획법에서 어떤 의미를 가질까요??

어떠한 점 x0에서 KKT조건을 만족한다는 것은 x0이 최적해가 되기 위한 필수조건을 만족하였다는 의미입니다.

따라서, x0이 최적해가 되고싶다면 KKT조건을 전부 성립시켜야 한다는 말이죠.

그래서 KKT조건을 최적해의 필요조건이라고 합니다.

그 이유는 최적해가 아니지만 KKT를 만족하는 해가 있을수도 있기 떄문입니다. (필요충분조건이 안되는 이유)

하지만 convex거나 concave임이 이미 증명이 된 경우, 필요충분조건이 됩니다. 

어떤 x0의 지점에서 해를 찾았을 때, 여러분은 이미 그 해가 최소 local min 혹은 local max라는 것을 알기 떄문입니다. 

따라서 이때의 KKT조건은 여러분이 찾은 어떤 해의 최적성을 보장하는 충분조건이 되게 됩니다. (당연히 필수도 되겟죠?)

Reference

KMOOC