凸优化学习笔记 12：KKT条件_kkt条件实例

上一小节讲了拉格朗日函数，可以把原始问题转化为对偶问题，并且对偶问题是凸的。我们还得到了弱对偶性和强对偶性的概念，并且提到了 Slater Condition 保证凸问题的强对偶性成立，并且给出了一些几何的直观解释。那么在这一节，我们将引出著名的 KKT 条件，它给出了最优解需要满足的必要条件，是求解优化问题最优解的一个重要方式。

有需要的话可以参考前面两节内容
凸优化学习笔记 10：凸优化问题
凸优化学习笔记 11：对偶原理

1. KKT 条件

我们首先回顾一下拉格朗日函数，考虑下面的优化问题
 minimize  f 0 ( x )  subject to  f i ( x ) ≤ 0 , i = 1 , … , m h i ( x ) = 0 , i = 1 , … , p

$$\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}$$  minimize  subject to ​f0​(x)fi​(x)≤0,i=1,…,mhi​(x)=0,i=1,…,p​

那么他的拉格朗日函数就是
$$L(x,\lambda ,\nu )=f_0(x)+{\lambda }^{T}f(x)+{\nu }^{T}h(x)$$

首先，我们看对偶函数
$$g(\lambda ,\nu )=\underset{x\in \mathcal{D}}{\inf }\left(f_0(x)+{\lambda }^{T}f(x)+{\nu }^{T}h(x)\right)$$

对偶问题实际上就是
$$d^{\star }=\underset{\lambda ,\nu }{\sup }g(\lambda ,\nu )=\underset{\lambda ,\nu }{\sup }\underset{x}{\inf }L(x,\lambda ,\nu )$$

然后我们再看原问题，由于 $\lambda ⪰0,f(x)⪯0$，我们有
$$f_0(x)=\underset{\lambda ,\nu }{\sup }L(x,\lambda ,\nu )$$

原问题的最优解实际上就是
$$p^{\star }=\underset{x}{\inf }{f}_0(x)=\underset{x}{\inf }\underset{\lambda ,\nu }{\sup }L(x,\lambda ,\nu )$$

弱对偶性 $p^{\star }\ge d^{\star }$ 实际上说的是什么呢？就是 max-min 不等式
$$\underset{x}{\inf }\underset{\lambda ,\nu }{\sup }L(x,\lambda ,\nu )\ge \underset{\lambda ,\nu }{\sup }\underset{x}{\inf }L(x,\lambda ,\nu )$$

强对偶性说的又是什么呢？就是上面能够取等号
$$\underset{x}{\inf }\underset{\lambda ,\nu }{\sup }L(x,\lambda ,\nu )=\underset{\lambda ,\nu }{\sup }\underset{x}{\inf }L(x,\lambda ,\nu )=L(x^{\star },{\lambda }^{\star },{\nu }^{\star })$$
实际上 $x^{\star },{\lambda }^{\star },{\nu }^{\star }$ 就是拉格朗日函数的鞍点！！！（数学家们真实太聪明了！！！妙啊！！！）那么也就是说强对偶性成立等价于拉格朗日函数存在鞍点(在定义域内)。

好，如果存在鞍点的话，我们怎么求解呢？还是看上面取等的式子
f 0 ( x ⋆ ) = g ( λ ⋆ , ν ⋆ ) = inf ⁡ x ( f 0 ( x ) + λ ⋆ T f ( x ) + ν ⋆ T h ( x ) ) ≤ f 0 ( x ⋆ ) + λ ⋆ T f ( x ⋆ ) + ν ⋆ T h ( x ⋆ ) ≤ f 0 ( x ⋆ )

$$\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}$$ f0​(x⋆)=g(λ⋆,ν⋆)​=xinf​(f0​(x)+λ⋆Tf(x)+ν⋆Th(x))≤f0​(x⋆)+λ⋆Tf(x⋆)+ν⋆Th(x⋆)≤f0​(x⋆)​

这两个不等号必须要取到等号，而第一个不等号取等条件应为
$${\nabla }_x\left(f_0(x)+{\lambda }^{\star T}f(x)+{\nu }^{\star T}h(x)\right)=0$$

第二个不等号取等条件为
$${\lambda }_i^{\star }{f}_i(x^{\star })=0,\forall i$$

同时，由于 $x^{\star },{\lambda }^{\star },{\nu }^{\star }$ 还必须位于定义域内，需要满足约束条件，因此上面的几个条件共同构成了 KKT 条件。

KKT 条件

1. 原始约束 $f_i(x)\le 0,i=1,...,m,h_i(x)=0,i=1,...,p$
2. 对偶约束 $\lambda ⪰0$
3. 互补性条件(complementary slackness) ${\lambda }_i{f}_i(x)=0,i=1,...,m$
4. 梯度条件

