[Week 5] Duality [4]

ESC·2023년 12월 13일

2023-Winter

목록 보기

10/10

Duality에 대한 마지막 포스트에서는 Lagrange duality를 Generalized inequality constraint를 가진 문제로 확장하고자 한다. 포스트를 읽기에 앞서, 시리즈의 초반부에 등장하는 proper cone의 개념에 대해 간단하게 복습하고 넘어오는 것이 도움이 된다. 본 포스트에서 우리는 기본적으로 아래와 같은 optimization problem을 정의한다.

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

이때 $K_i \subseteq R^{K_i}$ 는 proper cone이며, domain $\mathcal{D}$ 가 nonempty 하다고 가정한다.

1. The Lagrange dual

위 최적화 문제에 대한 라그랑지안 및 dual function은 아래와 같이 정의된다.

L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^p\lambda_i^Th_i(x) + \sum_{i=1}^m\nu_i^Tf_i(x) \\ g(\lambda, \nu) = \inf_{x\in D}L(x, \lambda, \nu) = \inf_{x\in D} \ \{ f_0(x) + \sum_{i=1}^p\lambda_i^Th_i(x) + \sum_{i=1}^m\nu_i^Tf_i(x) \}

이는 앞서 살펴봤던 기본적인 문제들과 크게 다르지 않다. 라그랑지안이 dual variables $(\lambda, \nu)$ 에서 affine하고, dual function이 라그랑지안의 pointwise infimum이므로 concave하며 $p^*$ 에서 lower bound를 갖는다. 이때 Nonnegativity의 유지를 위해, scalar inequalities의 $\lambda_i \ge 0$ 의 조금 더 확장된 형태인 $\lambda_i \succeq_{K_i^*}0$ 를 requirement로 갖는다.

Nonnegativity requirement $\lambda_i \succeq_{K_i^*}0$ 와 generalized inequality constraint인 $f_i(x)\preceq_{K_i} 0$ 가 주어졌다. 이제 dual cone의 정의를 떠올려보자.

K^* = \{y|x^Ty \ge 0 \; \text{for all} \; x\in K\}

따라서 $\lambda^Tf_i(\tilde{x})\le0$ 이 성립하고, 이에 따라 $f_0(\tilde{x}) + \sum_{i=1}^p\lambda_i^Th_i(\tilde{x}) + \sum_{i=1}^m\nu_i^Tf_i(\tilde{x})\le f_0(\tilde{x})$ 이 만족되어 weak duality인 $g(\lambda, \nu)\le p^*$ 가 얻어진다. Dual problem은 다음과 같이 정리된다.

\begin{aligned} &\text{maximize} \quad g(\lambda, \nu)\\ &\text{subject to} \quad \lambda_i \succeq_{K_i^*}0, \quad i=1, ..., m \end{aligned}

나아가 primal problem이 convex하고 적절한 constraint 조건을 만족해야 strong duality ( $d^*=p^*$ )가 충족된다. 예를 들어 아래와 같은 generalized version의 Slater’s condition을 만족해야 한다.

x \in \ relint D \quad \text{with} \quad Ax=b \quad \text{and} \quad f_i(x)\prec_{K_i}0, \quad i=1, .., m.

해당 조건을 만족하면서 dual optimum이 얻어진다면 strong duality가 만족된다.

2. Optimality conditions

Strong duality와 관련된 조건들을 계속해서 살펴보자.

Complementary slackness

Scalar inequality의 경우와 크게 다르지 않다. Strong duality가 성립한다면 아래의 식 역시 성립한다.

\begin{aligned} f_0(x^*) &=g(\lambda^*, \nu^*) \\ &\le f_0(x^*) + \sum_{i=1}^m \lambda_i^* f_i(x^*) + \sum_{i=1}^p \nu_i^* h_i(x^*) \\ &= f_0(x^*) \end{aligned}

따라서 위의 식을 만족하기 위해서는 아래와 같은 조건이 필요하다.

{\lambda_i^*}^T f_i(x^*) = 0

결과적으로 complementary slackness는 아래의 3가지 경우에 만족될 수 있다.

