[Theory of Optimization] convexity and duality

1. Mathematical Optimization이란?

$\def\m#1{\mbox{#1}}$

$\def\t#1{\textbf{#1}}$

$\def\R{\mathbb{R}}$

최적화 문제(Optimization Problem) 혹은 Mathematical Programming Problem의 일반적 정의는 다음과 같다.

\[\ \mbox{For a function } f : A \rightarrow \mathbb{R} \mbox{ from some set A to the real numbers, } \\\ \mbox{Find an Element }\textbf{x}_0 \in A \mbox{ such that } f(\textbf{x}_0) \leq f(\textbf{x}) \mbox{ or }f(\textbf{x}_0) \geq f(\textbf{x}), \forall \textbf{x} \in A\]

Standard Form

\[\m{minimize } f(\textbf{x})\\ \mbox{ subject to } g_i(\textbf{x}) \leq 0 , i =1,2,...,m \\\ \ \qquad \qquad h_j(\textbf{x}) =0 ,j=1,2,...,n\]

이에 대해서 다음과 같은 implement가 있다.

• 함수 자체에 음수 곱하면 minimize 문제와 maximize 문제가 바뀌므로 최대화 문제와 최소화 문제는 대동소이하다.
• 여기서 A는 \(\R^n\)의 부분집합이며, 제약으로 한정될 수 있다.
• $f$는 목적함수(Objective Function), 비용함수(Cost), 손실함수(Loss), 효용함수(Utility), 적합함수(Fitness) 등 여러가지 명칭으로 불리지만, 이 또한 대동소이 하다.
• 이때의 해 \(\textbf{x}_0\)를 “An Optimal Solution”이라고 부른다.
• 근이 무한대로 발산할 시, infinity 혹은 undefined하다고 말한다.

아래는 local minimum의 정의이다. 적당히 알아두자.

Local Minimum

