Constrained optimization

 

앞서 살펴보았던 unconstrained optimization은 목적함수를 최소화하는 방법으로 진행하였는데, constrained optimization은 모든 $x$에 대해서 $f(x)$를 찾는게 아니라 일정한 제약 하의 $x$에 대해서 함수값을 찾는 것이다.

 

 

 

아래의 그림처럼 일정 지정 안에서 minimum을 찾는 것이다.

 

 

 

 

 

indicator function을 사용해 contrained를 unconstrained로 바꾸어준다. (7.19)는 indicator function을 나타내고 여기서 $z$가 0보다 작거나 같으면 0이 되어서 식 (7.18)에서 $J$는 $f$와 같아져서 그 함수값을 최소화하면 되는 방향으로 가면 되는 것이고, $z$가 0보다 크면 목적함수 값이 무한대가 되어서 (7.18)을 최소화하는 것이 (7.17)과  같아짐을 알 수 있다.

 

 

 

 

 

 

직접 구하기는 힘들기 때문에 linear한 function으로 고쳐서 사용한다. 이를 Lagrange multiplier 라고 한다.

제약 조건에 람다가 붙은 것을 포함한 목적함수는 아래와 같다.

 

 

 

 

$J(x)$ 대신에 라그랑지안 함수를 최소화한다.

 

Lagrangian duality: 원래의 함수 최적화 문제를 다른 함수의 최적화 문제로 변환한다.

 => 풀기 어려운 문제가 있을 때 dual 문제로 접근하면 간단해지므로 변환을 하곤 한다.

 

 

 

 

예제를 살펴보자.

(7.17)과 동일한 제약조건이 있다고 할 때, 이를 primal problem이라고 하고 primal variables 는 $x$라 한다. 이 때 Lagrangian dual problem은 아래와 같다. 

 min하던 문제가 max하는 문제로 바뀌었고, $x$ 대신에 람다라는 dual variables로 바뀌었다.

 임의의 람다값에 대해서 $x$가 가장 작을 때의 지점에서의 Lagrangian 값이 $D(\lambda)$이고 Lagrangian  dualiry 라고 한다.

 

(7.17) -> (7.22) 를 기억하자. 그리고 minmize해야하는 목적함수도.

 

 

 

 

 

 

primal problem을 Lagrangian dual problem으로 푸는데 필요한 두가지 개념을 살펴볼 필요가 있다.

 

-minimax inequality

 한 사람은 동쪽방향으로 가장 낮은 지점을 탐색하면서 이동, 다른 한 사람은 북쪽방향으로 가장 높은 지점을 탐색하면서 이동, 각각 이동 경로중에서 동쪽방향으로 찾은 가장 높은 지점은 북쪽방향으로 찾았던 것중 가장 낮은 지점보다 항상 낮더라. 라고 직관적으로 이해.

 

-Weak duality

 Primal values는 dual values보다 크거나 같다. 제약 조건을 만족하면 람다가 0 크거나 같으면 되고, 제약조건을 만족하지 않으면 람다가 무한대로 가버리는. Langrange function이 J function과 동일시 되게 하니 계산이 간편해진다.

 

 

 

 

reference:https://github.com/mml-book

 

 

 

 

ㅇ