[Week 5] Duality [3]

ESC·2023년 12월 13일

2023-Winter

목록 보기

9/10

아주 간단한 equivalent reformulation만으로도 매우 다른 dual problem을 도출할 수 있다. 기존 문제를 보다 쉽게 풀거나 해석하기 위한 방법이다. 크게 3가지의 대표적인 reformulation 방법이 존재하는데, 이번 포스트를 통해 각각에 대해 자세히 살펴보자.

1. Introducing new variables and equality constraints

다음과 같이 제약조건이 없는 primal problem이 있다고 가정하자.

{\begin{aligned}&{\text{minimize }}\ f_0(Ax+b) \end{aligned}}

이것의 Lagrangian은 $L(x) = f_0(Ax+b)$ 로, Lagrange dual function 값이 $p*$ 와 완전히 동일한 형태의 상수가 되므로 strong duality 하에서 어떠한 의미도 같지 못한다. 그러나 해당 식에 새로운 변수 $y = Ax+b$ 를 도입할 경우 이 problem은 다음과 같이 재정리 된다.

{\begin{aligned}&{\text{minimize }} \ f_0(y) \\[0.5ex]&{\text{subject to }} \ Ax+b=y \end{aligned}}

이때 objective function과 하나의 equality constraint를 가진 Lagrangian과 Lagrange dual function은 다음과 같이 reformulated된다. Infimum이 $-\infin$ 이 되지 않으려면 $A^T\nu=0$ 이어야 한다.

L(x, y, \nu)=f_0(y)\ +\ \nu^T(Ax+b-y)\\g(\nu) = b^T\nu \ +\ \inf_y(f_0(y)-\nu^Ty)=b^T\nu\ -\ f_0^*(\nu)

이때, $f^*_0$ 는 $f_0$ 의 conjugate이다(형태 참고). 따라서 이것의 dual problem은 다음과 같이 표현된다.

{\begin{aligned}&{\text{maximize }} \ b^T\nu\ -\ f^*_0(\nu) \\[0.5ex]&{\text{subject to }} \ A^T\nu=0 \end{aligned}}

따라서 이러한 reformulated problem의 dual은 original problem의 dual보다 유용할 수 있다. 이처럼 새로운 변수와 등식 제약을 도입한 식 변형은 objective function 뿐만 아니라 constraint function에도 적용될 수 있다. 다음의 예시( $A_i$ 와 $f_i$ 는 convex)에 대해 생각해보자.

{\begin{aligned}&{\text{minimize }} \ f_0(A_0x+b_0) \\[0.5ex]&{\text{subject to }} \ f_i(A_ix+b_i)\leq0, \ i=1, ..., m\end{aligned}}

해당 식에 새로운 변수 $y_i=A_ix+b_i$ 를 도입할 경우 다음과 같이 변형된다.

{\begin{aligned}&{\text{minimize }} &&f_0(y_0) \\[0.5ex]&{\text{subject to }} &&f_i(y_i)\leq0, \ i=1,...,m\leq0, \\[0.5ex]& &&A_ix+b=y_i,\ i=0,...,m \end{aligned}}

이 문제의 Lagrangian은 $f_0(y_0)+\Sigma_{i=1}^m\lambda_if_i(y_i)+\Sigma_{i=0}^m\nu_i^T(A_ix+b_i-y_i)$ 로 표현된다. 이때, $x$ 에 대한 infimum이 $-\infin$ 이 되지 않으려면 $\Sigma_{i=0}^m A^T_i\nu_i=0$ 이어야 한다. 따라서 다음과 같은 식 정리가 가능하다.

\begin{aligned} &g(\lambda, \nu_0, ..., \nu_m)\\ &= \sum_{i=0}^m \nu_i^Tb_i + \inf_{y_0, ..., y_m} (f_0(y_0)+ \sum_{i=1}^m \lambda_i f_i(y_i)-\sum_{i=0}^m \nu_i^Ty_i) \\ &= \sum_{i=0}^m \nu_i^Tb_i + \inf_{y_0} (f_0(y_0) - \nu_0^Ty_0)+ \sum_{i=1}^m \lambda_i \inf_{y_i}(f_i(y_i)-(\nu_i/\lambda_i)^Ty_i) \\ &= \sum_{i=0}^m \nu_i^Tb_i -f_0^*(\nu_0)- \sum_{i=1}^m \lambda_i f_i^* (\nu_i/\lambda_i) \end{aligned}