\[\ \textbf{x}' \mbox{ is local minimum } \\\ \iff \exists \delta >0 \mbox{ such that } \forall \textbf{x} \in A \mbox{ where } \parallel \textbf{x} - \textbf{x}' \parallel \leq \delta , f(\textbf{x}') \leq f(\textbf{x})\]

2. Convex Optimization 이란?

Optimization의 하위 분류에는 Integral Optimization, Quadratic Optimization, Stochastic Optimization 등 여러가지가 있지만, 가장 너른 범주를 커버하는 것은 Convex Optimization이다.

Convex Optimization

Convex Set 위의 Convex Function을 목적함수로 삼아 최적화 하는 문제

Convex Set의 정의는 아래와 같다.

Convex Set

\[\ A \mbox{ is convex set } \\\ \iff \forall x,y \in A ,\mbox{a line segment between x and y is in A}\]

line segment라 함은 두 끝점사이 직선을 구성하는 원소의 집합이라고 할 수 있다. 위의 정의가 의미하는 것은 집합 내부 모든 원소 쌍에 대해 두 원소를 이은 직선이 모두 Set 내부에 존재해야 함을 의미한다. 즉 그림으로 나타내면 아래와 같다.

좌측이 convex set이고 우측이 non-convex set이다. 간혹 non-convex set을 concave set이라고 부르기도 한다는데, 많은 수학자들이 지양하는 표현이라고 한다.

Convex function의 정의는 다음과 같다.

Convex Function

\[\ \mbox{For }f : X \rightarrow \R , f \mbox{ is convex function } \\\ \iff \forall \textbf{x}_1, \textbf{x}_2 \in X ,\mbox{a line segment between }\textbf{x}_1 \mbox{ and } \textbf{x}_2 \mbox{ lies above the graph }\]

-f가 Convex function일때 f는 Concave function이다.

• convex function의 epigraph는 convex set
• \[f(y) \geq f(x) + \nabla f(x)^t(y-x)\]
• \[\nabla f(x^*) =0 \iff x^* \m{ minimize } f\]
• \[\nabla^2 f(x) \geq 0\]
• \[f(E(x)) \leq E(f(X))\]

Convex Optimization의 특징

• \(\inf \{f(\textbf{x}) : \textbf{x} \in C)\}\) 인 \(\textbf{x} = \textbf{x}_0\)를 찾는 것이 Convex Optimization
• \(C\)는 feasible set (접근 가능한 집합)
• \(\textbf{x}_0\)의 집합을 an Optimal Point이라고 함
• \(f\)가 끝도 없이 최소화 되거나, infimum을 얻을 수 없다면, Optimization이 Unbounded하다고 이야기함

• \(C\)가 공집합일시 infeasible 하다고 이야기함

• 모든 local minimum이 global minimum이다.
• optimal set이 convex set이다.
• 목적함수가 strictly convex할 시 optimal point는 두개 이상 있을 수 없다.

이는 hilbert projection theorem에서 증명된 성질들이라고 한다.

convex optimization의 local minima가 존재하지 않음은 위 그림을 통해서 알 수 있다.

Convex Optimization의 종류

LP : Linear Programming

\[\mbox{Minimize } \textbf{c}^t \textbf{x} \\\\\mbox{ subject to }A \textbf{x} = \textbf{b} \\\ \qquad \qquad \ \ Ex \leq F\]

QP : Quadratic Programming

\[\mbox{Minimize } \textbf{x}^t Q \textbf{x} \\\\\mbox{ subject to }A \textbf{x} = \textbf{b} \\\ \qquad \qquad \ \ E\textbf{x} \leq \textbf{f}\]

SOCP : Second- Order Cone Programming

minimize $f^t x$ subject to \(\parallel A_i x +b_i\parallel _2 \leq c_i^t x + d_i\) and \(Fx=g\)

SDP : Semidefinite Programmming

\(\underset{x_1,x_2,...,x_n \in \R^n}{\min} \underset{i,j \in N}{\sum} c_{i,j} (x_i,x_j)\) subject to \(\underset{i,j \in N}{\sum} a_{i,j,k} (x_i,x_j) \leq b_k\)

CP : Conic Programming

아래는 Convex Optimization을 푸는 가장 대표적인 문제이다.

2-1.Lagrange Multipliers Methods

최적화 문제의 일반화 Form을 Lagrange Multipliers \(\t u , \t v\)를 도입하여 아래와 같이 표현할 수 있다.

\[\underset{\textbf{x}}{\min} f(\textbf{x})\\ \mbox{ subject to } g_i(\textbf{x}) \leq 0 , i =1,2,...,m \\\ \ \qquad \qquad h_j(\textbf{x}) =0 ,j=1,2,...,n\] \[L(\t x ,\t u, \t v) = f(\t x) + \sum u_i g_i(\t x) + \sum v_j h_j(\t x) \{\t u \geq 0\}\]

이때의 \(L(\t x, \t u, \t v)\)를 Lagrangean Function이라고 한다.

Lagrangean Function의 특수한 꼴은 Lagrange Multiplier Theorem을 이용해서 매우 쉽게 풀린다. Lagrange Multiplier Theorem는 부등호 제약없이 등호제약 하에서 Local Minima나 Maxima를 찾는 방법이다.

Lagrange Multiplier Theorem

\[f : \R^n \rightarrow \R \{\mbox{: objective function}\}, g:\R^n \rightarrow \R^c \{\mbox{: constraints function}\} \\\ \mbox{let }x^* \mbox{ is optimal solution of follow :} \\\ \begin{cases}\mbox{maximize }f(x) \\\ \mbox{subject to :}g(x)=0 \end{cases} \\\ \mbox{, then x* follows equition :} \\\ \{ \frac{\delta}{\delta x}f(x)\mid_{x=x^*} = \lambda \frac{\delta}{\delta x} g(x) \mid_{x=x^*} \}\]

3. Duality

Duality란 쌍대성으로 해석이 되며, 최적화 이론에서는 다음과 같은 정의를 가진다.

Duality

Principle that Optimization Problems may viewed from either of two perspectives, the Primal Problem or the Dual Problem.

최적화 문제는 원초문제와 쌍대문제, 두 가지 관점으로 해석될 수 있다는 원칙

가장 기본적인 Linear Programming 문제를 살펴보자.

\[\mbox{Minimize } \textbf{c}^t \textbf{x} \\\\\mbox{ subject to }A \textbf{x} = \textbf{b} \\\ \qquad \qquad \ \ E\textbf{x} \leq \t f\]

제약식의 양변에 \(\textbf{u},\textbf{v}\)라는 새로운 벡터를 곱해보자, 여기서 부등식에 곱하는 벡터는 모두 양수로 설정을 해서 부등호가 바뀌지 않도록 해주자.

\[\textbf{u}^t A \textbf{x} = \t u^t \t b , \t v^t E \t x \leq \t v^t \t f\] \[\t u ^t A \t x + \t v ^t E \t x \leq \t u^t \t b + \t v^t \t f \\\ (\t u ^t A + \t v^t E) \t x \leq \t u^t \t b + \t v^t \t f \\\ (-A^t \t u - E^t \t v)^t \t x \geq -\t u^t \t b - \t v^t \t f \\\ \therefore \t c^t \t x \geq -\t u^t \t b - \t v^t \t f\]

여기서 우리는 \(c^t \textbf{x}\)의 lower bound \(-\t u^t \t b - \t v^t \t f\)를 찾을 수 있다.

따라서 lower bound를 최대화 시키는 \(\t u , \t v\)를 찾음으로써, \(c^t \t x\)를 간접적으로 찾을 수 있다. 정리하면 위의 문제는 아래의 문제 꼴로 변형시킬 수 있다.

\[\m{Maximize } -\t u^t \t b -\t v^t \t f \\\ \m{subject to } -A^t \t u - E^t \t v = \t c \\\ \qquad \qquad \quad \t v \geq 0\]

위의 원본 폼을 Primal Problem(원초 문제)이라고 한다면 아래 폼을 Dual Problem(쌍대 문제)이라고 한다.

물론, 쌍대문제에서 최대화 시킨 값이 원초 문제에서 최소화 시킨 값과 같다는 보장은 없다. 여기서 등장하는 개념이 Duality Gap 개념이다.

Duality Gap

원초문제의 최적화 값 - 쌍대문제의 최적화 값

Strong Duality

원초문제의 최적화 값과 쌍대문제의 값이 서로 일치하는 현상, Duality Gap = 0

Weak Duality

원초문제의 최적화 값이 쌍대 문제의 값보다 항상 큰 현상, Duality Gap > 0

Linear Programming 문제에서는 Strong Duality가 hold함이 증명되어 있다. 따라서 쌍대문제를 최적화 시키는 값 \(\t u, \t v\)를 찾음으로써 원초문제를 최적화 시키는 값 \(\textbf{x}\)를 찾을 수 있다.

3-1. Lagrange Dual Problem

이러한 Duality Problem은 Linear Programming을 넘어서 일반화된 폼에서도 적용할 수 있다.

\[\underset{\textbf{x}}{\min} f(\textbf{x})\\ \mbox{ subject to } g_i(\textbf{x}) \leq 0 , i =1,2,...,m \\\ \ \qquad \qquad h_j(\textbf{x}) =0 ,j=1,2,...,n\]

위 문제의 Lagrangean Function을 살펴보자

\(L(\t x ,\t u, \t v) = f(\t x) + \sum u_i g_i(\t x) + \sum v_j h_j(\t x)\) 제약식 부분은 0 아니면 음수이므로 \(f(\t x)\)보다 항상 작다. 따라서 다음과 같은 부등호가 성립된다.

\[\underset{\t x}{\min} f(\t x) \geq \underset{\t x \in C}{\min}L(\t x, \t u, \t v) \geq \underset{\t x}{\min} L(\t x, \t u, \t v) := g(\t u , \t v)\]

여기서 \(g(\t u, \t v)\)를 Lagrange Dual Fucntion이라고 부르고, \(\t u,\t v\)를 Dual Variable이라고 부른다.

이를 이용하면 다음과 같은 쌍대문제를 만들 수 있다.

Lagrange Dual Problem

\[\m {maximize } g(\t u , \t v) \\\ \m{subject to } \t u _i\geq 0\]

위의 부등호에 의해 이 쌍대 문제는 항상 Weak Duality가 성립한다.

여기서 중요한 점은 Lagrange Dual Function은 항상 Convex Function이라는 점이다.(Pointwise - Maximization Function) 따라서 Lagrange Dual Problem은 Convex Optimization Problem이다.

그리고 다음의 중요한 Property가 있다.

Slater’s Condition

If Primal is a Convex Problem and there exists at least one strictly feasible \(x \in \R^n\), then Strong Duality Holds.

만약 원초문제가 Convex Problem이고 적어도 하나의 $\t x$가 제약식을 Stictly 하게 만족할 때, Strong Duality가 성립한다.

\[\m{For a Standart Mathematical Optimization,}\\\ \m{If } \begin{cases}f, g_i \m { is convex and } h_j \m{ is affine}\\\ \m{ and } \exists x \in \R^n \m{ such that } g_i(\t x) <0 \m{ and } h_j (\t x) =0 \end{cases} \\\ \m{,then Strong Duality holds}\]

4. Karush - Kunh - Tucker Condition

이러한 최적화 문제를 푸는 데 있어 가장 좋은 방식은 KKT Condition을 활용하는 것이다. 즉 다음과 같다.

만약 \(\t x^*, \t u^* , \t v^*\)가 KKT Condition을 만족한다면, \(\t x^*, \t u^* , \t v^*\)는 원초문제와 쌍대문제의 최적해이다.

다음 Standard Problem에 대해서 Karush - Kunh - Tucker Condtion(이하 KKT Condition)은 다음과 같이 정의된다.

\[\underset{\textbf{x}}{\min} f(\textbf{x})\\ \mbox{ subject to } g_i(\textbf{x}) \leq 0 , i =1,2,...,m \\\ \ \qquad \qquad h_j(\textbf{x}) =0 ,j=1,2,...,n\]

Karush - Kunh - Tucker Condtion

• \(0 \in \partial_{\t x} (f(\t x) + \sum \t u_i g_i(\t x) + \sum \t v_j h_j(\t x))\) (Stationarity Condition)

\(\t x\)에 대한 편미분 벡터가 0을 포함해야 한다.

• \(\t u_i \cdot g_i (\t x) =0 \m{ for all }i\) (Complementary Slackness)
• \(g_i (\t x) \leq 0 , h_j (\t x) =0 \m{ for all }i,j\) (Primal Feasibility)
• \(\t u_i \geq 0 \m{ for all i}\) (Dual Feasibility)

이 조건을 만족하는 \(\t x, \t u, \t v\)에는 도대체 어떤 의미가 있을까? 전술했듯, KKT Condition을 만족하는 \(\t x, \t u, \t v\)는 원초문제와 쌍대문제의 최적해(\(\t x^*, \t u^*, \t v^*\))이다. 어떻게 도출된 건지 알아보자

위의 경우에서 Strong Duality가 만족된다고 가정하자. 그 경우 Duality Gap이 0이므로 \(f(\t x^*) = g(\t u^*,\t v^*)\)를 만족한다. 따라서 다음과 같은 식이 성립한다.

\[f(\t x ^*) = g(\t u^*,\t v^*) \\\ \qquad = \underset{\t x}{\min} \{f(\t x) + \sum\t u_i^* g_i (\t x) + \sum \t v_j ^* h_j(\t x)\} \\\ \qquad \leq f(\t x^*) + \sum\t u_i^* g_i (\t x^*) + \sum \t v_j ^* h_j(\t x^*)\} \\\ \qquad \leq f(\t x ^*)\]

