KKT & Inequality Constraint

KKT & Inequality Constraint

KKT condition은 Convex Optimization의 꽃. KKT 조건이란 제약조건이 없는 상황에서 f(x)의 local minimum의 필요조건이 f’(x)=0인 것 처럼, 제약조건이 있는 상황에서의 필요조건이다.

KKT가 중요한 이유는 Convex 문제에서 KKT를 만족하는 x, mu, lambda를 찾기만 하면, x는 optimal solution이 된다. (충분조건이 된다.)

• Optimization with Equality Condition에서의 필요조건

  $\min f(\boldsymbol{x}) \\ s.t \ \ \ h(\boldsymbol{x})=0$

  → $L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x})+ \boldsymbol{\lambda}^{T}h(\boldsymbol{x})$

  • local minimum의 필요조건
    1. $\nabla f(\boldsymbol{x}^{*}) + \boldsymbol{\lambda}^{T} \nabla h(\boldsymbol{x}^{*})= 0$
    2. $h(\boldsymbol{x}^{*}) = 0$

    을 만족하는 람다가 존재.

• Optimization with Inequality & Equality Condition에서의 필요조건은 아래와 같다.

  제약조건 함수과 목적함수들이 연속적으로 미분이 가능하고, 아래 KKT 조건을 만족하는 뮤와 람다가 존재할 경우, x*는 극소이다.

  

  ref. https://www.stat.cmu.edu/~ryantibs/convexopt-F16/scribes/kkt-scribed.pdf

  • Matrix Representation

    

    

    

    • Stationarity를 기하학적으로 확인

      g의 gradient와 f라는 gradient의 방향만 고려해서 생각해보자.

      f’(x*)와 mg(x*)를 넘기면 m은 dual feasibility에 의해 양수여야 하므로 반대방향이다.

      f’(x*)와 수직인 어떤 u벡터에 대해 위쪽 영역은 각이 90도 미만이니까(cosine이니까) 내적하면 양수이고, 아래 빨간색 영역은 음수인 영역이고 이는 f를 줄이는 영역이다. 똑같이 g를 줄이는 영역을 생각할 수 있다. 완전하게 반대 방향일 때, f를 줄이며, g를 보다 잘 만족하는 영역이 없어지게 된다.

      

      여기서 f를 대신에 equality constratint의 Lagrangian 함수라고 바꿔, 생각하면 함수 f,g,h를 모두 고려한 stationarity 조건의 기하학적 해석으로 볼 수 있다.

      

    • Complementary slackness

      

      

      g≤0의 영역을 위와 같다고 하면, 위 조건을 만족하기 위해 2가지 경우를 생각할 수 있다.

      경계에 local minimum이 있는 경우에는 g(x*)=0이기 때문에 바로 만족이 된다.

      경계에 있지 않은 경우에는 mu가 0이어야만 한다. 내부에 어떤 점이 local minimum인 경우에는 local minimum이고, 이미 g(x) ≤ 0 을 만족하기 때문에 (equality constraint만 있기 때문에) $\nabla f + \lambda\nabla h = 0$이 만족이 되어야한다. stationarity 조건을 만족해야하기 위해서, mu를 0으로 잡아주면 된다.

      

    • Regularity condition(constraint qualification)

      KKT의 조건이 constrained 최적화 문제의 필요조건이기 위한 조건. (Ref. 위키피디아)

      아래 중 하나만 만족하면 Regularity condition을 만족하며 LICQ를 가장 보편적으로 사용

      

      • LCQ: g, h는 affine function
      • LICQ: active inequality란, 부등식 제약조건에서 g(x*) = 0 인 경우를 active 라고 한다.

        (g(x*) <0은 in active이다.) 부등식을 등식으로 바꿀 때의 gradient와 등식제약조건이 x*에서 linearly independent해야 함.

        LICQ를 만족하면, MFCF 만족 → CPLD → QNCQ

        LICQ를 만족하면, CRCQ 만족 → CPLD → QNCQ

      • SC(Slater’s condition)

        convex 문제에서 등식 제약 조건 hi 대해 $h_{i}(x) = 0$ 이고

        affine 함수인 gi에 대해 $g_{i}(x) \le 0$ 이고

        affine 함수가 아닌 gj에 대해 $g_{j} <0$

        을 만족하는 점 x가 존재하면 regularity를 만족한다.

        → Slater’s condition는 strong duality에 대한 충분 조건이다.

