05. Constrained Optimization

Constrained Optimization

General Constrained Optimization

$$\begin{array}{rlrl}& \text{minimize}& & f(x)\\ & \text{subject to}& & g_i(x)\le 0,i=1,\dots ,l\\ & & & h_j(x)=0,j=1,\dots ,m\end{array}$$

• $f$ : objective function.

• $g_i$ : inequality constraints.

• $h_j$ : equality constraints.

• 제약 조건을 만족하는 $x$의 집합을 feasible set 이라고 한다.

• 점 $x$에 대해 $A(x)=\{i:g_i(x)=0\}\cup \{j:h_j(x)=0\}$을 active set 이라고 한다.

• 주어진 점 $x^{\ast }$과 active set $A(x^{\ast })$에 대해, $\{\nabla g_i(x^{\ast }),i\in A(x^{\ast })\}$이 linearly independent이면, LICQ (Linearly Independence Constraint Qualification)가 성립한다고 말한다.

LICQ 성립 시, active constraint의 gradient는 0이 될 수 없다.

• The problem can be rewrite as:

$$\begin{array}{rlrl}& \text{minimize}& & f(x)\\ & \text{subject to}& & \mathbf{g}(x)\le 0\\ & & & \mathbf{h}(x)=0\end{array}$$

• 주어진 문제의 Lagrangian 은 다음과 같이 정의된다.

$$\begin{array}{rl}L(x,\nu )& =f(x)+\sum _{i=1}^l{\lambda }_i{g}_i(x)+\sum _{j=1}^m{\nu }_j{h}_j(x)\\ & =f(x)+{\lambda }^T\mathbf{g}(x)+{\nu }^T\mathbf{h}(x)\end{array}$$

Karush-Kuhn-Tucker (KKT) Conditions

Motivation for the KKT Conditions

하나의 inequality constraint를 가진 optimization problem을 고려하자.

$$\begin{array}{rlrl}& \text{minimize}& & f(x)\\ & \text{subject to}& & g(x)\le 0\end{array}$$

이는 다음과 같이 표현될 수 있다.

$$\begin{array}{rl}\text{minimize}{f}_{\infty -step}(x)& :=\{\begin{array}{ll}f(x)& \text{if }g(x)\le 0\\ 0& \text{if }g(x)>0\end{array}\\ & =f(x)+\infty \cdot 1_{g(x)>0}\end{array}$$

이 때, $f_{\infty -step}=\underset{\lambda \ge 0}{\max }$ $L(x,\lambda )$ where $L(x,\lambda )=f(x)+\lambda g(x)$.

따라서, 해당 optimization problem은 다음과 같이 새롭게 표현될 수 있다:

$$\underset{x}{\min }\underset{\lambda \ge 0}{\max }L(x,\lambda ):=f(x)+\lambda g(x)$$

KKT Conditions

Theorem: First-Order Necessary Conditions (KKT conditions) Suppose that $x^{\ast }$ is a local solution of constrained optimization problem and the LICQ holds at $x^{\ast }$.

$$\begin{array}{rlrl}& \text{minimize}& & f(x)\\ & \text{subject to}& & g_i(x)\le 0,i=1,\dots ,l\\ & & & h_j(x)=0,j=1,\dots ,m\end{array}$$

Then there is a Lagrangian multiplier vector $({\lambda }^{\ast },{\nu }^{\ast })$, such that the following KKT conditions are satisfied at $(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })$:

$$\begin{array}{rl}& \text{(1)}{\nabla }_{x}L(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })={\nabla }_{x}f(x^{\ast })+\sum _{i=1}^l{\lambda }_i^{\ast }{\nabla }_x{g}_i(x^{\ast })+\sum _{j=1}^m{\nu }_j^{\ast }{\nabla }_x{h}_j(x^{\ast })=0\\ & \text{(2)}{g}_i(x^{\ast })\le 0,\forall i\\ & \text{(3)}{h}_j(x^{\ast })=0,\forall j\\ & \text{(4)}{\lambda }_i^{\ast }\ge 0,\forall i\\ & \text{(5)}{\lambda }_i^{\ast }{g}_i(x^{\ast })=0,\forall i\end{array}$$

각 조건은 다음과 같이 불린다.

• (1): Stationarity 조건
• (2), (3): Primal feasibility 조건
• (4): Dual feasibility 조건
• (5): Complementary slackness 조건

Lagrangian Duality

Primal and Dual Problem

• Primal problem

$$\begin{array}{rlrl}& \text{minimize}& & f(x)\\ & \text{subject to}& & g_i(x)\le 0,i=1,\dots ,l\\ & & & h_j(x)=0,j=1,\dots ,m\end{array}$$