\begin{aligned} &(1) \ \lambda_{i}^{*T}f_i(x^*)=0, i=1,...,m \\ &(2) \ \lambda_{i} \succ_{K_{i}^*} 0 \Longrightarrow f_i(x^*)=0 \\ &(3)\ f_i(x^*) \prec_{K_{i}}0, \Longrightarrow\lambda_{i}^*=0 \end{aligned}

이때 scalar inequality case와 달리 $\lambda_i^* \neq 0$ 이고 $f_i(x^*) \neq 0$ 일 때도 식이 성립할 수 있다.

KKT condition

$f_i$ , $h_i$ 가 모두 미분 가능하다고 가정해보자. 그렇다면 complementary slackness로부터 $x^*$ 가 라그랑지안을 최소화함을 알 수 있다.

\triangledown f_0(x^*) + \sum_{i=1}^m Df_i(x^*)^T \lambda_i^*  + \sum_{i=1}^p \nu_i^* \triangledown h_i(x^*) =0

Generalized Inequality 하에서 strong duality가 만족된다면 아래의 5가지 조건인 KKT condition이 만족되어야 한다.

{\begin{aligned} &f_i(x^*)\preceq _{K_i} 0, \ i=1, ..., m &&(1) \\[1.0ex]&h_i(x^*)=0, \ i=1, ..., p &&(2) \\[1.0ex] &\lambda_i^* \succeq_{K_i^*} 0, \ i=1, ..., m &&(3) \\[1.0ex] &{\lambda_i^*}^T f_i(x^*)=0, \ i=1, ..., m &&(4) \\ &\nabla f_0(x^*)+\sum_{i=1}^m D\lambda_i^* + \sum_{i=1}^p \nu_i^* \nabla h_i(x^*)=0 &&(5) \end{aligned}}

3. Perturbation and sensitivity analysis

기존의 문제와 달리, 제약조건에 $u_i, \ v_i$ 를 집어 넣는 것을 perturbation이라 한다.

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

Perturbed problem에서의 optimal value는 $p^*(u, v)$ 로 표현된다. 이때 inequality constraint의 $u_i$ 가 양수라면 relaxed, 음수라면 tightened인 상태라고 칭하며, original problem의 optimal value는 $p^*(0, 0)$ 이다. 만약 original problem이 convex하고 slater’s condition이 만족된다면 다음의 부등식이 성립한다.

p^*(u, v) \ge p^*(0 ,0)- {\lambda^*}^T u- {\nu^*}^Tv

이에 대한 증명은 아래를 참고하라.

\begin{aligned} p^*(0, 0) &= g(\lambda^*, \nu^*) \\ &\le f_0(x) + \sum_{i=1}^m \lambda_i^{*T} f_i(x) + \sum_{i=1}^p \nu_i^{*T} h_i(x) \\ &\le f_0(x) +\lambda^{*T} u + \nu^{*T} v \end{aligned}

따라서 $f_0(x)\ge p^*(0, 0) -\lambda^{*T} u - \nu^{*T} v$ 이 성립하며, 이는 $p^*(u, v)$ 의 하한을 제시해준다. 이때 만약 $\lambda_i^*$ 가 크고 i 번째 제약 조건이 tightened 되었다면 optimal value인 $p^*(u, v)$ 는 크게 증가한다. 이와 같은 변화에 대한 분석을 Sensitivity analysis라고 칭한다. 만약 $p^*(u, v)$ 가 $u=0, \ v=0$ 에서 미분 가능하다면 아래의 식이 성립한다.

\lambda_i^{*} = -{\partial p^*(0, 0)\over\partial u_i}, \quad \nu_i^{*} = -{\partial p^*(0, 0)\over\partial v_i}

이에 대한 해석을 정리해보자.

$u_i \ \text{tightened \& small}$ → $p^*$ increase of $-\lambda_i ^* u_i$
$u_i \ \text{lossen \& small}$ → $p^*$ decrease of $\lambda_i ^* u_i$
$\lambda_i^* \ \text{small}$ → constraint가 optimal value에 영향을 미치는 부분이 작다
$\lambda_i^* \ \text{big}$ → constraint가 optimal value에 영향을 미치는 부분이 크다

이러한 perturbation은 generalized inequality 하에서도 성립되며, 그 기본적인 형태는 다음과 같다.

{\begin{aligned}&{\text{minimize }}_x &&f_0(x) \\[0.5ex]&{\text{subject to }} &&f_i(x)\preceq_{K_i} u_i, \quad i=1, ..., m \\[0.5ex]& &&h_i(x)=v_i, \quad i=1, ..., p\end{aligned}}