$$\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(重要结论)

1. 前面推导没有任何凸函数的假设，因此不论是否为凸问题，如果满足强对偶性，那么最优解一定满足 KKT 条件。
2. 但是反过来不一定成立，也即 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(重要结论)：

1. 考虑原问题为凸的，那么若 KKT 条件有解 $\tilde{x},\tilde{\lambda },\tilde{\nu }$，则原问题一定满足强对偶性，且他们就对应原问题和对偶问题的最优解。
2. 但是需要注意的是，KKT 条件可能无解！此时就意味着原问题不满足强对偶性！

假如我们考虑上一节提到的 SCQ 条件，如果凸优化问题满足 SCQ 条件，则意味着强对偶性成立，则此时有结论

Remarks(重要结论)：

如果 SCQ 满足，那么 $x$ 为最优解当且仅当存在 $\lambda ,\nu$ 满足 KKT 条件！

例子 1：等式约束的二次优化问题 $P\in S_{+}^n$
 minimize  ( 1 / 2 ) x T P x + q T x + r  subject to  A x = b

$$\begin{aligned} \text { minimize } \quad& (1/2)x^TPx+q^Tx+r \\ \text { subject to } \quad& Ax=b \end{aligned}$$  minimize  subject to ​(1/2)xTPx+qTx+rAx=b​

那么经过简单计算就可以得到 KKT 条件为
[ P A T A 0 ] [ x ⋆ ν ⋆ ] = [ − q b ] \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] [PA​AT0​][x⋆ν⋆​]=[−qb​]

例子 2：注水问题
 minimize  − ∑ i = 1 n log ⁡ ( α i + x i )  subject to  x ⪰ 0 , 1 T x = 1

$$\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}$$ ​ minimize −i=1∑n​log(αi​+xi​) subject to x⪰0,1Tx=1​

根据上面的结论，$x$ 是最优解当且仅当 $x⪰0,1^{T}x=1$，且存在 $\lambda ,\nu$ 满足
$$\lambda ⪰0,{\lambda }_i{x}_i=0,\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 \ge 1/{\alpha }_i$：${\lambda }_i=\nu -1/{\alpha }_i,x_i=0$

整理就可以得到 1 T x = ∑ i max ⁡ { 0 , 1 / ν − α i } \mathbf{1}^{T} x=\sum_i\max\{0,1/\nu-\alpha_i\} 1Tx=∑i​max{0,1/ν−αi​}，这个式子怎么理解呢？就像向一个池子里注水一样

3. 扰动与敏感性分析

现在我们再回到原始问题
 minimize  f 0 ( x )  subject to  f i ( x ) ≤ 0 , i = 1 , … , m h i ( x ) = 0 , i = 1 , … , p

$$\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}$$  minimize  subject to ​f0​(x)fi​(x)≤0,i=1,…,mhi​(x)=0,i=1,…,p​

我们引入了对偶函数 $g(\lambda ,\nu )$，那这两个参数 $\lambda ,\nu$ 有什么含义吗？假如我们把原问题放松一下
 minimize  f 0 ( x )  subject to  f i ( x ) ≤ u i , i = 1 , … , m h i ( x ) = v i , i = 1 , … , p

$$\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}$$  minimize  subject to ​f0​(x)fi​(x)≤ui​,i=1,…,mhi​(x)=vi​,i=1,…,p​

记最优解为 $p^{\star }(u,v)=\min f_0(x)$，现在对偶问题变成了
max ⁡ g ( λ , ν ) − u T λ − v T ν s.t. λ ⪰ 0

$$\begin{aligned} \max \quad& g(\lambda,\nu)-u^T\lambda -v^T\nu\\ \text{s.t.} \quad& \lambda\succeq0 \end{aligned}$$ maxs.t.​g(λ,ν)−uTλ−vTνλ⪰0​

假如说原始对偶问题的最优解为 ${\lambda }^{\star },{\nu }^{\star }$，松弛后的对偶问题最优解为 $\tilde{\lambda },\tilde{\nu }$，那么根据弱对偶性原理，有
p ⋆ ( u , v ) ≥ g ( λ ~ , ν ~ ) − u T λ ~ − v T ν ~ ≥ g ( λ ⋆ , ν ⋆ ) − u T λ ⋆ − v T ν ⋆ = p ⋆ ( 0 , 0 ) − u T λ ⋆ − v T ν ⋆

$$\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}$$ p⋆(u,v)​≥g(λ~,ν~)−uTλ~−vTν~≥g(λ⋆,ν⋆)−uTλ⋆−vTν⋆=p⋆(0,0)−uTλ⋆−vTν⋆​

