Duality

Boyd , Convex Optimization을 일부 정리한 내용입니다.

---

The Lagrangian

Lagrangian $L: R^n \times R^m \times R^p \rightarrow R$은 domain이 unconstrained 되어 있다.

$$L(x,\lambda,\nu)= f_0(x) + \sum\limits^m_{i=1}\lambda_i f_i(x) + \sum\limits^p_{i=1}\nu_i h_i (x)$$

The Lagrange dual function

Dual function은 $g:R^m\times R^p \rightarrow R$인 함수이다. Dual function의 domain도 unconstrained 이다.

$$g(\lambda,\nu) = \inf_{x\in\mathcal{D}}L(x,\lambda,\nu)=\inf_{x\in\mathcal{D}} f_0(x) + \sum\limits^m_{i=1}\lambda_i f(_i(x) + \sum\limits^p_{i=1}\nu_i h_i(x)$$

Example 1 ( Lagrange Dual of Standard LP )

\begin{align} \text{minimize}\quad & c^Tx \\ \text{subject to}\quad &Ax=b \\ & x\succeq 0 \end{align}

이 때 Lagrangian 은 $L(x,\lambda,\nu) = -b^T\nu + (c+A^T\nu - \lambda)^Tx$이고

dual function은 $g(\lambda,\nu) = \inf_x L(x,\lambda,\nu)=-b^T\nu + \inf_x (c+A^T\nu-\lambda)^T x$ 이다.

$c+A^T\nu-\lambda \neq 0$ 이 아니면 $g(\lambda,\nu)=-\infty$이다.

 

Weak Duality

Dual function은 $\lambda,\nu$에 대해 concave함을 알 수 있다. Any feasible $\tilde{x}$에 대해

$$ g(\lambda,\nu) = \inf_{x\in\mathcal{D}}L(x,\lambda,\nu) \leq L(\tilde{x},\lambda,\nu) \leq f_0(\tilde{x})$$ 임을 알 수 있다.

따라서 이 때 lower bound의 maximum을 구하는 것을 Largange dual probelm 이라고 한다.

\begin{align} &\text{max} \quad  g(\lambda,\nu)\\ & \text{subject to} \quad \lambda \succeq 0 \end{align}

이 때 $\lambda \succeq 0$ 하고 $g(\lambda,\nu) > -\infty$인 경우 dual feasible하다고 한다.

weak duality ( $p^* \geq d^*$) 가 성립함을 알 수 있다.

 

Strong Duality

$d^*=p^*$일 때 strong duality가 성립한다고 한다.

convex primal과 convex inequality와 affine equality constraint 인 problem에 대해 Slater's condition이 성립할 때, strong duality가 성립함을 알 수 있다.

Weak Duality via set of values

$$\mathcal{G}= \{(f_1(x),\dots,f_m(x),h_1(x),\dots,h_p(x),f_0(x))\in \mathbb{R}^m \times \mathbb{R}^p \times \mathbb{R} \mid x\in \mathcal{D}   \}$$

The primal optimal value $p^* = \inf \{t \mid (u,v,t) \in \mathcal{G} , u \preceq 0, v=0\}$

We express the dual as 

$$g(\lambda,\nu) = \inf_t \{ (\lambda,\nu,1)^T (u,v,t) \mid (u,v,t) \in \mathcal{G} \}$$

이 때 $g(\lambda,\nu)$는 $\mathcal{G}$의 supporting hyperplane이 됨을 알 수 있다.

이제 $\mathcal{G}$의 epigraph를 생각해보자.

$$\mathcal{A}= \{(u,v,t)\mid \exists{x} \in \mathcal{D}, f_i(x) \leq u_i,h_i(x)=v_i,f_0(x)\leq t \}$$

Proof of strong duality under Slater's condition

$\mathcal{B}=\{ (0,0,s) \in \mathbb{R}^m \times \mathbb{R}^p \times \mathbb{R} \mid s<p^* \}$

$\mathcal{A}$와 $\mathcal{B}$ 모두 convex set이기 때문에 separating hyperplane이 존재한다. 이를

$$(u,v,t)\in \mathcal{A} \rightarrow \tilde{\lambda}^Tu + \tilde{\nu}^Tv + \mu t \geq \alpha$$

$$(u,v,t)\in \mathcal{B} \rightarrow \tilde{\lambda}^Tu + \tilde{\nu}^Tv + \mu t \leq \alpha$$

이 때 $\mathcal{A}$에 속한 $(u,t)$는 무한히 커질 수 있으므로 $\lambda \succeq 0,\mu \geq 0$이여야 된다. 

$\sup\mathcal{B}$를 생각하면, $\mu p^* \leq \alpha$임을 알 수 있다.

따라서 any $x\in\mathcal{D}$에 대해 $\sum\limits^m_{i=1}\tilde{\lambda}_i f_i(x) + \tilde{\nu}^T (Ax-b) + \mu f_0(x) \geq \alpha \geq \mu p^*$가 성립함을 알 수 있다.

Optimality Condition

Suppose 

$f_0 (x^*) = g( \lambda^*,\nu^*)\leq \inf_x (f_0(x) + \sum\limits^m_1 \lambda^*_i f_i (x) + \sum\limits^p_1 \nu_i^* h_i(x) ) \leq f_0 (x^*) + \sum\limits^m_1 \lambda^*_i f_i (x^*) + \sum\limits^p_1 \nu^*_i h_i (x^*) \leq f_0 (x^*) $

The equality holds when $\lambda^* f_i (x^*)=0$ which is complementary slackness.

어떤 optimization problem with differentiable objective and constraint function 에 대해 strong duality 가 obtain되면 이 때 primal and dual optimal point들은 KKT condition을 만족시켜야 한다.

Primal problem이 convex라면 kkt 조건을 만족시키면 strong duality가 성립한다.

또한 convex optimization with slater's condition 과 같이 storng duality를 만족시키는 경우, kkt 조건을 만족한다.

즉, kkt 조건이 optimality를 위한 necessary and sufficient conditon 이 된다.