• 위의 식을 잘 살펴보자. 두번째 줄이 성립하기 위해서는 \(\t x\)에 대해서 minimize한 것이므로 미분값이 0이어야 한다. 이것이 KKT Conditon의 첫번째 조건 Stationarity Condition 이다.
• 세번째 줄에서 네번째 줄로 넘어가기 위해서는 \(\sum \t u_i g_i(\t x) =0\)과 \(\sum \t v_j h_j (\t x) =0\)이어야 한다. 두번째 조건은 원초문제의 제약에 의해 자동으로 성립되지만 첫번째 조건은 따로 만들어 줘야한다. 이것이 KKT Condition의 두번째 조건 Complementary Slackness 이다.
• 위의 문제에서도 최적해들은 여전히 원초문제와 쌍대문제의 제약을 성립해야한다. 이것이 KKT Condition의 3번째 조건 Primal Feasibility ,4번째 조건 Dual Feasibility 를 이룬다.

(KKT Condition은 Strong Duality가 만족한다면 Convex Optimization이 아니라도 성립하는 것을 주지하자)

즉 이를 통해 알 수 있는 것은 다음과 같다.

만약 \(\t x^*,\t u^*,\t v^*\)가 원초문제와 쌍대문제의 최적해라면 \(\t x^*,\t u^*,\t v^*\)는 KKT Condition을 만족한다. (\(\Rightarrow\))

