弱对偶 与 强对偶 关系解释一
弱对偶
弱对偶：在最优化问题中，对偶间隙(duality gap)总是大于等于0。对于最小值优化来说，即$d\leqslant p$
强对偶
强对偶：在最优化问题中，对偶间隙(duality gap)等于0，即原问题等于对偶问题，$d=p$。
弱对偶 变为 强对偶 （充分条件）
- 若原问题是线性归回问题
则弱对偶直接等于强对偶 - 若原问题是凸优化问题
则需要满足Slater’s condition
Slater’s condition
给定原问题：
$min_x f_0(x)$
$subject\_to:$
$f_i(x)\leqslant0, i=1,2,…,m$
$Ax=b$
其中，$f_0(x)$是凸函数，$f_i(x)$也是凸函数
Slater’s condition是说，如果存在任意一个$x’$，使得
$f_i(x’)<0, i=1,2,…,m$
$Ax’=b$
那么强对偶成立。
弱对偶 与 强对偶 关系解释二
从必要条件上说
如果$d^*=p^*$，那么$d^*$对应的解(乘子)$\alpha^*, \beta^*$，和$d^*$对应的解$x^* $都是最优解。
从充分条件，判定相等上说
假定$f(x),c_i(x)$是凸函数，$h_j(x)$是仿射函数。若存在任意一个$x$，对于所有$c_i(x)$，使得所有不等式约束$c_i(x)<0$，则存在$x^*,\alpha^*,\beta^*$，使得$x^*$是最优原始问题$p^*$的解，$\alpha^*\beta^*$是最优对偶问题$d^*$的解,并且等式成立
$$d^*=L(x^*,\alpha^*,\beta^*)=p^*$$
从充分条件，解最优上说
假定$f(x),c_i(x)$是凸函数，$h_j(x)$是仿射函数，若存在任意一个$x$，对于所有$c_i(x)$，使得所有不等式约束$c_i(x)<0$，则$x^*$和$\alpha^*,\beta^*$分别是原始问题和对偶问题的解的充要条件是$x^*,\alpha^*,\beta^*$满足KKT条件：
$\nabla_xL(x^*,\alpha^*,\beta^*)=0$
$\nabla_{\alpha}L(x^*,\alpha^*,\beta^*)=0$
$\nabla_{\beta}L(x^*,\alpha^*,\beta^*)=0$
$\alpha_i^*c_i(x^*)=0, i=1,2,…,k$
$c_i(x^*)\leqslant0, i=1,2,…,k$
$\alpha_i\geqslant0, i=1,2,…,k$
$h_j(x^*)=0, j=1,2,…,l$
其中，$\alpha_i^*c_i(x^*)=0, i=1,2,…,k$称为kkt的对偶互补条件，若$c_i(x)<0$，那么$\alpha_i=0$
Reference
- https://en.wikipedia.org/wiki/Weak_duality
- https://en.wikipedia.org/wiki/Strong_duality
- https://en.wikipedia.org/wiki/Slater%27s_condition
- 统计学习方法
