最优性条件

次优解认证和终止准则

如果能够找到一个对偶可行解 $(\lambda ,\nu )$，就对原问题的最优值建立了一个下界：$p^{\star }⩾g(\lambda ,\nu )$。因此，对偶可行点 $(\lambda ,\nu )$ 为表达式 $p^{\star }⩾g(\lambda ,\nu )$ 的成立提供了一个证明或认证。强对偶性意味着存在任意好的认证。

对偶可行点可以让我们在不知道 $p^{\star }$ 的确切值的情况下界定给定可行点的次优程度。事实上，如果 $x$ 是原问题的可行解且 $(\lambda ,\nu )$ 对偶可行，那么

$$f(x)-p^{\star }⩽f_0(x)-g(\lambda ,\nu )$$

特别地，上式说明了 $x$ 是 $ϵ$- 次优，其中 $ϵ=f_0(x)-g(\lambda ,\nu )$。

定义原问题和对偶问题目标函数的差值

$$f_0(x)-g(\lambda ,\nu )$$

为原问题可行解 $x$ 和对偶可行解 $(\lambda ,\nu )$ 之间的对偶间隙。一对原对偶问题的可行点 $x,(\lambda ,\nu )$ 将原问题（对偶问题）的最优值限制在一个区间上：

$$p^{\star }\in [g(\lambda ,\nu ),f_0(x)],d^{\star }\in [g(\lambda ,\nu ),f_0(x)]$$

区间的长度即为上面定义的对偶间隙。

如果原对偶可行对 $x,(\lambda ,\nu )$ 的对偶间隙为零，即 $f_0(x)=g(\lambda ,\nu )$，那么 $x$ 是原问题的最优解且 $(\lambda ,\nu )$ 是对偶问题的最优解。此时，我们可以认为 $(\lambda ,\nu )$ 是证明 $x$ 为最优解的一个认证。（类似地，也可以认为 $x$ 是证明 $(\lambda ,\nu )$ 为最优解的一个认证。）

上述现象可以用在优化算法中给出非启发式停止准则。即令对偶间隙小于给定精度 ${ϵ}_{\mathrm{abs}}$，这能够保证当算法终止的时候，问题的解可以达到 ${ϵ}_{\mathrm{abs}}$- 最优。

互补松驰性

设原问题和对偶问题的最优值都可以达到且相等（即强对偶性成立）。令 $x^{\star }$ 是原问题的最优解，$({\lambda }^{\star },{\nu }^{\star })$，这表明

$$\begin{array}{rl}{f}_0\left(x^{\star }\right)& =g({\lambda }^{\star },{\nu }^{\star })\\ & =\underset{x}{inf}(f_0(x)+\sum _{i=1}^m{\lambda }_i^{\star }{f}_i(x)+\sum _{i=1}^p{\nu }_i^{\star }{h}_i(x))\\ & ⩽f_0\left(x^{\star }\right)+\sum _{i=1}^m{\lambda }_i^{\star }{f}_i\left(x^{\star }\right)+\sum _{i=1}^p{\nu }_i^{\star }{h}_i\left(x^{\star }\right)\\ & ⩽f_0\left(x^{\star }\right)\end{array}$$

第一个等式说明最优对偶间隙为零，第二个等式是对偶函数的定义。第三个不等式是根据 Lagrange 函数关于 $x$ 求下确界小于等于其在 $x=x^{\star }$ 处得到。最后一个不等式成立是因为

