凸优化学习笔记（四）：对偶性、KKT 条件、敏感性分析

四、对偶性

定义

原问题 P (Primal Problem)：

$x\in R^n,D=\bigcap^m_{i=1}dom(f_i)\cap\bigcap^p_{i=1}dom(h_i)$

$$ \begin{aligned} \min \ & f_0(x) \\ s.t. \ & f_i(x)\leq 0, i=1,...,M \\ & h_i(x)=0,i=1,...,P \end{aligned} $$

拉格朗日函数 (Lagrangian Function / Lagrangian)：

$\lambda、v$ 为拉格朗日乘子 (Lagrange Multiplier / Multiplier)

$$ L(x,\lambda,v)=f_0(x)+\sum\limits_{i=1}^m \lambda_i f_i(x)+\sum\limits_{i=1}^p v_i h_i(x) $$

拉格朗日对偶函数 (Lagrange Dual Function / Dual Function)：

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

对偶问题 D (Dual Problem / Lagrange Dual Problem)：

若对偶函数有部分情况为负无穷，则写对偶问题时可以直接忽略负无穷的部分

$$ \begin{aligned} \max \ & g(\lambda,v) \\ s.t. \ & \lambda\geq 0 \end{aligned} $$

对偶函数性质

对偶函数一定是凹函数
$\forall \lambda \geq 0,\forall v,g(\lambda,v)\leq p^*$ ， $p^*$ 为原问题最优值

对偶问题性质

对偶问题一定是凸优化问题
$d^*、p^*$ 分别为对偶问题、原问题的最优值，其中 $d^*\leq p^*$
$\lambda^*、v^*$ 为最优拉格朗日乘子 (Optimal Lagrange Multiplier)

强 / 弱对偶 - 对偶间隙

对偶概念：

弱对偶 (Weak Duality)： $d^*\leq p^*$
强对偶 (Strong Duality)： $d^*=p^*$
对偶间隙 (Duality Gap)： $p^*-d^*$

D 的相对领域 (Relative Interior)：

Relint $D=\{x\in D|B(x,r)\cap aff\ D\leq D,\exists r>0\}$
其中 $aff\ D$ 表示 $D$ 的仿射包， $B(x,r)$ 表示以 $x$ 为中心， $r$ 为半径的小球
D 的相对领域即是去除 D 边缘后的区域

Slater’s Condition (充分条件)：

若有如下凸问题存在，其中 $f_i(x),\forall i$ 为凸，则当 $\exists x\in \text{relint} \ D$ 使 $f_i(x)<0,i=1,…,m,Ax=b$ 满足时， $p^*=d^*$

$$ \begin{aligned} \min \ & f_0(x) \\ s.t. \ & f_i(x)\leq 0,i=1,...,m\\ & Ax=b \end{aligned} $$

A weaker Slater’s Condition：

若不等式约束为仿射时，只要可行域非空，必有 $p^*=d^*$
推论：线性规划问题若有可行解，则 $p^*=d^*$

鞍点的解释 (Saddle Point)：

使得下式成立的 $x^*、\lambda^*$ 即为鞍点

$$ p^*=\inf_{x\in D}\sup_{\lambda\geq 0}L(x,\lambda)=\sup_{\lambda\geq 0}\inf_{x\in D}L(x,\lambda)=d^* $$

鞍点定理：

若 $(\tilde{x},\tilde{\lambda})$ 为 $L(x,\lambda)$ 的鞍点 $\Leftrightarrow$ 强对偶存在，且 $\tilde{x},\tilde{\lambda}$ 为 Primal 与 Dual 最优解

KKT 条件

$$ \begin{aligned} p^*=f_0(x^*)=d^*=&g(\lambda^*,v^*)\\ =&\inf_x\{f_0(x)+\sum\limits_{i=1}^m \lambda_i^* f_i(x)+\sum\limits_{i=1}^p v_i^* h_i(x)\}\\ \leq & f_0(x^*)+\sum\limits_{i=1}^m \lambda_i^* f_i(x^*)+\sum\limits_{i=1}^p v_i^* h_i(x^*) \\ \leq & f_0(x^*) \end{aligned} $$

由此中间的不等号应改为等号，进而推出以下两个条件。

互补松弛条件 (Complementary Slackness)

若 $p^*=d^*$ ，则 $\lambda_i^*f_i(x^*)=0$ ，即如果 $\lambda_i^*>0$ 则 $f_i(x^*)=0$ ；如果 $f_i(x^*)<0$ 则 $\lambda_i^*=0$

稳定性条件 (Stationarity)

$$ \inf_xL(x,\lambda^*,v^*)= \inf_x\{f_0(x)+\sum\limits_{i=1}^m \lambda_i^* f_i(x)+\sum\limits_{i=1}^p v_i^* h_i(x)\}=L(x^*,\lambda^*,v^*) $$

因此 $L(x,\lambda^*,v^*)$ 在 $x^*$ 处取到最小值，即 $x^*$ 处导数为 0，即