이때의 dual problem은 다음과 같이 정리된다.

{\begin{aligned}&{\text{maximize }} \ \sum_{i=1}^m\nu_i^Tb_i-f_0^*(\nu_0)-\sum_{i=1}^m\lambda_if_i^*(\nu_i/\lambda_i) \\[0.5ex]&{\text{subject to }} \ \lambda\geq0,\ \sum_{i=0}^mA^T_i\nu_i=0 \end{aligned}}

2. Transforming the objective

앞서 교재 4.1.3장에서, objective function $f_0$ 를 이에 대한 increasing function으로 대체하여도 original problem과 equivalent하다는 사실을 다뤘다. 그러나 이 두 문제에 대한 dual은 매우 다르게 정의된다.

{\begin{aligned}&{\text{minimize }}\ ||Ax-b|| \end{aligned}}

다음과 같은 문제에 새로운 변수 $y=Ax-b$ 를 도입하고 $y$ 에 대한 증가 함수로 objective function을 대체한다면, 아래와 같이 표현할 수 있을 것이다. 이 문제는 original problem과 equivalent하다.

{\begin{aligned}&{\text{minimize }} \ (1/2)||y||^2 \\[0.5ex]&{\text{subject to }} \ Ax-b=y \end{aligned}}

이제 각 problem에 대한 dual을 도출해보자.

\begin{aligned} &L(x, y, \nu) = \lVert y \rVert + \nu^T(b+y-Ax)\\ &g(\nu) = \inf_y(\lVert y \rVert + \nu^Ty) + \nu^Tb - \inf_x(A^T\nu x)\\ \end{aligned}

이때 $A^T\nu=0$ 이 성립하면 dual function은 $g(\nu)=b^T\nu - f^*(\nu)$ 가 된다. Conjugate function $f^*(\nu)$ 의 dual norm이 1보다 같거나 작으면 0이 되고, 그렇지 않으면 무한대의 값을 가지므로 첫 번째 문제의 dual problem은 아래와 같다.

{\begin{aligned}&{\text{maximize }} \ b^T\nu\ \\[0.5ex]&{\text{subject to }} \ f^*(\nu) = 0, \ A^T\nu = 0\end{aligned}}

이번엔 두 번째 문제의 dual problem을 구해보자.

\begin{aligned} &L(x, y, \nu) = (1/2)\lVert y \rVert^2 + \nu^T(y-Ax+b)\\ &g(\nu) = \inf_{x,y}((1/2)\lVert y \rVert + \nu^Ty - \nu^TAx + b^T\nu)\\ \end{aligned}

$A^T\nu=0$ 가 안된다면 unbounded below가 되므로 $A^T\nu=0$ 가 보장되어야 한다. 따라서 이를 dual function에 대입하여 정리하면 아래와 같다.

g(\nu)= \begin{cases} b^T\nu + \inf_y((1/2)\lVert y \rVert^2 + \nu^Ty) \quad \text{if} \ \ A^T\nu=0 \\ -\infty \quad \text{otherwise} \end{cases}

이때 $\inf_y((1/2)\lVert y \rVert^2 + \nu^Ty)$ 를 conjugate 형태인 $(-f^*(\nu))$ 로 대체할 수 있으며 norm의 conjugate function이 dual norm임을 고려했을 때 다음과 같이 식이 정리된다.

{\begin{aligned}&{\text{maximize }} \ -(1/2)||\nu||^2_*+b^T\nu \\[0.5ex]&{\text{subject to }} \ A^T\nu=0 \end{aligned}}

즉 첫번째 문제의 dual problem과 두번째 문제의 dual problem이 다른 것을 확인할 수 있다.

3. Implicit constraints

마지막으로, explicit constraints를 objective function의 domain에 대한 implicit constraints로 표현하는 예시를 다뤄보자. 명시적으로 표현된 조건이 objective function 안에 내장되도록 objective function을 재표현함으로써 dual problem을 단순화하는 것이다.

{\begin{aligned}&{\text{minimize }} &&c^Tx \\[0.5ex]&{\text{subject to }} &&Ax=b \\[0.5ex]& &&l\preceq x\preceq u \end{aligned}}

