$\def\m#1{\mbox{#1}} \def\t#1{\textbf{#1}}$
앞선 포스팅에서는 Duality의 개념에 대해서 살펴보고 이를 이용해 제약이 있는 문제를 푸는 매우 강력한 툴인 KKT Condition에 대해서도 알아보았다. 그러나 Duality 개념은 KKT Condition을 유도하는 것 뿐만 아니라 훨씬 더 유용한 개념들로 확장될 수 있다. 이번 포스팅에서는 이러한 것들을 다루어 보려고 한다.
1. Lagrange Form
일반적인 L2-Penalty Problem은 다음과 같이 적는다.
$\underset{x}{\min} f(x) + \parallel x \parallel_p $
이는 목적함수에 제약식을 반영해 제약이 없는 문제의 형태로 바꿈으로써, 제약이 없을때 사용하는 여러가지 최적화 기법을 사용할 수 있게 해주는 테크닉이다.
그런데 이러한 테크닉이 제약을 정말 의도한대로 반영해줄 수 있을까? 다행히 이도 Duality 개념의 연장선에 있기 때문에 의도대로 반영되는 것을 보장할 수 있다.
즉, 적절한 $t,\lambda$ 아래서 아래의 두 폼은 동치이다.
| Constrained Form | Lagrange Form |
|---|---|
| $\ \underset{x}{\min} f(x) \\ \m{ subject to } h(x) \leq t$ | $\underset{x}{\min} f(x) + \lambda h(x) $ |
pf) $C \Rightarrow L$
If C is strictly Feasible ,then Strong Duality holds.
따라서 C-Form의 Lagrange Dual Problem은 $\underset{x}{\min} f(x) + \lambda (h(x)-t)$ 꼴이며 L-Form과는 목적함수에 $\lambda t$가 있느냐 없느냐의 차이지만 이는 x와 무관하기에 두 문제의 근은 똑같다.
pf) $L \Rightarrow C$
$x^\ast$를 L-Form의 근이라고 할때, $h(x^\ast)=t$로 둠으로써, C-Form의 KKT Condition이 성립하게 할 수 있으므로 L의 근은 C의 근이 된다.
2. Dual Norm
Duality라 함은 단순히 최적화 문제를 넘어 수학의 거의 전분야에 적용될 수 있는 개념이다. 그 중에서도 최적화 문제와 연관이 있는 Dual개념으로 Dual Norm이 있다. Dual Norm은 다음과 같이 정의된다.
Dual Norm
$\parallel x\parallel_\ast$ is dual norm iff
$\parallel x \parallel_\ast = \underset{\parallel z \parallel \leq 1}{\max} z^tx$
굉장히 복잡한 개념이라 직관적인 이해는 어렵다. 단, 이렇게 만들어진 Dual Norm의 Dual은 Primal Norm이 되기에 Duality의 성질을 가지고 있다고 말할 수 있다
다행히 몇가지 Norm들은 Dual Norm이 쉬운 형태로 존재한다.
LP Norm Dual
$(\parallel x \parallel_p)_\ast = \parallel x \parallel_q , \mbox{where }\frac{1}{p}+\frac{1}{q} =1$
pf)
$\parallel fg \parallel _2 \leq \parallel f \parallel_p \times \parallel g\parallel_q , \mbox{where }\frac{1}{p}+\frac{1}{q} =1$ (holder’s inequality)
$\mid fg\mid = f^tg \leq \parallel f \parallel_p \times \parallel g\parallel_q$
$f^t\frac{g}{\parallel g \parallel_q} \leq \parallel f \parallel_p$
$\underset{\parallel g’\parallel_q \leq 1}{\max} f^tg’ = \parallel f \parallel_p $
Trace Norm Dual
$(\parallel X \parallel_{tr})\ast = \parallel x \parallel{op}$
cf)
$\parallel X \parallel_{tr} = \sum_i \sigma_i(X)$
$\parallel X \parallel_{op} = \sigma_1(x)$
Dual Norm의 Dual이 Primal Norm인 것도 증명해보자.
pf)
최적화 문제 $\underset{y}{\min} \parallel y \parallel s.t. \ y=x $를 생각해보자.
이 문제의 근은 매우 쉽게 x임을 알 수 있다.
이 문제의 Lagrange Dual Problem을 살펴보자.
$\underset{y}{\min} \parallel y \parallel -u^t(y-x) = \parallel y \parallel -u^ty+u^tx$
이때 Dual Norm의 정의를 생각해보자.
$\parallel u \parallel_\ast = \underset{\parallel y\parallel \leq 1}{\max} u^ty$
만약 $\parallel u \parallel _\ast > 1 $일시 $\min_y {\parallel y \parallel - y u^t}$는 음수로 발산한다.
만약 $\parallel u\parallel_\ast \leq 1 $일시 $\min_y {\parallel y \parallel - y u^t}$는 0이다.
따라서 Lagrange Dual Problem은 다음과 같다
$\underset{u}{\max} u^tx \ s.t. \ \parallel u \parallel_\ast \leq 1 $
이에 대해 Strong Duality가 성립하므로 원초 문제 $\parallel x \parallel = \parallel x \parallel_{\ast \ast}$이다.
3. Conjugate Function
최적화 문제에서 또 유용하게 다룰 수 있는 개념으로 Conjugate Function이 있다.
$f: \mathbb{R}^2 \rightarrow \mathbb{R}$에 대해 Conjugate Funcion $f^\ast$는 다음과 같이 정의된다.
$f^\ast (y) = \underset{x}{\max} y^tx - f(x)$
이는 f(x)의 형태와 무관하게 항상 Convex Function인데, $g_x(y) = y^tx-f(x)$가 y에 대한 Convex function이며, $f^\ast(y) = \max_x g_x(y)$이므로 Convex Function의 Pointwise Maximization이다. 따라서 $f^\ast(x)$는 항상 Convex Function이다.
이에 더해 만약 f(x)가 미분가능하다면 이러한 변형을 일컬어 Legendre Transformation이라고 말한다.
conjugate function엔 아래와 같은 property가 있다.
- Fenchel’s Inequality: $\forall x,y, \quad f(x) + f^\ast(y) \geq x^ty$
pf)
$f^\ast(y) = \max x^ty-f(x) \geq x^t y - f(x) \\ \Rightarrow f(x)+f^\ast(y) \geq x^ty$
- Conjugate of Conjugate : $f^{\ast\ast} \leq f$
pf)
$f^{\ast \ast}(z) = \underset{y}{\max}{ z^ty-f^\ast(y)} \\ \ \qquad = \underset{y}{\max}{ z^ty-\underset{x}{\max} {x^ty - f(x)}} \\ \ \qquad \leq \underset{y}{\max}{ z^ty-{x^ty - f(x)}} \quad (\mbox{ ineqaulity holds for any x}) \\ \ \qquad = z^ty^\ast-x^ty^\ast +f(x) \quad(\mbox{it holds for any x, including x=z}) \\ \ \qquad \Rightarrow f^{\ast \ast }(z) \leq f(z) \quad(\mbox{by setting x to z}) $
-
If $f$ is closed and convex, then for any x,y
$\ x \in \partial f^\ast(y) \iff y \in \partial f(x) $
-
If $f$ is closed and convex, then $f^{\ast \ast} = f$
pf)
$f^{\ast \ast}(z) = \underset{y}{\max} z^ty-f^\ast(y)$
$\ \Rightarrow 0 \in z - \partial f^\ast(y^\ast) { \mbox{by subgradient optimality of convex function } f^\ast(x)} \\ \Rightarrow z \in \partial f^\ast(y^\ast)$
$f^\ast(y^\ast) = \underset{x}{\max} y^{\ast t}x - f(x) \\ \Rightarrow 0 \in y^\ast - \partial f(x^\ast) { \mbox{by subgradient optimality of convex function } f(x)} \\ \Rightarrow x^\ast \in \partial f^\ast (y^\ast) (\mbox{by above property})$
$x^\ast$는Optimality Condition을 만족하기만 하면 되므로 위의 조건을 만족한다면 $x^\ast$를 임의로 설정할 수 있다.$\partial f^\ast (y^\ast)$에는 z도 포함되어 있으므로 $x^\ast$를 z로 두자. 그 경우 다음과 같이 풀 수 있다.
$f^{\ast\ast}(z) = \underset{y}{\max} z^ty-f^\ast(y) =\underset{y}{\max} y^tz-y^t x^\ast+f(x^\ast) \\ \qquad = f(z) \qquad (\mbox{by setting }x^\ast \mbox{ to }z)$
- If $f(u,v) = f_1(u) + f_x(v)$,then $f^\ast (w,z) = f_1^\ast(w)+f_2^\ast(z)$
ex)Simple Quadratic
$f(x) = \frac{1}{2}x^tQx , 0 \prec Q $
$f^\ast (x) = \max y^tx- \frac{1}{2}x^tQx$는 $x = Q^{-1}y$일때 최대치가 된다.
즉 다음과 같다.
$f^\ast(x) = \frac{1}{2}y^tQ^{-1}y$
즉, Q의 역행렬을 최적화 하는 문제로 바뀐다. Q 계산이 까다로울때, 역행렬을 쉽게 도출할 수 있다면 (반대도 마찬가지) 이를 이용하여 문제를 쉽게 바꿀수 있다.
ex)Indicator Function
$f(x) = I_C(x) = \begin{cases} \ 0 \quad \mbox{ if }x \in C \\ \infty \quad \mbox{if }x \notin C \end{cases}$의 Conjugate는 다음과 같다.
$f^\ast (y) = \underset{x}{\max} y^tx-I_C(x) \\ \qquad= \underset{x\in C}{\max} y^tx $
이를 일컬어 Support Function이라고 말한다.
ex) Norm Function
If $f(x) = \parallel x\parallel$, then its conjugate is $f^\ast(x) = I_{{z: \parallel z \parallel_\ast \leq 1}}(x)$
pf)
$f^\ast(x) = \underset{y}\max {x^ty - \parallel y \parallel} \\ \qquad = \underset{y}{\max} { x^ty - \underset{\parallel z\parallel_\ast \leq 1 }{\max} z^ty} $
이에 대해 만약 $\parallel x\parallel_\ast \leq 1 $일시 0, 아닐시 발산한다.
이러한 Conjugate Function은 Dual Problem을 유도할때 사용할 수 있다.
다음 문제를 생각해보자.
$\underset{x}\min f(x)+g(x) $
이에 대해 변수를 분리시켜서 다음과 같이 만들 수 있다.
$\underset{x,z}{\min} f(x) +g(z) \ s.t. \ x=z$
이 함수의 Lagrange Dual Function은 다음과 같다.
$h(\mu) = \underset{x,z}{\min} f(x)+g(z) +u^t(z-x) \\ \quad \ \ = -\underset{x}{\max}(u^tx - f(x)) - \underset{z}{\max}(-u^tz-g(z)) \\ \quad \ \ =-f^\ast(u)-g^\ast(-u)$
즉 다음 문제와 같다.
$\underset{u}{\max} {-f^\ast(u)-g^\ast(-u)}$
ex) Norm-Penalty
Primal : $\underset{x}{\min} f(x) + \parallel x \parallel $
Dual : $\underset{u}{\max} - f^\ast(u) - I_{{z : \parallel z\parallel \ast \leq 1 }}(u) \\ \Rightarrow \underset{x}\max -f^\ast(u) \mbox{ subject to } \parallel u \parallel\ast \leq 1$
4. Duality Technique
Shifting Linear Transformation
Conjugate Dual Function이 가장 잘 사용될 수 있는 부분은 바로 선형결합의 이동에 있다.
예를 들어 다음 문제를 생각해보자.
$\underset{x}{\min} f(x) + g(Ax)$
이는 다음 문제와 동치이다.
$\underset{x,z}{\min} f(x) + g(z) \mbox{ subject to } Ax = z $
이에 대한 Dual Function은 다음과 같다.
$\ h(u) = \underset{x,z}{\min} f(x)+g(z)+u^t(z-Ax) \\ \qquad = -\underset{x}{\max}{u^tAx-f(x)} -\underset{z}{\max}{u^tz-f(z)} \\ \qquad = -f^\ast(A^tu)-g^\ast(-u)$
선형 결합 꼴이 g에서 f로 넘어갔다. 따라서, g가 복잡한 함수고 선형결합 때문에 더 복잡해진다면 f로 넘겨서 쉽게 풀 수 있다.
Dual Cone
Cone Set에 대해서도 Duality 개념을 도입할 수 있다.
우선 Cone의 정의는 다음과 같다.
$K \subset \mathbb{R}^n $ is cone iff $x \in K$ implies $\forall t \geq 0 , \quad tx \in K$
이에 대한 Dual Cone은 다음과 같이 정의된다.
Dual Cone
$K^\ast = {y : y^t x \geq 0 \mbox{ for all }x \in K}$
Normal Cone 과 비슷하지만 Half Space의 방향이 반대이다. 다음의 그림으로 이해를 해보자.
Dual Cone은 항상 Convex Cone이며 Primal Cone이 Closed Convex Cone일시 $K^{\ast\ast} = K$이다.
ex)Dual Cone
Linear Subspace : dual cone of Linear Subspace V is $V^{\perp}$
Norm Cone : Norm Cone은 다음과 같이 정의된다.
$K = {(x,t) \in \mathbb{R}^{n+1} : \parallel x \parallel \leq t}$
이에 대한 Dual Cone은 다음과 같이 정해진다.
$K^\ast = {(x,t) \in \mathbb{R}^{n+1} : \parallel x \parallel_\ast \leq t}$
이 Dual Cone은 다음과 같은 개념으로 연결된다.
다음과 같은 Cone constrained problem을 생각해보자.
$\underset{x}{\min} f(x) \mbox{ subject to } Ax \in K$
이는 다음과 같이 바꿀 수 있다.
$\underset{x}{\min} f(x) +I_K( Ax)$
이에 대한 Conjugate Dual Problem은 다음과 같다.
$\underset{u}{\max} - f^\ast(A^tu)-I_K^\ast(-u)$
이는 Dual Cone 개념을 사용하여 다음과 같이 바꿀수 있다.
$\underset{u}{\max} - f^\ast(A^tu)-I_{K^\ast}(-u)$
Boyd,S. & Vandenberghe, L. (2004) Convex Optimization.Cambridge, UK: Cambridge Press
Tibshirani,R. “KKT Conditions” Convex Optimization, Oct. 2019, Carnegie Mellon University, Pittsburgh