• Inequality 제약이 있는 최적화 문제를 Duality problem으로 풀기

  equality 제약이 있을 때, 크게 필요조건으로 푸는 방법과 duality problem으로 푸는 방법이 있었다.

  KKT조건(필요조건)으로 푸는 방법은 라그랑지안 함수의 미분해서 0이 x, 람다, 뮤을 구하고 feasibility를 확인하고, 어떤 x가 가장 작은지 확인해야 하는 번거로움이 있다.

  알고리즘으로 접근하는 Interior point method라는 방법이 편하긴 하다.

  • Primal Problem & Primal Optimal

    아래와 같은 문제를 Primal Problem이라 하며, 이 때의 optimal solution x*를 primal optimal (point)이라 한다.

    

  • Duality 이용하는 방법

    

    $\mu \ge 0$, 에서

    $\nabla_{x}L = 0$을 이용해 $arg\min_{x} L$을 찾은 Lagrangian Dual Function q(x)로

    $\nabla_{\mu, \lambda} q(\mu, \lambda) = 0$을 통해 $arg\max_{\mu,\lambda}$ q를 찾는 방법이 duality를 활용해 푸는 방법이다.

    • Lagrangian Dual Function, $q(\mu, \lambda)$

      $\begin{matrix} q(\mu, \lambda) &\triangleq& \min_{x} f(x) + \lambda h(x) + \mu g(x) \\&\le& f(x^{*}) + \lambda h(x^{*}) + \mu g(x^{*})\\&\le& f(x^{*}) \end{matrix}$

      라그랑지안 듀얼 함수는 위와 같이 정의하며, 아래 2가지 특징이 있다.

      1. $f(x^{*}) + \lambda h(x^{*}) + \mu g(x^{*})$보다 작은 이유는 primal optimal은 gi(x)≤ 0, h(x)=0이라는 제약조건 아래에 구했기 때문에, 제약조건을 고려하지 않고 라그랑지안 함수를 최적화 한것은 더 작다.
      2. $\lambda h(x^{*}) + \mu g(x^{*})$에서 제약조건에 의해, h(x*)=0이고, mu ≥ 0 g(x*)는 음수이기 때문에 $q(\mu, \lambda)$는 f(x*)보다 작다.
    • Primal Optimal Value, f*

      $f(x^{*})$, f에 primal optimal (point)의 결과. f*로도 표현

    • Dual Optimal Value, q*

      라그랑지안 듀얼함수의 최댓값 $\max_{\mu \ge 0\ , \lambda } q(\mu^{*}, \lambda^{*} )$. q*로도 표현

      그랑지안의 b번 특성인 모든 $\mu \ge 0\ , \lambda$ 에 대해 $q(\mu, \lambda) \le f(x^{*})$가 만족하니 아래와 같이 생각할 수 있다.

      $q(\mu, \lambda) \le \max_{\mu \ge 0\ , \lambda } q(\mu^{*}, \lambda^{*} ) \le f(x^{*})$

      

    • Lagrangian Dual Problem (Dual Problem)

      $\max_{\mu \ge 0\ , \lambda } q(\mu, \lambda) \\ \ \ s.t \ \ \ \ \mu \ge 0$

    • Weak Duality: q* ≤ f*

      Strong Duality: q* = f*

      Duality gap: f* - q*

    → 결론적으로 Dual Problem으로 푸는 것이 primal problem을 푸는 것보다 간단하므로

    $q(\mu, \lambda) = f(x)$를 만족하는 $\mu^{*}, \lambda^{*}, x^{*}$를 찾는 다면 그것이 optimal solution이 된다.

    $q(\mu, \lambda) = f(x)$를 만족하는 해가 없더라도, Duality Gap이 가장 작은 best lower bound이다.

• References

  https://www.youtube.com/watch?v=xd641yJvXTk&list=PL_iJu012NOxeMJ5TPPW1JZKec7rhjKXUy&index=14