$$\{\begin{array}{cc}{\lambda }_i^{\star }⩾0,& i=1,\cdots ,m\\ f_i(x^{\star })⩽0,& i=1,\cdots ,m\\ h_i(x^{\star })=0,& i=1,\cdots ,p\end{array}$$

因此，在上面的式子链中，两个不等式取等号。

由此可以得出一些有意义的结论。其中一个特别重要的结论是

$$\sum _{i=1}^m{\lambda }_i^{\star }{f}_i(x^{\star })=0$$

事实上，求和项的每一项都非正，因此有

$${\lambda }_i^{\star }{f}_i(x^{\star })=0,i=1,\cdots ,m$$

上述条件称为互补松弛性。它对任意原问题的最优解 $x^{\star }$ 以及对偶问题的最优解 $({\lambda }^{\star },{\nu }^{\star })$ 都成立（当强对偶性成立时）。我们可以将互补松弛性条件写成

$${\lambda }_i^{\star }>0⟹f_i(x^{\star })=0$$

或者等价地

$$f_i(x^{\star })<0⟹{\lambda }_i^{\star }=0$$

互补松弛性条件说明了在最优点处，除了第 $i$ 个约束起作用的情况，最优 Lagrange 乘子的第 $i$ 项都为零。

KKT 最优性条件

非凸问题的 KKT 条件

由于 $L(x,{\lambda }^{\star },{\nu }^{\star })$ 关于 $x$ 求极小在 $x^{\star }$ 处取得最小值，因此函数在 $x^{\star }$ 处的导数必须为零，即

$$\mathrm{\nabla }{f}_0\left(x^{\star }\right)+\sum _{i=1}^m{\lambda }_i^{\star }\mathrm{\nabla }{f}_i\left(x^{\star }\right)+\sum _{i=1}^p{\nu }_i^{\star }\mathrm{\nabla }{h}_i\left(x^{\star }\right)=0$$

因此，我们可以得到

$$\begin{array}{rlrl}{f}_i\left(x^{\star }\right)& ⩽0,& i& =1,\cdots ,m\\ h_i\left(x^{\star }\right)& =0,& i& =1,\cdots ,p\\ {\lambda }_i^{\star }& ⩾0,& i& =1,\cdots ,m\\ {\lambda }_i^{\star }{f}_i\left(x^{\star }\right)& =0,& i& =1,\cdots ,m\\ \mathrm{\nabla }{f}_0\left(x^{\star }\right)+\sum _{i=1}^m{\lambda }_i^{\star }\mathrm{\nabla }{f}_i\left(x^{\star }\right)+\sum _{i=1}^p{\nu }_i^{\star }\mathrm{\nabla }{h}_i\left(x^{\star }\right)& =0& & \end{array}$$

我们称上式为 Karush-Kuhn-Tucker (KKT) 条件。

总之，只要强对偶性成立，那么任何一对原问题的最优解和对偶问题的最优解必须满足 KKT 条件。

凸问题的 KKT 条件

$$\begin{array}{rlrl}{f}_i(\tilde{x})& ⩽0,& i& =1,\cdots ,m\\ h_i(\tilde{x})& =0,& i& =1,\cdots ,p\\ \tilde{\lambda }\mathrm{\_}i& ⩾0,& i& =1,\cdots ,m\\ \tilde{\lambda }\mathrm{\_}i{f}_i(\tilde{x})& =0,& i& =1,\cdots ,m\\ \mathrm{\nabla }{f}_0(\tilde{x})+\sum _{i=1}^m\tilde{\lambda }\mathrm{\_}i\mathrm{\nabla }{f}_i(\tilde{x})+\sum _{i=1}^p\tilde{\nu }\mathrm{\_}i\mathrm{\nabla }{h}_i(\tilde{x})& =0,& & \end{array}$$

从凸问题的 KKT 条件中，我们可以得出结论

$$\begin{array}{rl}g(\tilde{\lambda },\tilde{\nu })& =L(\tilde{x},\tilde{\lambda },\tilde{\nu })\\ & =f_0(\tilde{x})+\sum _{i=1}^m\tilde{\lambda }\mathrm{\_}if\mathrm{\_}i(\tilde{x})+\sum _{i=1}^p\tilde{\nu }\mathrm{\_}i{h}_i(\tilde{x})\\ & =f_0(\tilde{x})\end{array}$$

推导过程的最后一步成立是因为 $h_i(\tilde{x})=0$ 以及 ${\tilde{\lambda }}_i{f}_i(\tilde{x})=0$。这说明原问题的解 $\tilde{x}$ 和对偶问题的解 $(\tilde{\lambda },\tilde{\nu })$ 之间的对偶间隙为零，因此分别是原、对偶问题的最优解。总之，对目标函数和约束函数可微的任意凸优化问题，任意满足 KKT 条件的点分别是原、对偶问题的最优解，对偶间隙为零。

KKT 条件在优化领域有着重要作用。在一些特殊的情形下，是可以解析求解 KKT 条件的（因此可以求解优化问题）。更一般地，很多求解凸优化问题的方法可以认为或者理解为求解 KKT 条件的方法。

INFO

关于 KKT 条件的深入理解与分析，详见下一小节深入理解 KKT 条件。