KKT Optimality Conditions

2011 Dec. written by 이주형 (Lee Ju Hyung)

구속이 없는 경우의 다변수 함수 f 의 최적화 조건은 아래와 같다.

    \[\nabla f(x^*) = 0\]

이를 확장하여 구속이 있는 경우의 일반적인 최적화 조건을 알아보자.

Lagrange Multipliers

우선 등식 뿐인 구속조건 최적화 문제는 다음과 같다.

    \[\mathrm{minimize} \; f(x)\]

    \[\mathrm{s.t.} \quad g_i(x) = 0 \quad i \in \{1, \dots, m\}\]

이러한 구속 조건하에서 목적 함수 f 의 최적값이 c 라고 가정하자. 이때 f = c 에 수직인 \nabla fg_i = 0 에 수직인 \nabla g_i 는 아래와 같은 관계에 있다.

    \[\nabla f = \sum_{i=1}^m \lambda_i \nabla g_i\]

여기서 \lambda_i 를 [Lagrange multipliers](http://en.wikipedia.org/wiki/Lagrange_multiplier) 라고 부른다.

위의 식을 변형해서 Lagrange 함수를 만든다.

    \[L(x, \lambda) = f(x) - \sum_{i=1}^m \lambda_i g_i(x)\]

결과적으로 등식 구속조건의 목적함수 최적화 문제는 구속조건이 없는 Lagrange 함수 최적화 문제로 바뀐다.

Fritz-John 조건

등식과 부등식 구속조건이 포함되는 최적화 문제는 다음과 같다.

    \[\mathrm{minimize} \; f(x)\]

    \[\mathrm{s.t.} \quad g_i(x) \le 0 \quad i \in \{1, \dots, m\}\]

    \[h_j(x) = 0 \quad j \in \{1, \dots, l\}\]

f, g_i, h_j 가 임의의 함수일 때, 최적해를 가질 필요 조건을 Fritz-John 조건이라고 하고, 종류 별로 다음과 같이 나타낸다.

Stationarity:

    \[\xi_0 \nabla f(x^*) + \sum_{i=1}^m \xi_i \nabla g_i(x^*) + \sum_{j=1}^l \eta_j \nabla h_j(x^*) = 0\]

Primal feasibility:

    \[\begin{aligned} g_i(x^*) \le 0 \\ h_j(x^*) = 0 \end{aligned}\]

Dual feasibility:

    \[\xi_i \ge 0\]

Complementary slackness:

    \[\xi_i g_i(x^*) = 0\]

KKT 조건

Fritz-John 조건에서 \xi_0 = 0 인 경우는 최적화 조건이 목적함수에 의존하지 않는다는 것으로 특수한 경우이다. 많은 실용적인 경우에 있어서 \xi_0 = 1 로 잡을 수 있다. (0 이 아니므로 \xi_0 으로 나누면 된다)

Stationarity:

    \[\nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0\]

Primal feasibility:

    \[\begin{aligned} g_i(x^*) \le 0 \\ h_j(x^*) = 0 \end{aligned}\]

Dual feasibility:

    \[\lambda_i \ge 0\]

Complementary slackness:

    \[\lambda_i g_i(x^*) = 0\]

이것을 KKT (Karush–Kuhn–Tucker) 조건이라고 한다. 또한 \lambda_i, \nu_j 를 KKT multipliers 라고 한다.

KKT 조건이 최적해를 가지기 위한 필요 충분 조건이 되기 위해서는 f, g 가 미분 가능한 convex 함수이고, h 는 affine 함수이어야 한다.

쌍대 이론 (Duality Theory)

아래와 같은 선형 구속 조건이 있다고 하자.

(1)   \[ Ax \le b, x \ge 0\]

여기서 A \in \mathbb{R}^{m \times n} 이고 x \in \mathbb{R}^n, b \in \mathbb{R}^m 이다. (첫번째 m 개의 부등식을 inequality constraints, 두번째 n 개의 부등식을 non-negative constraints 라고 구분지어 말한다) 이 구속 조건하에 c \cdot x 가 최대값 (또는 최소값) 이 되도록하는 해 x 를 구하는 문제를 LPP (Linear Programming Problem) 라고 한다.

기하학적으로 나타내면 구속 조건하의 half-space 들의 교집합 (convex set) 을 c 방향으로의 \mathbb{R}^n 평면이 최대 (또는 최소) 거리를 갖게 하는 해를 구하는 문제가 된다. 이때 여유변수 (slack variables) 를 추가하여 non-negative constraints 만 남기고 부등식 구속 조건을 등식으로 바꾸어 나타낼 수 있다.1

    \[\begin{aligned} Ax + s &= b \\ \begin{bmatrix} A & I \end{bmatrix} \begin{bmatrix} x \\ s \end{bmatrix} &= b \end{aligned}\]

    \[x \ge 0, s \ge 0\]

위의 해는 \mathbb{R}^{n+m} 초평면의 교집합을 나타낸다. (단 각 성분은 0 이상)

한편 모든 LP 문제는 그에 대응하는 쌍대문제를 갖는데, 원 문제를 primal problem 이라고 하고, 쌍대 문제를 dual problem 이라고 한다. primal problem 이 최대화 문제였다면 쌍대 문제는 최소화 문제가 된다. 수식으로 나타내면 b \cdot y 의 최소값을 구하는 문제가 되며, 아래와 같은 구속 조건을 가진다.

(2)   \[ y^T A \ge c^T, y \ge 0\]

여기서 y \in \mathbb{R}^m, c \in \mathbb{R}^n. 여유변수를 추가하면,

    \[\begin{aligned} A^T y + u &= c \\ \begin{bmatrix} A^T & I \end{bmatrix} \begin{bmatrix} y \\ u \end{bmatrix} &= c \end{aligned}\]

    \[y \ge 0, u \ge 0\]

(1), (2) 에서 각각 y^Tx 를 곱하면,

    \[y \cdot b \ge y^T Ax \ge c \cdot x\]

이것은,

    \[y \cdot b \ge c \cdot x\]

가 된다. 이것은 primal problem 의 최적해가 dual problem 의 최적해보다 작거나 같다는 것을 의미한다. (약한 쌍대성의 원칙) 특히 primal problemdual problem 이 모두 최적값을 가진다면 y \cdot b = c \cdot x 이다. (강한 쌍대성의 원칙)

일반 쌍대 이론으로부터 KKT 조건을 유도

등식과 부등식 구속조건을 포함하는 primal problemdual problem 은 다음과 같이 나타낼 수 있다.

    \[\mathrm{minimize} \; f(x)\]

    \[\mathrm{s.t.} \quad g(x) \le 0 \quad i \in \{1, \dots, m\}\]

    \[h_j(x) = 0 \quad j \in \{1, \dots, l\}\]

,

    \[\mathrm{maximize} \; p(\lambda, \nu)\]

    \[\mathrm{s.t.} \quad \lambda_i \ge 0 \quad i \in \{1, \dots, m\}\]

여기서,

    \[p(\lambda, \nu) := \inf_{x \in \mathbb{R}^n} L(x, \lambda, \nu)\]

여기서,

    \[L(x, \lambda, \nu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^l \nu_j h_j(x)\]

L 의 하한 (infimum) 인 p 를 구하기 위해 x 로 편미분해 나타내면,

(3)   \[ \nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0\]

최적값이 존재할 때 primal problem 의 최적값은 dual problem 의 최적값과 같기 때문에 f(x^*) = p(\lambda^*, \nu^*) 이 성립한다.

    \[\begin{aligned} f(x^*) &= p(\lambda^*, \nu^*) \\ &= \inf_{x \in \mathbb{R}^n} L(x, \lambda^*, \nu^*) \\ &\le L(x^*, \lambda^*, \nu^*) \\ &= f(x^*) + \sum {\lambda_i}^* g_i(x^*) + \sum {\nu_j}^* h_j(x^*) \\ \end{aligned}\]

위의 식을 살펴보면,

(4)   \[ \sum {\lambda_i}^* g_i(x^*) = 0\]

이라는 것을 알 수 있다.

결과적으로 primal problemdual problem 의 구속 조건식과 식 (3), (4) 로부터 KKT 조건이 모두 유도됨을 알 수 있다.

References

  1. Game Physics 2nd Edition
    David H. Eberly
    http://www.amazon.com/Game-Physics-Second-David-Eberly/dp/0123749034
  1. 이렇게 나타낸 형식을 Linear Programming Problem 의 normal form 이라고 한다.

Leave a Reply

Your email address will not be published. Required fields are marked *