$$ \nabla f_0(x^*)+\sum\limits_{i=1}^m \lambda_i^* \nabla f_i(x^*)+\sum\limits_{i=1}^p v_i^* \nabla h_i(x^*)=0 $$

KKT 条件适用范围

KKT 条件从强对偶性质出发进行推导，共得到以下五个条件：

原问题可行性
- $f_i(x^*)\leq 0,i=1,…,m$
- $h_i(x^*)=0,i=1,…,p$
对偶问题可行性
- $\lambda^*\geq 0$
互补松弛条件
- $\lambda_i^* f_i(x^*)=0,i=1,…,m$
稳定性条件

$$ \displaystyle\frac{\partial L(x,\lambda^*,v^*)}{\partial x}|_{x=x^*}=\nabla f_0(x^*)+\sum\limits_{i=1}^m \lambda_i^* \nabla f_i(x^*)+\sum\limits_{i=1}^p v_i^* \nabla h_i(x^*)=0 $$

定理：

对任意问题，若各个函数可微，对偶间隙为零，则 KKT 条件为 $(x^*,\lambda^*,v^*)$ 为最优解时的必要条件
若原问题为凸问题，各个函数可微，对偶间隙为零，则 KKT 条件为充分条件

若原问题为凸问题且满足 Slater 条件，则 KKT 条件为充要条件

KKT 举例

利用共轭函数求解对偶问题

原问题：

$$ \min f_0(A x+b) $$

转换原问题：

$$ \begin{array}{ll} \min & f_0(y) \\ \text { s.t. } & A x+b=y \end{array} $$

定义拉格朗日函数：

$$ L(x, y, v)=f_0(y)+v^{\top}(A x+b-y) $$

求解拉格朗日对偶函数：

若 $A^\top v\not=0$ ，则 $g(v)=-\infty$ ，因此仅考虑 $A^\top v=0$ 时的情况：（其中 $f_0^*$ 为 $f_0$ 为共轭函数）

$$ g(v)=b^{\top} v+\inf _y\left(f_0(y)-v^{\top} y\right)=b^{\top} v-f_0^*(v) $$

得到最终的对偶问题：

$$ \begin{array}{ll} \max & b^{\top} v-f_0^*(v) \\ \text { s.t. } & A^{\top} v=0 \end{array} $$

总结

一般的优化问题（不一定凸）：

若拉格朗日函数 $L(x,\lambda,v)$ 有鞍点 $\Leftrightarrow$ 鞍点为原 / 对偶函数的最优解

一般的可微优化问题（不一定凸）：

若对偶间隙为零，则 KKT 条件是 $(x^*,\lambda^*,v^*)$ 为最优解的必要条件

可微的凸优化问题：

若对偶间隙为零，则 KKT 条件是 $(x^*,\lambda^*,v^*)$ 为最优解的充要条件

敏感性分析

原问题：

$$ \begin{aligned} \min \ & f_0(X) \\ s.t. \ & f_i(X)\leq 0, i=1,...,M \\ & h_i(x)=0,i=1,...,P \end{aligned} $$

干扰问题：

$P^*(u,w)$ 为干扰问题的最优值函数，其中 $P^*(0,0)$ 为原问题最优值

$$ \begin{aligned} \min \ & f_0(X) \\ s.t. \ & f_i(X)\leq u_i, i=1,...,M \\ & h_i(x)=w_i,i=1,...,P \end{aligned} $$

性质：

若原问题为凸，则 $P^*(u,w)$ 为 $(u,w)$ 的凸函数
若原问题为凸，对偶间隙为零， $\lambda^*,v^*$ 为原问题对偶最优解，则 $P^*(u,w)\geq P^*(0,0)-(\lambda^*)^Tu-(v^*)^Tw$
若 $\lambda_i^*$ 很大，且加紧第 $i$ 次不等式约束，即 $u_i<0$ 则 $P^*(u,w)$ 可能会急剧上升
若 $v_i^*$ 很大正值，且 $w_i<0$ ；或 $v_i^*$ 为负值，即绝对值很大，且 $w_i>0$ ，则 $P^*(u,w)$ 可能会急剧上升
若 $\lambda_i^*$ 很小，且 $u_i>0$ ，则最优值变化不大
若 $v_i^*$ 为很小正值，且 $w_i>0$ 或 $v_i^*$ 为绝对值很小的负值，且 $w_i<0$ ，则最优值变化不大
若原问题为凸，对偶间隙为零，且 $P^*(u,w)$ 在 $(u,w)=(0,0)$ 处可微，则 $\lambda_i^*=-\displaystyle\frac{\partial P^*(0,0)}{\partial u_i},v_i^*=-\displaystyle\frac{\partial P^*(0,0)}{\partial w_i}$ ，即根据泰勒展开，得到 $P^*(u,w)\approx P^*(0,0)-(\lambda^*)^Tu-(v^*)^Tw$