6. 对偶与对偶问题

Duality

0. 前言

• 主要记录了对偶问题和对偶方法。由于强对偶性下对偶问题的解与原问题相等，许多问题在原函数性质不好的情况下可以变换到对偶空间去求解。
• Why duality? 降低计算复杂度，数据降维等；更好的性质，更光滑、凸。。

1. Lagrangian

• Standard form problem:

  minimize $f_0(x)$

  subject to $f_i(x)\leq 0, i=1,\cdots,m, h_i(x)=0,i=1,\cdots,p$

• Lagrangian:

  $$L(x,\lambda,\nu)=f_0(x)+\sum^m_{i=1}\lambda_if_i(x)+\sum^p_{i=1}\nu_ih_i(x)$$

$\lambda,\nu$ 分别是不等式约束和等式约束的拉格朗日乘子

2. Lagrangian Dual

$$g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu)$$

因为 $\inf$ 的存在，且 $L$ 是关于 $\lambda,\nu$ 的仿射函数，对偶函数一定凸且构成了原问题最优值 $p^\star$ 的下界 $g(\lambda,\nu)\leq p^\star$

3. Lagrange dual and conjugate function

• minimize $f_0(x)$

  subject to $Ax\preceq b, Cx=d$

  $$\begin{align} g(\lambda,\nu)&=\inf_{x\in\textbf{dom}f_0}(f_0(x)+(A^T\lambda+C^T\nu)^Tx-b^T\lambda-d^T\nu)\\ &=-f_0^*(-A^T\lambda-C^T\nu)-b^T\lambda-d^T\nu \end{align}$$

4. The dual problem

• maximize $g(\lambda,\nu)$

  subject to $\lambda \succeq 0$

  finds best lower bound of $p^\star$_

5. Weak and strong duality

• weak duality: $d^\star\leq p^\star$

  always holds for convex and nonconvex problems

• strong duality: $d^\star=p^\star$

  Slater’ constraint qualification:

  $$\exists x\in \textbf{int}D: f_i(x)<0, i=1,\cdots,m$$

Slater条件成立即不等式约束可以取严格小于，强对偶性成立。 Slater条件确保拉格朗日函数存在鞍点(参见拉格朗日对偶的鞍点解释，即 $x^\star,\lambda^\star$ 最优且强对偶性成立，则其为 $L$ 的鞍点)

6. A nonconvex problem with strong duality

对非凸问题也可能存在强对偶条件

无论 $x$ 的维数($x\in \mathcal{R}^n$ )，其对偶问题总是针对 $\lambda\in \mathcal{R}$ 的一维优化。这是个很好的性质，可以直接使问题降维。

7. Geometric interpretation

$$g(\lambda)=\inf_{(u,t)\in G}(t+\lambda u)$$

where $G={(f_1(x),f_2(x))\mid x\in D}$

原问题可行集在左半侧(Slater条件)；超平面 $\lambda u+t=g(\lambda)$ 与 $t$ 的交点永远在 $p^*$ 的下边。此处 $\lambda$ 作为自变量变换超平面的”斜率”，取与G相切之后（inf保证相切）与t轴焦点即为 $g(\lambda)$ 。无论怎么交，最优点（最大的 $g(\lambda)$ ）总在 $p^\star$ 下部。

(弱对偶条件 $d^<p^$)

• Epigraph variation:

令 $A$ 为G的上境图，强对偶性成立当$p^\star$ 处可以作非垂直（于坐标轴u）的支撑超平面。

上图G非凸；如果G凸（即对于凸问题），过 $(0,p^\star)$ 可以作支撑超平面。

此时Slater’s condition: 如果存在 $(\tilde{u},\tilde{t})\in A$ 且 $\tilde{u}<0$ ，$(0,p^\star)$ 点的支撑超平面必然不垂直。

8. Complementary slackness

• assume strong duality holds, $x^\star$ optimal and $(\lambda^\star,\nu^\star)$ dual optimal

  obviously we have:

  $$\begin{align} f_0(x^\star)=g(\lambda^\star,\nu^\star)&=\inf_x\{f_0(x)+\sum\lambda_i^\star f_i(x)+\sum\nu_i^\star h_i(x)\}\\ &\leq f_0(x^\star)+\sum\lambda_i^\star f_i(x^\star)+\sum\nu_i^\star h_i(x^\star)\\ &\leq f_0(x^\star) \end{align}$$
  • First inequality: $x^\star$ minimize $L(x,\lambda^\star,\nu^\star)$
  • $\sum \lambda_i^\star f_i(x^\star)=0$

第二个条件即 complementary slackness 互补松弛性，即最优点处除非第i个约束起作用，否则最优拉格朗日乘子的第i项都为零。

9. KKT Condition

• For non-convex problem, if strong duality holds, i.e. $x^\star$ minimize $L(x,\lambda^\star,\nu^\star)$ , so its gradient at $x^\star$: $$\triangledown f_0(x^\star)+\sum \lambda^\star_i\triangledown f_i(x)+\sum\nu^\star_i\triangledown h_i(x)=0$$ so we have KKT condition: $$\begin{align} f_i(x^\star)&\leq 0 \text{ primal constraints}\\ h_i(x^\star)&=0 \\ \lambda^\star_i&\geq 0 \text{ dual constraints}\\ \lambda^\star_if_i(x^\star)&=0\text{ complementary slackness}\\ \triangledown f_0(x^\star)+\sum \lambda^\star_i\triangledown f_i(x)+\sum\nu^\star_i\triangledown h_i(x)&=0 \text{ gradient vanish} \end{align}$$

KKT条件由强对偶性下的非凸问题导出，即在非凸问题中，原问题和对偶问题的一堆最优解必须满足KKT条件(必要条件) 。

（原问题可行性、对偶问题可行性、互补松弛性、最优性）

若原问题为凸，必要条件变为充要条件，满足KKT条件的点是最优解且对偶间隙为零(强对偶)。对于还未知是否满足强对偶性的凸问题，需要满足 Slater 条件。

10. Example

$\underset{y}{\min} \frac{1}{2}|x-y|^2_2$， $s.t. |x|_1=1$

待补充

11. LP, SDP, SOCP Duality

待补充