上一小节讲了拉格朗日函数，可以把原始问题转化为对偶问题，并且对偶问题是凸的。我们还得到了弱对偶性和强对偶性的概念，并且提到了 Slater Condition 保证凸问题的强对偶性成立，并且给出了一些几何的直观解释。那么在这一节，我们将引出著名的 KKT 条件，它给出了最优解需要满足的必要条件，是求解优化问题最优解的一台重要方式。
1. KKT 条件
我们首先回顾一下拉格朗日函数，考虑下面的优化问题
\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { subject to } \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &h_{i}(x)=0, \quad i=1, \ldots, p \end{aligned} \\
那么他的拉格朗日函数就是
L(x,\lambda,\nu)=f_0(x)+\lambda^Tf(x)+\nu^Th(x) \\
首先，我们看对偶函数
g(\lambda,\nu)=\inf_{x\in\mathcal{D}}\left(f_0(x)+\lambda^Tf(x)+\nu^Th(x)\right) \\
对偶问题实际上就是
d^\star = \sup_{\lambda,\nu}g(\lambda,\nu)=\sup_{\lambda,\nu}\inf_x L(x,\lambda,\nu) \\
然后我们再看原问题，由于 \lambda\succeq0,f(x)\preceq0，我们有
f_0(x)=\sup_{\lambda,\nu}L(x,\lambda,\nu) \\
原问题的最优解实际上就是
p^\star=\inf_x f_0(x)= \inf_x \sup_{\lambda,\nu}L(x,\lambda,\nu) \\
弱对偶性 p^\star \ge d^\star 实际上说的是指什么呢？就是 max-min 不等式
\inf_x \sup_{\lambda,\nu}L(x,\lambda,\nu) \ge \sup_{\lambda,\nu}\inf_x L(x,\lambda,\nu) \\
强对偶性说的又是指什么呢？就是上面能够取等号
\inf_x \sup_{\lambda,\nu}L(x,\lambda,\nu) = \sup_{\lambda,\nu}\inf_x L(x,\lambda,\nu) = L({x}^\star,{\lambda}^\star,{\nu}^\star) \\
实际上 {x}^\star,{\lambda}^\star,{\nu}^\star 就是拉格朗日函数的鞍点！！！（数学家们真实太聪明了！！！妙啊！！！）那么也就是说强对偶性成立等价于拉格朗日函数存在鞍点(在定义域内)。
好，如果存在鞍点的话，我们如何求解呢？或是看上面取等的式子
\begin{aligned} f_0({x}^\star) = g(\lambda^\star,\nu^\star) &= \inf_x \left( f_0(x)+\lambda^{\star T}f(x)+\nu^{\star T}h(x) \right) \\ & \le f_0(x^\star)+\lambda^{\star T}f(x^\star)+\nu^{\star T}h(x^\star) \\ & \le f_0(x^\star) \end{aligned} \\
这两个不等号必须要取到等号，而第一台不等号取等条件应为
\nabla_x \left( f_0(x)+\lambda^{\star T}f(x)+\nu^{\star T}h(x) \right) =0 \\
第二个不等号取等条件为
\lambda^\star_i f_i(x^\star)=0,\forall i \\
同时，由于 {x}^\star,{\lambda}^\star,{\nu}^\star 还必须位于定义域内，需要满足约束条件，因此上面的几个条件共同构成了 KKT 条件。
KKT 条件
- 原始约束 f_i(x)\le0,i=1,...,m, \quad h_i(x)=0,i=1,...,p
- 对偶约束 \lambda\succeq0
- 互补性条件(complementary slackness) \lambda_i f_i(x)=0,i=1,...,m
- 梯度条件
\nabla f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} \nabla f_{i}(x)+\sum_{i=1}^{p} \nu_{i} \nabla h_{i}(x)=0 \\
2. KKT 条件与凸问题
Remarks(重要结论)
- 前面推导没有任何凸函数的假设，因此不论是否为凸问题，如果满足强对偶性，那么最优解一定满足 KKT 条件。
- 但是反过来不一定成立，也即 KKT 条件的解不一定是最优解，因为如果 L(x,\lambda^\star,\nu^\star) 不是凸的，那么 \nabla_x L=0 并不能保证 g(\lambda^\star,\nu^\star)=\inf_x L(x,\lambda^\star,\nu^\star)\ne L(x^\star,\lambda^\star,\nu^\star)，也即不能保证 {x}^\star,{\lambda}^\star,{\nu}^\star 就是鞍点。
但是如果我们假设原问题为凸问题的话，那么 L(x,\lambda^\star,\nu^\star) 就是一台凸函数，由梯度条件 \nabla_x L=0 我们就能得到 g(\lambda^\star,\nu^\star)=L(x^\star,\lambda^\star,\nu^\star)=\inf_x L(x,\lambda^\star,\nu^\star)，另一方面根据互补性条件我们有此时 f_0(x^\star)=L(x^\star,\lambda^\star,\nu^\star)，因此我们可以得到一台结论
Remarks(重要结论)：
- 考虑原问题为凸的，那么若 KKT 条件有解 \tilde{x},\tilde{\lambda},\tilde{\nu}，则原问题一定满足强对偶性，且他们就对应原问题和对偶问题的最优解。
- 但是需要注意的是，KKT 条件可能无解！此时就意味着原问题不满足强对偶性！
假如我们考虑上一节提到的 SCQ 条件，如果凸优化问题满足 SCQ 条件，则意味着强对偶性成立，则此时有结论
Remarks(重要结论)：
如果 SCQ 满足，那么 x 为最优解当且仅当存在 \lambda,\nu 满足 KKT 条件！ 例子 1：等式约束的二次优化问题 P\in S_+^n
\begin{aligned} \text { minimize } \quad& (1/2)x^TPx+q^Tx+r \\ \text { subject to } \quad& Ax=b \end{aligned} \\
那么经过简单计算就可以得到 KKT 条件为
\left[\begin{array}{cc} P & A^{T} \\ A & 0 \end{array}\right]\left[\begin{array}{l} x^{\star} \\ \nu^{\star} \end{array}\right]=\left[\begin{array}{c} -q \\ b \end{array}\right] \\
例子 2：注水问题
\begin{aligned} &\text { minimize } \quad-\sum_{i=1}^{n} \log \left(\alpha_{i}+x_{i}\right)\\ &\text { subject to } \quad x \succeq 0, \quad \mathbf{1}^{T} x=1 \end{aligned} \\
根据上面的结论，x 是最优解当且仅当 x\succeq0,\mathbf{1}^{T} x=1，且存在 \lambda,\nu 满足
\lambda \succeq 0, \quad \lambda_{i} x_{i}=0, \quad \frac{1}{x_{i}+\alpha_{i}}+\lambda_{i}=\nu \\
根据互补性条件 \lambda_i x_i=0 分情况讨论可以得到
- 如果 \nu<1/\alpha_i：\lambda_i=0,x_i=1/\nu-\alpha_i
- 如果 \nu\ge1/\alpha_i：\lambda_i=\nu-1/\alpha_i,x_i=0
整理就可以得到 \mathbf{1}^{T} x=\sum_i\max\{0,1/\nu-\alpha_i\}，这个式子如何理解呢？就像向一台池子里注水一样
3. 扰动与敏感性分析
目前我们再回到原始问题
\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { subject to } \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &h_{i}(x)=0, \quad i=1, \ldots, p \end{aligned} \\
我们引入了对偶函数 g(\lambda,\nu)，那这两个参数 \lambda,\nu 有什么含义吗？假如我们把原问题放松一下
\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { subject to } \quad& f_{i}(x) \leq u_i, \quad i=1, \ldots, m\\ &h_{i}(x)=v_i, \quad i=1, \ldots, p \end{aligned} \\
记最优解为 p^\star(u,v)=\min f_0(x)，目前对偶问题变成了
\begin{aligned} \max \quad& g(\lambda,\nu)-u^T\lambda -v^T\nu\\ \text{s.t.} \quad& \lambda\succeq0 \end{aligned} \\
假如说原始对偶问题的最优解为 \lambda^\star,\nu^\star，松弛后的对偶问题最优解为 \tilde{\lambda},\tilde{\nu}，那么根据弱对偶性原理，有
\begin{aligned} p^\star(u,v) &\ge g(\tilde\lambda,\tilde\nu)-u^T\tilde\lambda -v^T\tilde\nu \\ &\ge g(\lambda^\star,\nu^\star)-u^{T}\lambda^\star -v^{T}\nu^\star \\ &= p^\star(0,0) - u^{T}\lambda^\star -v^{T}\nu^\star \end{aligned} \\
这像不像关于 u,v 的一阶近似？太像了！实际上，我们有
\lambda_{i}^{\star}=-\frac{\partial p^{\star}(0,0)}{\partial u_{i}}, \quad \nu_{i}^{\star}=-\frac{\partial p^{\star}(0,0)}{\partial v_{i}} \\
4. Reformulation
前面将凸优化问题的时候，我们提到了Reformulation的几个方法来简化原始问题，比如消去等式约束，添加等式约束，添加松弛变量，epigraph等等。目前当我们学习了对偶问题，再来重新看一下这些方法。
4.1 引入等式约束
例子 1：考虑无约束优化问题 \min f(Ax+b)，他的对偶问题跟原问题是一样的。如果我们引入等式约束，原问题和对偶问题变为
\begin{aligned} \text{minimize} \quad& f_{0}(y) \quad \\ \text{subject to} \quad& A x+b-y=0 \end{aligned} \quad\qquad \begin{aligned} \text{maximize} \quad& b^{T} \nu-f_{0}^{*}(\nu) \\ \text{subject to} \quad& A^{T} \nu=0 \end{aligned} \\
例子 2：考虑无约束优化 \min \Vert Ax-b\Vert，类似的引入等式约束后，对偶问题变为
\begin{aligned} \text{minimize} \quad& b^{T} \nu \\ \text{subject to} \quad& A^{T} \nu=0,\quad \Vert\nu\Vert_*\le1 \end{aligned} \\
4.2 显示约束与隐式约束的相互转化
例子 3：考虑原问题如下，可以看出来对偶问题非常复杂
\begin{aligned} \text{minimize} \quad& c^{T} x \\ \text{subject to} \quad& A x=b \\ \quad& -1 \preceq x \preceq 1 \end{aligned} \begin{aligned} \text{maximize} \quad& -b^{T} \nu-\mathbf{1}^{T} \lambda_{1}-\mathbf{1}^{T} \lambda_{2} \\ \text{subject to} \quad& c+A^{T} \nu+\lambda_{1}-\lambda_{2}=0 \\ \quad& \lambda_{1} \succeq 0, \quad \lambda_{2} \succeq 0 \end{aligned} \\
如果我们原问题的不等式约束条件转化为隐式约束，则有
\begin{aligned} \text{minimize} \quad& f_{0}(x)=\left\{\begin{array}{ll}c^{T} x & \Vert x\Vert_\infty \preceq 1 \\ \infty & \text { otherwise }\end{array}\right. \\ \text{subject to} \quad& A x=b \end{aligned} \\
然后对偶问题就可以转化为无约束优化问题
\text{maximize} -b^T\nu-\Vert A^T\nu +c\Vert_1 \\
4.3 转化目标函数与约束函数
例子 4：还考虑上面提到的无约束优化问题 \min \Vert Ax-b\Vert，我们可以把目标函数平方一下，得到
\begin{aligned} \text{minimize} \quad& (1/2)\Vert y\Vert^2 \\ \text{subject to} \quad& Ax-b=y \end{aligned} \\
然后对偶问题就可以转化为
\begin{aligned} \text{minimize} \quad& (1/2)\Vert \nu\Vert_*^2+ b^T\nu \\ \text{subject to} \quad& A^T\nu=0 \end{aligned} \\ |
