[최적화] (11) solving dual problem with KKT

그럼 Regularity condition이 충족되었다는 가정하에 inequality constraint가 주어진 primal problem을 duality를 활용하여 풀어보자. 이 때 KKT가 활용된다. 

우선 del_x L=0으로 L을 최소화하는 x*를 찾고, del_λ,μ q(λ,μ)=0으로 q를 극대화하는 λ,μ값을 찾는다.

후술하겠지만 간단히 얘기하자면 Lagrangian fn이 x,λ,μ의 함수이기 때문에 del_x L=0의 x*는 x(λ,μ)의 형태로 나오는데, 이 λ,μ를 del_λ,μ q(λ,μ)를 통해 찾아 optimal solution인 x*를 찾아낸다는 얘기다. 

 

자 그럼 처음보는 q(λ,μ), Lagrangian dual problem을 정의해보자.

q(λ,μ) = min(L(x,λ,μ))이다. 우리는 여지껏 aL/ax=0 방법을 통해 f(x)를 최소화했는데, 이 dual problem의 q(λ,μ)는 Lagrangian fn 자체값을 최소화한다. given λ,μ을 q fn의 인자로 대입할 경우 L(x,λ,μ)는 최소화된다. 

잘 생각해보면 aL/ax=0을 통해 구한 primal optimal sol x*은 f(x)를 constraint를 충족시키면서 최소화한다. primal optimal value f(x*)는 f(x*)+λh(x*)+μg(x*)보다 클 수 밖에 없다. h(x*)=0, mu*g=0이기 때문이다. 

반대편으로 넘어와서 q(λ,μ)는 L(x,λ,μ) 전체를 minimize한 값이기 때문에 f(x)만을 minimize한 f*보다 작거나 같은 값을 가진다. 따라서 q(λ,μ) <= f* (for all μ>=0, λ)으로 정리된다. 

그런데 모든 λ,μ값에 대해 q<=f*이니 minimize된 Lagrangian값들 중 가장 극대화된 값인 q* 마저도 f*보다 작을 것이다. 따라서 이를 q*<=f*라고 쓰고 weak duality라 부른다. 

 

q*=f*가 성립되면 이는 strong duality를 충족하는 경우다. 일전에 살펴봤듯이 regularity condition SC가 충족되면 strong duality가 충족된다. q*<f*인 경우도 있는데 둘간의 간극을 duality gap이라 부른다. 

 

정리하자면 다음과 같다. 

primal feasiblity(KKT의 4,5번 조건)을 만족하는 x와 dual feasibility(3번조건)을 만족하는 mu, 그리고 lambda 즉 다시 말해 feasibility set 중에서 q(λ,μ) = f(x)가 만족되면 optimal solution이다. 

샌드위치 정리에 의해 양 극단의 q와 f가 같다면 q*=f*인 것이고, 이는 strong duality를 충족하기 때문에 optimal solution이 된다. 이 때 optimal solution λ,μ로 도출된 값 q*을 dual optimal, x로 도출된 값 f*을 primal optimal이라 부른다. 우리는 primal optimal을 구하기 힘들어서 이를 dual problem으로 변환한뒤 dual optimal을 구함으로서 optimal solution을 구한다.

 

처음부터 다시 정리.

del_x L =0으로 L을 최소화하는 x를 찾는 과정은 lagrangian dual fn을 구하기 위함이다. 

del_λ,μ q = 0으로 q를 극대화하는 λ,μ를 찾는 과정은 dual optimal을 구하기 위함이다.  

앞서 언급했듯이 x를 구하면 x(λ,μ)의 형태로 도출되기 때문에 λ,μ를 구하여 이를 다시 x에 대입하는 형식으로 문제를 풀 수 있다. 

 

풀이방식을 단계별로 풀어쓴 것이다. 아래 예시를 통해 자세히 살펴보자. 

 

1단계) del_x L=0으로 L을 최소화하는 x를 찾는다. 이 때 인자가 두개이므로 편미분을 두번해줌으로서 λ,μ을 인자로 포함한 x1, x2식을 찾는다.

2단계) 기존의 min(x1+x2+μ(x1^2+x2^2-1))의 형태로 표현되었던 q(λ,μ)에 (x1+x2+μ(x1^2+x2^2-1))을 최소화해주는 x1, x2식을 대입한다. 이는 1단계에서 얻은 식이다.

3단계) q(λ,μ)가 λ,μ의 식으로 전개되었으니 q를 극대화해주는 λ,μ를 찾는다. 이경우 aq/aμ = 0 을 만족하는 μ는 +-1/sqrt(2)인데 mu>=0이니 양수만 취한다. 

4단계) 얻은 λ,μ값을 1단계에서 얻은 x식에 대입하면 primal optimal solution을 해결할 수 있다.