이 명제의 역도 성립한다.

\[\m{If } \exists \t x^*, \t u^*, \t v^* \m{ which holds KKT condition}\\\ \m{,then } g(\t u^*,\t v^*) = f(\t x^*) + \sum\t u_i^* g_i (\t x^*) + \sum \t v_j ^* h_j(\t x^*) \{\m{by Stationarity}\} \\\ \qquad \qquad \qquad = f(x^*)\{\m{by Complementary Slackness}\}\]

즉 \(\t x^*, \t u^*, \t v^*\)는 Duality Gap을 0으로 만든다. 따라서 \(\t x^*, \t u^*, \t v^*\)는 원초문제와 쌍대문제의 최적해이다.

만약 \(\t x^*, \t u^* , \t v^*\)가 KKT Condition을 만족한다면, \(\t x^*, \t u^* , \t v^*\)는 원초문제와 쌍대문제의 최적해이다. (\(\Leftarrow\))

만약 전자만 만족했다면 KKT Condition을 만족하는 \(\t x^*, \t u^* , \t v^*\)가 유일하다는 보장이 없지만 후자까지 만족함으로써, 유일성을 얻어낼 수 있다.

---

예시를 하나 풀어보자

아래는 Support Vector Machine을 만들기 위한 문제이다.

\[\underset{\beta,\beta_0,\epsilon}{\min} \frac{1}{2}\parallel\beta\parallel_2^2 +C \sum \epsilon_i \\\ \m{subject to } \epsilon_i \geq 0, i=1,2,...,n \\\ \qquad \qquad \ y_i(x_i^t\beta+\beta_0) \geq 1 - \epsilon_i , i =1,2,...,n\]