이와 같은 문제의 dual은 원래 다음과 같이 정의된다.

{\begin{aligned}&{\text{maximize }} &&-b^T\nu - \lambda_1^T u + \lambda_2^Tl \\[0.5ex]&{\text{subject to }} &&A^T \nu + \lambda_1 - \lambda_2 + c=0 \\[0.5ex]& && \lambda_1 \succeq 0, \ \lambda_2 \succeq 0 \end{aligned}}

그러나 inequality constraint를 없애고 이를 objective function이 함축(?)할 수 있도록 표현한다면,

{\begin{aligned}&{\text{minimize }} \ f_0(x) \\[0.5ex]&{\text{subject to }} \ Ax=b \\ &f_0(x)= \begin{cases} c^Tx \quad l\preceq x\preceq u\\ \infty \quad \text{otherwise} \end{cases} \end{aligned}}

다음과 같은 형태로 정리될 것이다. 이 문제는 original problem과 equivalent하다. 다만 해당 문제의 dual은 원 문제의 dual과 상당히 다른 형태를 띈다.

\begin{aligned} g(\nu) &= \inf_{l\preceq x\preceq u}(c^Tx+\nu^T(Ax-b) \\ &= -b^T\nu - u^T(A^T\nu+c)^{-} + l^T(A^T\nu+c)^{+} \end{aligned}

위의 식에서 $(A^T\nu+c)^{+} = max\left\{(A^T\nu+c), 0\right\}$ , $(A^T\nu+c)^{-} = max\left\{(-A^T\nu-c), 0\right\}$ 이다. 최종적으로 도출되는 dual problem은 아래와 같다.

{\begin{aligned}&{\text{maximize }}\ -b^T\nu -u^T(A^T\nu +c)^{-} + l^T(A^T\nu +c)^{+} \end{aligned}}

Box constraint를 objective function의 바운더리로 넣어버리면서 기존 식보다 조건이 오히려 줄어들었다. 다양한 최적화 문제 풀이에 이러한 방법을 유용하게 사용할 수 있을 것이다.

4. Weak alternatives

현실의 문제들을 다루는 데에 있어서 가장 중요한 것 중 하나가 바로 feasibility이다. 우리는 이 feasibility 여부를 알아내기 위한 방법으로써 alternatives의 개념에 대해 다뤄볼 것이다.

Weak alternative : 두 inequality system 중 많아봐야 한 개의 inequality system만 feasible하다. 즉, 둘다 feasible할 수 는 없다는 것을 의미한다.

아래의 식처럼 제약을 설정할 때, constraint $f$ 와 $h$ 를 만족하는 영역이 항상 존재한다고 가정하였다.

f_i(x)\le0, \quad i=1, ..., m \quad h_i(x)=0, \quad i=1, ..., p \quad \quad (A)

이제 feasibility의 확인을 위해 다음과 같이 목적함수가 0인 문제를 정의해보자.

{\begin{aligned}&{\text{minimize }} &&0 \\[0.5ex]&{\text{subject to }} &&f_i(x)\le0, \quad i=1, ..., m \\[0.5ex]& &&h_i(x)=0, \quad i=1, ..., p \end{aligned}}

만약 (A)가 feasible 하다면 $p^*$ 값은 0이 되고, 그렇지 않다면 $\infty$ 을 가진다. 이때의 dual function $g(\lambda, \nu) = \inf_{x\in D} (\sum_{i=1}^m\lambda_i f_i(x)+\sum_{i=1}^p\nu_i h_i(x))$ 은 positive homogeneous하기 때문에 아래와 같은 형태의 $d^*$ 값을 가진다.

d^*= \begin{cases} \infty & \lambda\succeq0\;,\; g(\lambda, \nu)>0 \; \ \text{is feasible}\\ 0 & \lambda\succeq0\;,\; g(\lambda, \nu)>0 \; \ \text{is infeasible} \end{cases}

(B)를 다음과 같이 정의하자.

\quad \lambda\succeq0\;,\; g(\lambda, \nu)>0 \quad (B)

우리는 만약 (B)가 feasible 하다면 (A)는 infeasible함을 알 수 있다. (B)가 feasible 하면 $d^*$ 는 무한대로 정의되며, weak duality $p^* \geq d^*$ 에 의해 $p^*$ 도 무한대가 되어야한다. 이때 $p^*$ 가 무한대인 경우는 (A)가 not feasible한 경우이다. 반대로 (A)가 feasible 하다면 $p^*$ 는 0이 되고, $d^*$ 도 0이 되어 (B)는 infeasible 하다.

이러한 식 (A)와 (B)를 weak alternatives라고 부르며, 둘 중 최대 하나의 식만 feasible한 관계라고 볼 수 있다. Weak alternatives 하에서 우리는 하나의 system의 feasibility를 보임으로써 나머지 system의 infeasibility를 증명할 수 있다.

이번에는 등호가 빠진 Strict inequality의 case를 살펴보자.

f_i(x) <0, \ \ i=1, ..., m \ \ \ \ h_i(x)=0, \ \ i=1, ..., p \quad (A)

이때의 weak alternatives는 아래와 같다.

\quad \lambda\succeq0,\; \lambda \ne0,\; g(\lambda, \nu)\ge0 \quad (B)

두 식이 weak alternatives 임은 간단히 증명할 수 있다. 첫 번째 식이 feasible 하고 $\lambda$ 역시 조건을 만족한다고 가정하면 $L = \lambda_1f_1( \tilde{x}) + \cdots + \lambda_mf_m( \tilde{x})+\nu_1h_1( \tilde{x}) + \cdots + \nu_mh_m( \tilde{x})<0$ 가 항상 성립한다.

\begin{aligned} g(\lambda, \nu) &= \inf_{x\in D}(\sum_{i=1}^m\lambda_i f_i(x)+\sum_{i=1}^p\nu_i h_i(x)) \\ &\le \sum_{i=1}^m\lambda_i f_i(\tilde{x})+\sum_{i=1}^p\nu_i h_i(\tilde{x}) \\ &<0 \end{aligned}

그러나 위의 결과가 (B)와 모순되는 것을 확인할 수 있다.

5. Strong alternatives

Weak alternatives 관계에서의 두 식은 모두 infeasible할 수도 있다. Strong alternatives는 여기서 한 단계 더 나아가, 둘 중 하나는 반드시 feasible, 나머지 하나는 반드시 infeasible한 관계를 의미한다.

Strong alternative : Inequality system이 feasible 하다면, 그것의 alternative inequality system은 반드시 infeasible하다.

다음의 조건들을 만족하는 convex한 original inequality system에서 (마지막 조건은 $Ax=b$ 의 해가 $D$ space에 있음을 의미한다) 아래의 식들은 strong alternative을 만족한다. 이는 Slater’s condition과 strong duality를 이용해 보일 수 있다.

$f_i$ 가 convex
$h_i$ 가 affine
$x \in relint \;D \quad \text{with} \; Ax=b$

Strict inequality

\begin{aligned} &f_i(x)<0, \quad i=1, ..., m, \quad Ax=b \quad \quad (A) \\ &\lambda\succeq0\ , \quad \lambda \neq 0, \quad g(\lambda, \nu) \ge0 \quad \quad (B) \end{aligned}

Non-strict inequality

(A)와 (B), (C)와 (D)는 strong alternative 쌍으로 둘 중 하나만 feasible 하다.

Farkas’ lemma

\begin{aligned} &Ax \preceq0, \quad c^Tx<0 \quad \quad (E) \\ & A^Ty+c=0, \quad y \succeq0 \quad \quad (F) \end{aligned}

마지막으로 살펴볼 Farkas' lemma는 Strict + Non-strict inequalities 가 혼합된 Strong alternative의 예시이다. LP duality를 이용해 증명해보일 수 있다.

경제학적 쓰임새를 알아보자. $p$ 를 투자 당시의 가격, $x$ 를 투자자의 포트폴리오 목록이라고 하자. 그리고 $v^Tx$ 를 특정 시점 이후의 자산가치라고 정의하자. 포트폴리오 구성을 위해 초기 비용이 발생하므로, 이를 $p^Tx<0$ 이라고 설정할 수 있다. 모든 상황에서 특정 시점 이후의 자산가치가 늘어나는 경우는 일반적으로 불가능하다고 가정 (no Arbitrage) 하므로, 이를 inequality system으로 간략히 표현하면 아래와 같다.