这像不像关于 $u,v$ 的一阶近似？太像了！实际上，我们有
$${\lambda }_i^{\star }=-\frac{\partial p^{\star }(0,0)}{\partial u_i},{\nu }_i^{\star }=-\frac{\partial p^{\star }(0,0)}{\partial v_i}$$

4. Reformulation

前面将凸优化问题的时候，我们提到了Reformulation的几个方法来简化原始问题(参考凸优化学习笔记 10：凸优化问题)，比如消去等式约束，添加等式约束，添加松弛变量，epigraph等等。现在当我们学习了对偶问题，再来重新看一下这些方法。

4.1 引入等式约束

例子 1：考虑无约束优化问题 $\min f(Ax+b)$，他的对偶问题跟原问题是一样的。如果我们引入等式约束，原问题和对偶问题变为
minimize f 0 ( y ) subject to A x + b − y = 0 minimize b T ν − f 0 ∗ ( ν ) subject to A T ν = 0

$$\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{minimize} \quad& b^{T} \nu-f_{0}^{*}(\nu) \\ \text{subject to} \quad& A^{T} \nu=0 \end{aligned}$$ minimizesubject to​f0​(y)Ax+b−y=0​minimizesubject to​bTν−f0∗​(ν)ATν=0​

例子 2：考虑无约束优化 $\min \Vert Ax-b\Vert$，类似的引入等式约束后，对偶问题变为
minimize b T ν subject to A T ν = 0 , ∥ ν ∥ ∗ ≤ 1

$$\begin{aligned} \text{minimize} \quad& b^{T} \nu \\ \text{subject to} \quad& A^{T} \nu=0,\quad \Vert\nu\Vert_*\le1 \end{aligned}$$ minimizesubject to​bTνATν=0,∥ν∥∗​≤1​

4.2 显示约束与隐式约束的相互转化

例子 3：考虑原问题如下，可以看出来对偶问题非常复杂

minimize c T x subject to A x = b − 1 ⪯ x ⪯ 1 maximize − b T ν − 1 T λ 1 − 1 T λ 2 subject to c + A T ν + λ 1 − λ 2 = 0 λ 1 ⪰ 0 , λ 2 ⪰ 0

$$\begin{aligned} \text{minimize} \quad& c^{T} x \\ \text{subject to} \quad& A x=b \\ \quad& -1 \preceq x \preceq 1 \end{aligned}$$ \qquad $$\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}$$ minimizesubject to​cTxAx=b−1⪯x⪯1​maximizesubject to​−bTν−1Tλ1​−1Tλ2​c+ATν+λ1​−λ2​=0λ1​⪰0,λ2​⪰0​

如果我们原问题的不等式约束条件转化为隐式约束，则有
minimize f 0 ( x ) = { c T x ∥ x ∥ ∞ ⪯ 1 ∞  otherwise  subject to A x = b

$$\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}$$ minimizesubject to​f0​(x)={cTx∞​∥x∥∞​⪯1 otherwise ​Ax=b​

然后对偶问题就可以转化为无约束优化问题
$$\text{maximize}-b^T\nu -\Vert A^T\nu +c{\Vert }_1$$

4.3 转化目标函数与约束函数

例子 4：还考虑上面提到的无约束优化问题 $\min \Vert Ax-b\Vert$，我们可以把目标函数平方一下，得到
minimize ( 1 / 2 ) ∥ y ∥ 2 subject to A x − b = y

$$\begin{aligned} \text{minimize} \quad& (1/2)\Vert y\Vert^2 \\ \text{subject to} \quad& Ax-b=y \end{aligned}$$ minimizesubject to​(1/2)∥y∥2Ax−b=y​

然后对偶问题就可以转化为
minimize ( 1 / 2 ) ∥ ν ∥ ∗ 2 + b T ν subject to A T ν = 0

$$\begin{aligned} \text{minimize} \quad& (1/2)\Vert \nu\Vert_*^2+ b^T\nu \\ \text{subject to} \quad& A^T\nu=0 \end{aligned}$$ minimizesubject to​(1/2)∥ν∥∗2​+bTνATν=0​

最后给我的博客打个广告，欢迎光临
https://glooow1024.github.io/
https://glooow.gitee.io/

前面的一些博客链接如下
凸优化专栏
凸优化学习笔记 1：Convex Sets
凸优化学习笔记 2：超平面分离定理
凸优化学习笔记 3：广义不等式
凸优化学习笔记 4：Convex Function
凸优化学习笔记 5：保凸变换
凸优化学习笔记 6：共轭函数
凸优化学习笔记 7：拟凸函数 Quasiconvex Function
凸优化学习笔记 8：对数凸函数
凸优化学习笔记 9：广义凸函数
凸优化学习笔记 10：凸优化问题
凸优化学习笔记 11：对偶原理