or

$$\underset{x}{\min }\underset{\lambda \ge 0,\nu }{\max }L(x,\lambda ,\nu ):=f(x)+{\lambda }^{T}g(x)+{\nu }^{T}h(x)$$

• Lagrangian Dual problem

$$\underset{\lambda \ge 0,\nu }{\max }D(\lambda ,\nu ):=\underset{x}{\min }L(x,\lambda ,\nu )$$

Duality Theorem

Weak Duality

Dual problem의 optimal value는 primal problem의 optimal value의 lower bound이다.

Theorem: Weak Duality Let $x$ and $(\lambda ,\nu )$ be a feasible solution to primal and dual problems, respectively. Then $f(x)\ge D(\lambda ,\nu )$. Moreover, if $f(x^{\ast })=D({\lambda }^{\ast },{\nu }^{\ast })$, then $x^{\ast }$ and $({\lambda }^{\ast },{\nu }^{\ast })$ solves the primal and dual problems, respectively.

• Duality gap: $f(x^{\ast })-D({\lambda }^{\ast },{\nu }^{\ast })$

Strong Duality

Convex optimization problem의 경우, dual problem과 primal problem의 optimal value는 같다.

Theorem: Strong Duality Let $f,g_i$ be convex and $h_j$ be affine for all $i,j$. Then $f(x^{\ast })=D({\lambda }^{\ast },{\nu }^{\ast })$ if the optimal value is finite.

• Affine functions $f(x_1,...,x_n)=A_1{x}_1+...+A_n{x}_n+b$ 형태의 function.

Wolfe Duality

Strong Duality를 이용하면 주어진 optimization 문제를 다르게 표현할 수 있다.

Theorem: Wolfe Duality Let $f,g_i$ be convex, $h_j$ be affine for all $i,j$, and $x^{\ast }$ be an optimal solution of the primal. Then $(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })$ at which LICQ holds solves the Wolfe dual problem of the form

$$\begin{array}{rlrl}& \text{minimize}& & L(x,\lambda ,\nu )\\ & \text{subject to}& & {\nabla }_{x}L(x,\lambda ,\nu )=0\\ & & & \lambda \ge 0\end{array}$$

${\nabla }_{x}L(x,\lambda ,\nu )=0$는 $L(x,\lambda ,\nu )$의 local optima에 대한 조건이다.

Linear and Quadratic Programming

Linear Programming (LP)

$$\begin{array}{rlrl}& \text{minimize}& & c^{T}x\\ & \text{subject to}& & Ax=b\\ & & & x\ge 0\end{array}$$

• Lagrangian dual $L(x,\lambda ,\nu )=c^{T}x-{\lambda }^{T}x+{\nu }^T(b-Ax)$은 convex이다.
• 따라서, $c-\lambda -A^T\nu =0$ and $\lambda \ge 0$ 일 때, minimum을 얻는다.
  • Check that $c-\lambda -A^T\nu =0$ and $\lambda \ge 0$ $⟺$ $A^T\nu \le c$.
• 그 결과, dual problem은 다음과 같다.

$$\begin{array}{rlrl}& \text{maximize}& & b^T\nu \\ & \text{subject to}& & A^T\nu \le c\end{array}$$

Quadratic Programming (QP)

$$\begin{array}{rlrl}& \text{minimize}& & \frac{1}{2}{x}^{T}Hx+d^{T}x\\ & \text{subject to}& & Ax\le b\end{array}$$

where $H$ is symmetric and positive semidefinite. (따라서, objective function은 convex이다.)

• Lagrangian dual $L(x,\lambda )=\frac{1}{2}{x}^{T}Hx+d^{T}x+{\lambda }^T(Ax-b)$은 convex이다.
• 따라서, $Hx+A^T\lambda +d=0$ or $x=-H^{-1}(d+A^T\lambda )$ 일 때, minimum을 얻는다.
• 그 결과, dual problem은 다음과 같다.

$$\begin{array}{rlrl}& \text{maximize}& & \frac{1}{2}{\lambda }^{T}D\lambda +{\lambda }^{T}c-\frac{1}{2}{d}^T{H}^{-1}d\\ & \text{subject to}& & \lambda \ge 0\end{array}$$

where $D=-A{H}^{-1}A$ and $c=-b-A{H}^{-1}d$.

이 dual problem은 단순히 nonnegative domain에서의 concave quadratic function maximization 문제이기에, 상대적으로 쉽게 풀 수 있다.