마찬가지로 zero duality gap 하에서는 $p^*(u, v) \ge p^*- \sum_{i=1}^m {\lambda_i^*}^T u_i -{\nu^*}^Tv$ 가 성립하며, 미분 가능한 조건 내에서 $\lambda_i^*= -\nabla_{u_i} p^*(0, 0)$ 역시 만족된다.

4. Theorems of alternatives

기존의 Theorems of alternatives에 generalized inequality를 적용하여 이를 확장해보자.

Weak alternatives

\begin{aligned} &f_i(x) \preceq_{K_i} 0, \quad i=1, ..., m, \quad h_i(x)=0, \quad i=1, ..., p \quad \quad (A) \\ &\lambda_i \succeq_{K_i}0\ , \quad i=1, ..., m, \quad g(\lambda, \nu) >0 \quad \quad (B) \end{aligned}

$(A)$ 와 $(B)$ 는 동시에 동시에 feasible할 수 없으므로, 위 둘은 weak alternatives이다. 증명을 위해서는 둘 다 feasible 하다고 가정했을 때 $0<g(\lambda, \nu) \le \sum_{i=1}^m \lambda_i^T f_i(x) + \sum_{i=1}^p \nu_i h_i(x) <0$ 의 모순이 발생함을 보이면 된다.

\begin{aligned} &f_i(x) \prec_{K_i} 0, \quad i=1, ..., m, \quad Ax=b \quad \quad (C) \\ &\lambda_i \succeq_{K_i}0\ , \quad i=1, ..., m, \quad \lambda \neq0, \quad g(\lambda, \nu) \ge0 \quad \quad (D) \end{aligned}

마찬가지로 $(C)$ 와 $(D)$ 역시 weak alternatives의 관계를 가진다.

Strong alternatives

만약 $\tilde{x}\in relint D \ \ \text{satisfying} \ \ A\tilde{x}=b$ 가 존재한다고 (즉 slatter’s condition을 만족) 가정하고 아래와 같은 문제를 고려해보자.

{\begin{aligned}&{\text{minimize}} &&s \\[0.5ex]&{\text{subject to }} &&f_i(x) \preceq_{K_i} se_i, \quad i=1, ..., m \\[0.5ex]& && Ax=b \\[0.5ex] &\text{where} &&e_i \succ_{K_i} 0, \quad x, s \in R \end{aligned}}

위 문제의 dual problem은 아래와 같다.

{\begin{aligned}&{\text{maximize}} &&g(\lambda, \nu) \\[0.5ex]&{\text{subject to }} &&\lambda \succeq_{K_i} 0, \quad i=1, ..., m \\[0.5ex]& && \sum_{i=1}^m e_i^T \lambda_i=1 \end{aligned}}

앞서 등장한 $(C)$ 와 $(D)$ 를 다시 보자. $(C)$ 가 infeasible할 경우 $-f_i(x)\notin \;intK_i \to -\lambda^Tf_i(x)\le0$ 이므로 $\lambda^T(se_i-f_i(x))\ge0 \to s\ge0$ 가 만족되고, slater’s condition에 의해 $d^*=p^*$ 를 만족하는 $\tilde{\lambda}, \ \tilde{\nu}$ , $d∗ = p∗ ≥ 0$ 를 만족하는 $\tilde{\lambda}, \ \tilde{\nu}$ 가 존재한다. 따라서 $(D)$ 는 infeasible하다. 마찬가지로 $(C)$ 가 feasible 하다면 $(D)$ 는 infeasible하므로, 둘은 strong alternative의 관계이다.

\begin{aligned} &f_i(x) \preceq_{K_i}0, \quad i=1, ..., m \quad Ax=b \quad \quad (E) \\ &\lambda_i \succeq_{K^*_i}0, \quad i=1, ..., m, \quad g(\lambda, \nu)>0 \quad \quad (F) \end{aligned}

Primal problem이 convex이고 $\tilde{x}\in relint D \ \ \text{satisfying} \ \ A\tilde{x}=b$ 가 존재하며 optimal value가 얻어진다면, 두 부등식은 strong alternatives이다.

ESC

@Yonsei University

이전 포스트