Dual Variable \(\t u,\t v\)를 도입하자. 그렇다면 다음과 같은 Lagrange Dual Function을 만들 수 있다.

\[L(\beta,\beta_0,\epsilon, \t u, \t v) = \frac{1}{2}\parallel\beta\parallel_2^2 +C \sum \epsilon_i - \sum \t u_i \epsilon_i -\sum v_i(y_i(x_i^t\beta+\beta_0)+\epsilon_i-1)\]

여기서 Primal Variable \(\t x = \{\beta,\beta_0,\epsilon_i\}\)이므로 첫번째 조건(Stationarity)를 만족시키기 위해서 다음을 구하자.

1) \(\partial_\t x L(\beta,\beta_0,\epsilon,\t u, \t v) =0\)

1-1) \(\frac{\partial L}{\partial \beta} = \beta -\sum v_i y_i x_i =0\)

1-2)\(\frac{\partial L}{\partial \beta_0} = -\sum v_i y_i =0\)

1-3)\(\frac{\partial L}{\partial \epsilon_i} = C -u_i -v_i=0\)

다음으로 두 번째 조건(Complementary Slackness)을 만족시키는 \(\t u, \t v\)를 찾아보자.

2) \(u_i g_i(\t x) = 0 \m{ for all i}\)

2-1) \(u_i \epsilon_i =0 \m{ for all i}\)

2-2) \(v_i(y_i(x_i^t \beta+\beta_0) + \epsilon_i -1) =0 \m{ for all i}\)

위 조건을 만족하는 \(\t u, \t v\)를 찾음으로써 \(\t x\)를 대신 찾을 수 있다.

---

Duality 원칙과 KKT Condition을 통해서 기존의 최적화 문제를 여러방식으로 풀어낼 수 있다. 이 개념들은 각종 최적화 문제를 푸는데에 있어서 기본이 되는 것이라고 한다. 체화를 잘 해낸 다음 다른 개념을 배울 때 적용해보자.

---

Boyd,S. & Vandenberghe, L. (2004) Convex Optimization.Cambridge, UK: Cambridge Press
Tibshirani,R. “KKT Conditions” Convex Optimization, Oct. 2019, Carnegie Mellon University, Pittsburgh