Duality
25 Jan 2018 | Duality
이번 글에서는 Duality와 관련된 개념들을 살펴보도록 하겠습니다. 이 글은 미국 카네기멜런대학 강의를 기본으로 하되 영문 위키피디아 또한 참고하였습니다. 그럼 시작하겠습니다.
concept
최적화 이론에서 쌍대성(雙對性; duality)이란 어떤 최적화 문제가 원초문제(the primal problem)와 쌍대문제(the dual problem)의 두 가지 관점에서 볼 수 있다는 원칙입니다. 쌍대문제의 상한은 primal problem의 하한(a lower bound)이 됩니다. 선형계획법(linear programming)를 예로 들어보겠습니다. 다음과 같이 주어진 선형 조건을 만족시키면서 선형인 목적함수 $c^Tx$를 최소화하는 문제입니다. ($c$는 $n$차원. $b$는 $m$차원, $h$는 $r$차원 벡터, $A$는 $m×n$, $G$는 $r×n$ 행렬)
\[\begin{align*}
&\min_{ x }&&{ { c }^{ T }x } \\ &subject\quad to\quad &&Ax=b\\ &&&Gx\le h
\end{align*}\]
위 식은 행렬-벡터 형식인데요. 이를 스칼라 형태의 식으로 살펴보면 등식 형태의 제약식이 $m$개, 부등식 형태의 제약식이 $r$개가 있고, 이를 만족하면서 목적함수를 최대화시키는 $n$개의 미지수를 찾는 문제라고도 이해할 수 있습니다. 제약식 양변에 $u$, $v$라는 벡터를 곱해 봅시다. 여기에서 $v≥0$, 즉 벡터 $v$의 모든 요소는 0 이상의 값을 지닙니다. 따라서 위 식에서 부등식 형태의 제약식은 부등호 방향이 바뀌지 않습니다.
\[{ u }^{ T }Ax={ u }^{ T }b\\ { v }^{ T }Gx\le { v }^{ T }h\]
위 두 개 식을 더하고, 정리해 주면 다음과 같은 형태가 됩니다.
\[\begin{align*}
{ u }^{ T }Ax+{ v }^{ T }Gx&\le { u }^{ T }b+{ v }^{ T }h\\ \left( { u }^{ T }A+{ v }^{ T }G \right) x&\le { u }^{ T }b+{ v }^{ T }h\\ { \left( { A }^{ T }u+{ G }^{ T }v \right) }^{ T }x&\le { u }^{ T }b+{ v }^{ T }h\\ { \left( -{ A }^{ T }u-{ G }^{ T }v \right) }^{ T }x&\ge -{ u }^{ T }b-{ v }^{ T }h\\ \therefore \quad { c }^{ T }x&\ge -{ u }^{ T }b-{ v }^{ T }h
\end{align*}\]
위 식에서 볼 수 있듯 $-A^Tu-G^Tv$가 $c$가 되도록 하면, primal problem의 목적함수 $c^Tx$의 하한(a lower bound)은 $-u^Tb-v^Th$가 됩니다. 따라서 $-A^Tu-G^Tv=c$, $v≥0$이라는 제약식을 만족시키면서, $-u^Tb-v^Th$를 최대화하는 문제가 primal problem과 동일해질 겁니다. 결론적으로 말해 아래와 같은 형태가 primal problem와 쌍을 이루는 dual problem이 됩니다. primal problem에서는 주어진 식을 만족하는 벡터 $x$를 찾는 것이었으나 dual problem에서는 벡터 $u, v$를 찾는 문제가 됩니다.
\[\begin{align*}
&\max_{ u,v }&&{ -{ b }^{ T }{ u }-{ h }^{ T }{ v } } \\ &subject\quad to\quad && -{ A }^{ T }{ u }-{ G }^{ T }{ v } = c\\ &&&v\ge 0
\end{align*}\]
라그랑지안적 접근
primal problem과 dual problem을 라그랑주 승수법(Lagrange multiplier method)과 연관지어 살펴볼 수도 있습니다. 라그랑주 승수법이란 최적화하려는 값에 형식적인 라그랑주 승수(multiplier) 항을 더하여, 제약된 문제를 제약이 없는 문제로 바꾸는 방법입니다. 라그랑주 승수법 관련 자세한 내용은 이곳이나 이곳을 참고하시면 좋을 것 같습니다. 전 챕터에 이어 선형계획법 예시를 가지고 primal과 dual 문제를 살펴보겠습니다. primal problem을 다시 살펴보겠습니다.
\[\begin{align*}
&\min_{ x }&&{ { c }^{ T }x } \\ &subject\quad to\quad &&Ax=b\\ &&&Gx\le h
\end{align*}\]
위 primal problem을 라그랑주 승수 벡터 $u$와 $v$를 도입해 라그랑주 함수 $L$을 만들면 다음과 같은 형태가 됩니다. 단 여기에서 $v≥0$, 즉 벡터 $v$의 모든 요소는 0 이상의 값을 지닙니다.
\[L\left( x,u,v \right) ={ c }^{ T }x+{ u }^{ T }\left( Ax-b \right) +{ v }^{ T }\left( Gx-h \right)\le{c}^{T}x\]
그런데 위 식 우변의 두번째 항은 항상 0입니다($∵ Ax=b$). 세번째 항은 항상 0 이하의 값을 갖습니다($∵Gx≤h, v≥0$) 따라서 $L$은 목적함수 $c^Tx$보다 항상 작거나 같습니다. 여기에서 $C$를 원초문제의 제약식을 만족하는 $x$의 집합, $f^*$를 우리가 찾으려는 최적값이라고 할 때 다음 식이 성립합니다.
\[{ f }^{ * }\ge \min _{ x\in C }{ L\left( x,u,v \right) } \ge \min _{ x }{ L\left( x,u,v \right) }\]
위 부등식의 의미는 이렇습니다. 제약조건이 있는 것보다는, 없는 환경에서 해당 식의 값을 더 작게 만들 수 있을 겁니다. 위 부등식 가운데 오른쪽 마지막 항을 $g(u,v)$라 두겠습니다. $g(u,v)$를 라그랑지 듀얼 함수(Lagrange dual function)이라고도 부릅니다. 그러면 $g(u,v)$는 어떤 값을 지닐까요? 차근차근 구해보겠습니다.
우선 $g(u,v)$는 그 정의상 $L$의 최소값 즉, $min_x{L(x,u,v)}$입니다. $L$은 우리가 알고 싶은 미지수로 편미분한 결과가 0이 되는 지점에서 최소값을 갖습니다. $L$을 $x$로 편미분한 결과는 다음과 같습니다.
\[\frac { \partial L }{ \partial x } ={ c }^{ T }+{ u }^{ T }A+v^{ T }G=0\\ \therefore \quad c=-{ A }^{ T }u-{ G }^{ T }v\]
따라서 위 식을 $L$에 대입해 풀면 $g(u,v)$를 구할 수 있습니다.
\[\begin{align*}
L\left( x,u,v \right)&= { c }^{ T }x+{ u }^{ T }\left( Ax-b \right) +{ v }^{ T }\left( Gx-h \right)\\&\Rightarrow { \left( -{ A }^{ T }u-{ G }^{ T }v \right) }^{ T }x+{ u }^{ T }\left( Ax-b \right) +{ v }^{ T }\left( Gx-h \right) \\ &=-u^{ T }Ax-v^{ T }Gx+u^{ T }Ax-u^{ T }b+v^{ T }Gx-{ v }^{ T }h\\ &=-u^{ T }b-{ v }^{ T }h\\&=g(u,v)
\end{align*}\]
우리는 이미 $f^*≥g(u,v)$라는 관계를 확인했으므로, primal problem의 최소값을 찾는 것은 $g(u,v)$를 최대화하는 문제와 동일하다는 걸 확인할 수 있습니다. 단 라그랑주 승수법을 적용하는 과정에서 가정한 두 가지 조건, 즉 $-A^Tu-G^Tv=c$, $v≥0$을 만족해야 합니다.
따라서 우리는 다음과 같이 dual problem으로 다시 쓸 수 있습니다. 이는 당초 primal problem과 쌍을 이룹니다.
\[\begin{align*}
&\max_{ u,v }&&{ -{ b }^{ T }{ u }-{ h }^{ T }{ v } } \\ &subject\quad to\quad && -{ A }^{ T }{ u }-{ G }^{ T }{ v } = c\\ &&&v\ge 0
\end{align*}\]
라그랑지안적 접근의 장점은 지금까지 설명해드렸던 선형계획법 이외에도 임의의 최적화 문제에 대해 모두 적용할 수가 있다는 점입니다. 다시 말해 라그랑주 승수법을 적용해 다양한 유형의 primal problem를 dual problem으로 바꿔풀 수가 있습니다. 이제 최적화 문제를 일반적인 케이스에 적용해 봅시다. 다음과 같은 primal problem이 주어졌다고 칩시다.
\[\begin{align*}
&\min _{ x }&&{ f\left( x \right) } \\ &subject\quad to\quad &&{ h }_{ i }\left( x \right) \le 0,\quad i=1,...,m\\ &&&{ l }_{ j }\left( x \right) =0,\quad j=1,...,r
\end{align*}\]
라그랑지안 함수 $L$과 라그랑지 듀얼함수 $g$를 각각 정의합니다. 이미 살펴봤듯이 부등식 형태의 제약식에 붙는 라그랑주 승수(multiplier) $u_i$는 모두 0 이상의 값을 지녀야 합니다.
\[\begin{align*}
L\left( x,u,v \right) =&f\left( x \right) +\sum _{ i=1 }^{ m }{ { u_{ i }h }_{ i }\left( x \right) } +\sum _{ j=1 }^{ r }{ { v_{ i }l }_{ j }\left( x \right) } \\ g\left( u,v \right) =&\min _{ x }{ L\left( x,u,v \right) }
\end{align*}\]
$f^*≥g(u,v)$이므로 dual problem은 다음과 같이 쓸 수 있습니다. primal problem에서는 주어진 식을 만족하는 벡터 $x$를 찾는 것이었으나 dual problem에서는 벡터 $u, v$를 찾는 문제가 됩니다. 아울러 최소 문제가 최대 문제로 바뀌었습니다.
\[\begin{align*}
&\max_{ u,v }&&{ { g }(u,v) } \\ &subject\quad to\quad &&u\ge 0
\end{align*}\]
한편 dual problem은 항상 convex 문제가 됩니다. $g(u,v)$를 아래와 같이 자세히 뜯어보면 convexity를 보존하는 연산만 수행이 되기 때문입니다. convexity를 보존하는 연산에 대해서는 이곳을 참고하면 좋을 것 같습니다.
duality gap
$g(u,v)$는 $f$-star의 하한(a lower bound)입니다. 이를 바꾸어 말하면 dual problem의 목적함수 $g(u,v)$를 최대화하는 것은 primal problem의 목적함수를 최소화하는 문제가 됩니다. 그런데 primal problem의 해와 dual problem의 해가 반드시 같지는 않습니다. 아래 부등식에서 $f$의 최적값과 $g(u,v)$ 사이에 차이가 존재할 수 있음을 확인할 수 있습니다. 이를 duality gap이라고 합니다.
\[{ f }^{ * }\ge \min _{ x }{ L\left( x,u,v \right) }=g(u,v)\]
$f$의 최적값과 $g(u,v)$ 사이에 위와 같은 관계를 지니면 weak dual이라고 합니다. 그런데 아래와 같은 관계를 지니면 strong dual이라고 합니다. duality gap이 없음을 확인할 수 있습니다.
\[{ f }^{ * }=g(u,v)\]
primal problem의 목적함수와 제약식이 특정 조건을 만족하면 strong duality 속성을 지니게 된다고 합니다. 이것이 Slater’s condition입니다. 다음과 같습니다.
이번 글에서는 Duality와 관련된 개념들을 살펴보도록 하겠습니다. 이 글은 미국 카네기멜런대학 강의를 기본으로 하되 영문 위키피디아 또한 참고하였습니다. 그럼 시작하겠습니다.
concept
최적화 이론에서 쌍대성(雙對性; duality)이란 어떤 최적화 문제가 원초문제(the primal problem)와 쌍대문제(the dual problem)의 두 가지 관점에서 볼 수 있다는 원칙입니다. 쌍대문제의 상한은 primal problem의 하한(a lower bound)이 됩니다. 선형계획법(linear programming)를 예로 들어보겠습니다. 다음과 같이 주어진 선형 조건을 만족시키면서 선형인 목적함수 $c^Tx$를 최소화하는 문제입니다. ($c$는 $n$차원. $b$는 $m$차원, $h$는 $r$차원 벡터, $A$는 $m×n$, $G$는 $r×n$ 행렬)
\[\begin{align*} &\min_{ x }&&{ { c }^{ T }x } \\ &subject\quad to\quad &&Ax=b\\ &&&Gx\le h \end{align*}\]위 식은 행렬-벡터 형식인데요. 이를 스칼라 형태의 식으로 살펴보면 등식 형태의 제약식이 $m$개, 부등식 형태의 제약식이 $r$개가 있고, 이를 만족하면서 목적함수를 최대화시키는 $n$개의 미지수를 찾는 문제라고도 이해할 수 있습니다. 제약식 양변에 $u$, $v$라는 벡터를 곱해 봅시다. 여기에서 $v≥0$, 즉 벡터 $v$의 모든 요소는 0 이상의 값을 지닙니다. 따라서 위 식에서 부등식 형태의 제약식은 부등호 방향이 바뀌지 않습니다.
\[{ u }^{ T }Ax={ u }^{ T }b\\ { v }^{ T }Gx\le { v }^{ T }h\]위 두 개 식을 더하고, 정리해 주면 다음과 같은 형태가 됩니다.
\[\begin{align*} { u }^{ T }Ax+{ v }^{ T }Gx&\le { u }^{ T }b+{ v }^{ T }h\\ \left( { u }^{ T }A+{ v }^{ T }G \right) x&\le { u }^{ T }b+{ v }^{ T }h\\ { \left( { A }^{ T }u+{ G }^{ T }v \right) }^{ T }x&\le { u }^{ T }b+{ v }^{ T }h\\ { \left( -{ A }^{ T }u-{ G }^{ T }v \right) }^{ T }x&\ge -{ u }^{ T }b-{ v }^{ T }h\\ \therefore \quad { c }^{ T }x&\ge -{ u }^{ T }b-{ v }^{ T }h \end{align*}\]위 식에서 볼 수 있듯 $-A^Tu-G^Tv$가 $c$가 되도록 하면, primal problem의 목적함수 $c^Tx$의 하한(a lower bound)은 $-u^Tb-v^Th$가 됩니다. 따라서 $-A^Tu-G^Tv=c$, $v≥0$이라는 제약식을 만족시키면서, $-u^Tb-v^Th$를 최대화하는 문제가 primal problem과 동일해질 겁니다. 결론적으로 말해 아래와 같은 형태가 primal problem와 쌍을 이루는 dual problem이 됩니다. primal problem에서는 주어진 식을 만족하는 벡터 $x$를 찾는 것이었으나 dual problem에서는 벡터 $u, v$를 찾는 문제가 됩니다.
\[\begin{align*} &\max_{ u,v }&&{ -{ b }^{ T }{ u }-{ h }^{ T }{ v } } \\ &subject\quad to\quad && -{ A }^{ T }{ u }-{ G }^{ T }{ v } = c\\ &&&v\ge 0 \end{align*}\]라그랑지안적 접근
primal problem과 dual problem을 라그랑주 승수법(Lagrange multiplier method)과 연관지어 살펴볼 수도 있습니다. 라그랑주 승수법이란 최적화하려는 값에 형식적인 라그랑주 승수(multiplier) 항을 더하여, 제약된 문제를 제약이 없는 문제로 바꾸는 방법입니다. 라그랑주 승수법 관련 자세한 내용은 이곳이나 이곳을 참고하시면 좋을 것 같습니다. 전 챕터에 이어 선형계획법 예시를 가지고 primal과 dual 문제를 살펴보겠습니다. primal problem을 다시 살펴보겠습니다.
\[\begin{align*} &\min_{ x }&&{ { c }^{ T }x } \\ &subject\quad to\quad &&Ax=b\\ &&&Gx\le h \end{align*}\]위 primal problem을 라그랑주 승수 벡터 $u$와 $v$를 도입해 라그랑주 함수 $L$을 만들면 다음과 같은 형태가 됩니다. 단 여기에서 $v≥0$, 즉 벡터 $v$의 모든 요소는 0 이상의 값을 지닙니다.
\[L\left( x,u,v \right) ={ c }^{ T }x+{ u }^{ T }\left( Ax-b \right) +{ v }^{ T }\left( Gx-h \right)\le{c}^{T}x\]그런데 위 식 우변의 두번째 항은 항상 0입니다($∵ Ax=b$). 세번째 항은 항상 0 이하의 값을 갖습니다($∵Gx≤h, v≥0$) 따라서 $L$은 목적함수 $c^Tx$보다 항상 작거나 같습니다. 여기에서 $C$를 원초문제의 제약식을 만족하는 $x$의 집합, $f^*$를 우리가 찾으려는 최적값이라고 할 때 다음 식이 성립합니다.
\[{ f }^{ * }\ge \min _{ x\in C }{ L\left( x,u,v \right) } \ge \min _{ x }{ L\left( x,u,v \right) }\]위 부등식의 의미는 이렇습니다. 제약조건이 있는 것보다는, 없는 환경에서 해당 식의 값을 더 작게 만들 수 있을 겁니다. 위 부등식 가운데 오른쪽 마지막 항을 $g(u,v)$라 두겠습니다. $g(u,v)$를 라그랑지 듀얼 함수(Lagrange dual function)이라고도 부릅니다. 그러면 $g(u,v)$는 어떤 값을 지닐까요? 차근차근 구해보겠습니다.
우선 $g(u,v)$는 그 정의상 $L$의 최소값 즉, $min_x{L(x,u,v)}$입니다. $L$은 우리가 알고 싶은 미지수로 편미분한 결과가 0이 되는 지점에서 최소값을 갖습니다. $L$을 $x$로 편미분한 결과는 다음과 같습니다.
\[\frac { \partial L }{ \partial x } ={ c }^{ T }+{ u }^{ T }A+v^{ T }G=0\\ \therefore \quad c=-{ A }^{ T }u-{ G }^{ T }v\]따라서 위 식을 $L$에 대입해 풀면 $g(u,v)$를 구할 수 있습니다.
\[\begin{align*} L\left( x,u,v \right)&= { c }^{ T }x+{ u }^{ T }\left( Ax-b \right) +{ v }^{ T }\left( Gx-h \right)\\&\Rightarrow { \left( -{ A }^{ T }u-{ G }^{ T }v \right) }^{ T }x+{ u }^{ T }\left( Ax-b \right) +{ v }^{ T }\left( Gx-h \right) \\ &=-u^{ T }Ax-v^{ T }Gx+u^{ T }Ax-u^{ T }b+v^{ T }Gx-{ v }^{ T }h\\ &=-u^{ T }b-{ v }^{ T }h\\&=g(u,v) \end{align*}\]우리는 이미 $f^*≥g(u,v)$라는 관계를 확인했으므로, primal problem의 최소값을 찾는 것은 $g(u,v)$를 최대화하는 문제와 동일하다는 걸 확인할 수 있습니다. 단 라그랑주 승수법을 적용하는 과정에서 가정한 두 가지 조건, 즉 $-A^Tu-G^Tv=c$, $v≥0$을 만족해야 합니다.
따라서 우리는 다음과 같이 dual problem으로 다시 쓸 수 있습니다. 이는 당초 primal problem과 쌍을 이룹니다.
\[\begin{align*} &\max_{ u,v }&&{ -{ b }^{ T }{ u }-{ h }^{ T }{ v } } \\ &subject\quad to\quad && -{ A }^{ T }{ u }-{ G }^{ T }{ v } = c\\ &&&v\ge 0 \end{align*}\]라그랑지안적 접근의 장점은 지금까지 설명해드렸던 선형계획법 이외에도 임의의 최적화 문제에 대해 모두 적용할 수가 있다는 점입니다. 다시 말해 라그랑주 승수법을 적용해 다양한 유형의 primal problem를 dual problem으로 바꿔풀 수가 있습니다. 이제 최적화 문제를 일반적인 케이스에 적용해 봅시다. 다음과 같은 primal problem이 주어졌다고 칩시다.
\[\begin{align*} &\min _{ x }&&{ f\left( x \right) } \\ &subject\quad to\quad &&{ h }_{ i }\left( x \right) \le 0,\quad i=1,...,m\\ &&&{ l }_{ j }\left( x \right) =0,\quad j=1,...,r \end{align*}\]라그랑지안 함수 $L$과 라그랑지 듀얼함수 $g$를 각각 정의합니다. 이미 살펴봤듯이 부등식 형태의 제약식에 붙는 라그랑주 승수(multiplier) $u_i$는 모두 0 이상의 값을 지녀야 합니다.
\[\begin{align*} L\left( x,u,v \right) =&f\left( x \right) +\sum _{ i=1 }^{ m }{ { u_{ i }h }_{ i }\left( x \right) } +\sum _{ j=1 }^{ r }{ { v_{ i }l }_{ j }\left( x \right) } \\ g\left( u,v \right) =&\min _{ x }{ L\left( x,u,v \right) } \end{align*}\]$f^*≥g(u,v)$이므로 dual problem은 다음과 같이 쓸 수 있습니다. primal problem에서는 주어진 식을 만족하는 벡터 $x$를 찾는 것이었으나 dual problem에서는 벡터 $u, v$를 찾는 문제가 됩니다. 아울러 최소 문제가 최대 문제로 바뀌었습니다.
\[\begin{align*} &\max_{ u,v }&&{ { g }(u,v) } \\ &subject\quad to\quad &&u\ge 0 \end{align*}\]한편 dual problem은 항상 convex 문제가 됩니다. $g(u,v)$를 아래와 같이 자세히 뜯어보면 convexity를 보존하는 연산만 수행이 되기 때문입니다. convexity를 보존하는 연산에 대해서는 이곳을 참고하면 좋을 것 같습니다.
duality gap
$g(u,v)$는 $f$-star의 하한(a lower bound)입니다. 이를 바꾸어 말하면 dual problem의 목적함수 $g(u,v)$를 최대화하는 것은 primal problem의 목적함수를 최소화하는 문제가 됩니다. 그런데 primal problem의 해와 dual problem의 해가 반드시 같지는 않습니다. 아래 부등식에서 $f$의 최적값과 $g(u,v)$ 사이에 차이가 존재할 수 있음을 확인할 수 있습니다. 이를 duality gap이라고 합니다.
\[{ f }^{ * }\ge \min _{ x }{ L\left( x,u,v \right) }=g(u,v)\]$f$의 최적값과 $g(u,v)$ 사이에 위와 같은 관계를 지니면 weak dual이라고 합니다. 그런데 아래와 같은 관계를 지니면 strong dual이라고 합니다. duality gap이 없음을 확인할 수 있습니다.
\[{ f }^{ * }=g(u,v)\]primal problem의 목적함수와 제약식이 특정 조건을 만족하면 strong duality 속성을 지니게 된다고 합니다. 이것이 Slater’s condition입니다. 다음과 같습니다.
Comments