数值优化（9）——非线性规划中的极值性质，KKT条件

学弱猹

发布于 2021-08-09 16:59:16

1.2K0

发布于 2021-08-09 16:59:16

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

上一节笔记：数值优化（8）——带约束优化：引入，梯度投影法

——————————————————————————————————————————————

大家好！希望上一节的各种性质和定理没有把大家吓倒……

这一节我们开始研究一种特定的带约束优化的问题——非线性规划问题（当然了，就含义上来说它不是“线性规划”的反面，更像是它的一种泛化，推广的叫法），大家可能比较期待的KKT条件等就是非线性规划的重要内容。同时，因为比较传统的运筹学的相关内容也算是非线性规划的内容，因此我们也会在这一节提一些相关的运筹学中的算法。

那么我们开始吧。

Source

Nocedal, Wright, Numerical Optimization
课堂笔记，教授主页：https://www.math.fsu.edu/~whuang2/index.html

引入：非线性规划问题的结构

非线性规划 (nonlinear programming)问题其实说白了就是具有下面这个结构的优化问题

\min_x f(x) \\ s.t. c_i(x) = 0, i \in \mathcal E \\ c_i(x) \le 0, i \in \mathcal{I}

其中

f, c_i

为光滑函数。

i \in \mathcal{E}

意味着等式约束，另外一个自然就是不等式约束。

我们要求所有的不等式约束的不等号都是小于等于，这个不难做到，因为如果不满足条件，对约束函数取一个负即可。但是这里有一个条件是光滑，很多人会对此产生疑问，这个条件会不会太强了？事实上不会，因为很多时候我们都可以通过变换，拆分，使得问题满足我们这里的形式。这里我们举两个例子

Example 1: 对于问题

\min_{x \in \mathbb R^2}f(x) \quad s.t. \quad |x_1| + |x_2| \le 1

，变换其为非线性规划问题的结构。

我们其实可以看到，约束条件

|x_1| + |x_2| \le 1

就是一个典型的非光滑约束条件，但是我们可以把它等价为四个式子

x_1 + x_2 \le 1, x_1 - x_2 \le 1, -x_1 + x_2 \le 1, -x_1 - x_2 \le 1

所以这样做它就又变成了一些光滑的约束条件。

Example 2: 对于目标函数

f(x) = \max(x^2, x)

，化归为光滑函数的结构。

如果我们假设我们的目标是极小化这个函数，也就是

\min f(x)

。那么这个时候其实可以把它化为下面这样的两个式子。

\min t \quad s.t. \quad t \ge x, t \ge x^2

这样就可以了。

这两个例子就是为了说明，我们作“光滑”的假设并非是空穴来风，它已经足够可以覆盖我们关心的问题了。

一阶最优性条件的思想

我们希望发掘一些条件，来帮助我们解决这样的问题。为了引入这些思想，我们先考虑下面这个问题

\min_x f(x) = x_1 + x_2 \quad s.t. \quad h(x) = 2 - x_1^2 - x_2^2 = 0

画图可以很轻松的发现它的极小值点为

(-1, -1)^T

。

因为我们现在在关心一阶条件，所以我们对于每一个函数，我们希望它的变换满足我们要的一些条件。具体来说，就是利用Taylor展开，观察到

f(x + s) \simeq f(x) + \nabla f^T(x)s

所以对于目标函数

f(x)

，我们自然希望做到的是

f(x+s) - f(x) \simeq \nabla f^T(x) s < 0

对于约束函数

h(x)

，要求略有不同，我们希望

h(x+s) - h(x) \simeq \nabla h^T(x) s = 0

这是因为我们希望移动一小步

之后，我们的约束条件依然满足。

如何找到这个

首先要观察到的是，如果

\nabla f(x)

和

\nabla h(x)

是共线的（注意向量的共线类似于平行，但不完全相同），那么这个时候，这个式子是不可能满足的，换句话说在约束条件满足的情况下，函数值是无法下降的。反过来说，

\exists \lambda \in \mathbb{R}, \nabla f(x) - \lambda \nabla h(x) = 0

应该是一个极值的必要条件。

有的人可能会问如果说这两个向量并非共线，那么这个时候一定是可以找到

的。具体方法就是先找一个

s' = -\nabla f(x)

，然后为了使得它与

\nabla h(x)

共线，我们就把这个向量投影到

\nabla h(x)

的正交补空间上。具体来说，这个

就是

s = - P_{\nabla h(x)}^\perp \nabla f(x) = - (I - \frac{\nabla h(x) \nabla^T h(x)}{\|\nabla h(x)\|^2})\nabla f(x)

当然这个需要学过数值分析的东西才会了解为什么投影会写成这个形式。

下面我们再看一个例子

\min_x f(x) = x_1 + x_2 \quad s.t. \quad g(x) = 2 - x_1^2 - x_2^2 \ge 0

它的极小值点没有变，但是注意它的约束由一个空心圆变成了一个实心圆。

根据同样的Taylor展开，我们可以得到两个式子

f(x+s) - f(x) \simeq \nabla f^T(x) s < 0

g(x+s) \simeq g(x) + \nabla g^T(x) s \ge 0

这个时候就要区分函数是在边界还是在内部了。其实我们可以看到，如果在内部是非常简单的，因为如果可以下降，那么设

s = -\alpha \nabla f(x)

，对于一个足够小的

\alpha

，我们自然可以保证约束仍然满足，并且函数值得到下降。而如果不可以下降，其实就是

\nabla f(x) = 0

，也没什么好说。

但是如果在边界，也就是

g(x) = 0

，情况就会有点复杂，因为在这个时候，我们要求的是

\nabla f^T(x) s < 0

和

\nabla g^T(x) s \ge 0

。这个时候可以发现，面对同样的

，我们却需要让它同时满足两个看起来相反的结论。这怎么办？

其实没有想象的那么困难，因为我们可以看到的是，只要

\nabla f(x), \nabla g(x)

同向共线，

就不存在了，反过来说，只要它们俩不是同向共线，就会存在这样的

，具体的可以见下面这张图。

对于左边的部分，两个梯度同向共线，你会发现绿色的线分布的范围（当然了不包括那个

\nabla f(x)

）和红色的线分布的范围永远不会相交。而对于第二张图，蓝色的线就是一个可选的

。所以严格来说，

\exists \lambda \in \mathbb{R^+}, \nabla f(x) - \lambda \nabla h(x) = 0

应该是一个极小值的必要条件。

到此为止其实我们推出来的式子已经有些接近KKT条件了，但是要说我们完成了任务，还为时尚早。

一阶最优性条件的严格几何与代数性质

在做带约束优化的时候，边界往往会奇奇怪怪的，所以我们这里会在多个方面分析问题的性质，并给出一个通用性的解决方案。

Definition 1: Cone 对于集合

若满足

\forall x \in S

，都有

\forall \alpha > 0, \alpha x \in S

成立，则称其为锥。 Definition 2: Tangent Vector, Tangent Cone 设

x \in \mathcal K

，如果存在一系列可行域内的收敛到

的点

\{z_k\}

和一系列满足

\tau_k \to 0

的正常数

\{\tau_k\}

，使得

d = \lim_{k \to \infty} \frac{z_k - x}{\tau_k}

，那么

被称为是通向

的切向量。所有的这样的切向量的集合被称为通向

的切锥，记为

T_{\mathcal K}(x)

。

这个切向量的定义是有点抽象的，而且也不完全是“切”的意思，我们画一张图解释一下。

绿色的线就是我们这里的切向量。这个区域是取决于两条蓝色的线划分的边界的。当然了如果这个点 (图上圆锥的尖点）是可导的，区域是空心的，那么它就是我们一般理解的切向量了。

有了这个定义之后，我们可以给出一个局部极小值的几何定义

Proposition 1: 若

x^*

是局部极小值点，那么

\forall d \in T_{\mathcal K}(x), \nabla f^T(x^*)d \ge 0

。

简单说明一下这个性质。首先注意到方向导数的公式，我们倒过来用可以得到

\nabla f^T(x^*) d = \lim_{k \to \infty} \frac{f(x^* + \tau_k d) - f(x^*)}{\tau_k} = \lim_{k \to \infty}( \frac{f(z_k) - f(x^*)}{\tau_k} - \frac{f(x^* + \tau_k d + o(\tau_k)) - f(x^* + \tau_k d)}{\tau_k})

（这里要注意的是，根据定义可以得到

z_k = x + \tau_k d + o(\tau_k)

。）

对于极限的第二项，其实注意到因为变化量是一个

\tau_k

的小量，所以分母是

\tau_k

的情况下，极限应该是0。所以只需要再用上

f(x^*)

是极小值，就可以得到结论了。

如果我们把这个性质规范化，就会引入下面这个定义。

Definition 3: Normal Cone 定义可行域内

的正规锥为

N_\mathcal K (x) = \{v | \forall w \in T_\mathcal K (x) , v^T w \le 0 \}

。

所以事实上，我们就可以把Proposition 1写成下面的形式

Proposition 1-2: 若

x^*

为局部极小值点，那么

-\nabla f(x^*) \in N_\mathcal{K} (x)

。

所以其实正规锥就有点像我们的点所“无法企及”的方向。因为如果正规锥包含了负梯度方向，其实就说明了我们的可行方向没有能够使得函数值下降的方向，那自然就说明这个点是局部极小值了。

似乎到这里，我们对于解决这一类问题的几何工具已经准备就绪，但是实际上，很多情况下正规锥是很难画出来的，否则的话也就没代数（当然了，要加上一个限定词“线性”）方法什么事了。而代数方法就会依赖我们上一节所说的“激活”的概念，具体如下。

Definition 4: Active Set 在这一类问题中，定义被激活的集合为

\mathcal{A}(x) = \mathcal E \cup \{i \in \mathcal{I}: c_i(x) = 0\}

。

换句话说，我们考虑是否激活，是通过观察约束条件是否取0，取等号而得到的，这是一个非常重要的观察

接下来我们给出一个非常常见的代数构造。

Definition 5: Linearized Feasible Directions 定义

\mathcal F(x) = \left\{d | \begin{cases}d^T \nabla c_i(x) = 0 & i \in \mathcal{E} \\ d^T \nabla c_i(x) \ge 0 & i \in \mathcal{A} \cap \mathcal{I} \end{cases}\right\}

为

处的线性化可行方向锥

当然了这个“锥”的名字不是空穴来风，是可以验证的，大家可以自己有空去代入定义验证一下。同时要注意的是，这里并没有对不等式条件中非激活的条件做限制。不严谨的来说，是因为在那个时候，相当于某一个约束条件并没有取到0，也就是说当前的点并没有受到约束的限制，在这个时候，其实研究的思路和无约束优化就没有什么差别了，不是我们这里关注的话题。

这里要注意的是，我们这里为了做一些形象的解释，所以在举例的时候我们的约束条件都是写成了

c_i(x) \ge 0

的形式，这和规范的写法是不同的。如果我们的约束条件符号变了一下，那么对应的定义的符号也要取反号。

这个定义其实本质上考虑的依然是一个一阶情况下的Taylor展开

c_i(x + d) \simeq c_i(x) + d^T \nabla c_i(x)

而为什么定义成那样，在上面我们也有说。

这个定义其实就是我们刚开始探索一阶条件时，对于各种要求的一个结合。为了加深印象我们给一个例子来说明。

Example 3: 考虑

c(x) = x_1^2 + x_2 ^2 - 1= 0

，判断它在

x^* = (1, 0)^T

的切锥和线性化可行方向锥。

对于切锥其实没什么好说的，这个约束就是一个空心圆，画一个切线这就是它的切锥（但是要注意，如果是实心圆，就是一个半平面了）。而线性化可行方向锥呢，我们可以算出它的梯度

\nabla c(x^*) = (2, 0)^T

，所以也可以得到对应的

\mathcal{F}(x) = \{d \in \mathbb{R}^2: d_1 = 0, d_2 \in \mathbb{R}\}

。这个就是

T(x)

。可以看出对于这个例子，两种写法得到的结果一样，所以说明这种代数的结构可以帮助我们代替几何的结构，进而我们就可以使用一些比较偏线性代数的方法来求解这样的问题。

但是，情况也不是那么简单，比方说对于

c(x) = (x_1^2 + x_2^2 - 1)^2 = 0

，它的线性化可行方向锥就是

\mathbb{R}^2

，并不是切锥。所以我们又添加了一些条件来修复这样的问题。一个常见的条件叫做线性独立限制修正（LICQ）。具体定义为

Definition 6: Linear Independence Constraint Qualification (LICQ) 给定点

与激活集

\mathcal A(x)

，若

的梯度的激活集是线性无关的，那么称它为一个正规点，或者说它满足LICQ条件。

事实上，我们会有下面的结论成立

Proposition 3: 若

x^*

为一个可行点，那么

T_\mathcal K(x^*) \subset \mathcal F(x^*)

，但是如果

x^*

是一个正规点，那么二者相同。

这个性质就说明了，在这个LICQ条件加上去之后，代数化的方法就可以替代我们之前的几何意义了。当然了这个性质的证明不是特别的容易，大家可以参考Numerical Optimization的第323-325页。

KKT条件及应用

KKT条件的全称是Karush-kuhn-Tucker条件，是带约束优化问题中最重要的条件之一。虽然它的应用极为之广，但是要想证明并解释它并不是特别容易，我们先给出一个引理作为铺垫。

Lemma 1: Farkas's Lemma 给定

B, C

，设

K = \{x \in \mathbb R^n | x = By + Cw, B \in \mathbb R^{n \times m}, C \in \mathbb{R}^{n \times p}, y \ge 0\}

，那么对任意的

g \in \mathbb R^n

，要不

g \in K

，要不

\exists d \in \mathbb{R}^n

, 使得

g^T d < 0, B^T d \ge 0, C^T d = 0

，但二者无法同时成立。

这个性质初看不是很好理解。但我们可以通过它的证明来慢慢理解它所揭示的意义。

命题中给了两个条件，我们先来看第一个条件。假如说我们有

g = By + Cw

，那么我们可以找到一个

，使得它成为一个

的补空间的基，也就是说我们设

Q \in \mathbb R^{n \times (n - p)}

，满足

Q^T Q = I, Q^T C = 0

。在这样的情况下，我们希望说明

g = By + Cw \Leftrightarrow Q^T g = Q^T B y

一个方向是很显然的，我不写你也知道是哪一个。另一个方向可以结合

是列正交的，所以左乘不影响式子的等价性，也就是说我们可以推得

Q^T g = Q^T B y \Leftrightarrow QQ^T g = QQ^T B y

注意到

QQ^T = I - C(C^TC)^{-1}C^T

（这个思想可以参考https://zhuanlan.zhihu.com/p/46665398中的Proposition 4，我们这里不证明它），所以我们最后把这个式子代入，移项，就可以得到

g = By + C(C^TC)^{-1}C^T (g + By)

把第二项除了

以外的所有东西都设为

就行了。我们没有对

添加任何额外的条件限制，所以这不会有问题。

为了方便起见，这里我们设

\tilde g = Q^T g

，

\tilde B = Q^T B, \tilde C = Q^T C

，之后我们也会沿用这样的记号。

对于第二个条件，我们的希望是证明下面这个等价条件

\exists d, g^T d < 0, B^T d \ge 0, C^T d = 0 \Leftrightarrow \exists \tilde d, \tilde d^T \tilde g < 0, \tilde d^T \tilde B \ge 0, \tilde d^T \tilde C = 0

我们还是依赖我们之前构造的

，注意到如果说

存在且满足那三个式子，那么

d = Q Q^T d

（想想为什么？），设

\tilde d = Q^T d

，那么我们有

\tilde d^T \tilde g = \tilde d^T Q^T g = d^T QQ^T g = (QQ^Td)^T g = d^T g< 0

这就是第一个不等式。类似的你也可以推出第二和第三个式子。

当然了，如果说另一方面成立，那么注意到

d = Q \tilde d

，就可以得到

d^T g = \tilde d^T Q g = \tilde d^T \tilde g < 0

其它两个也类似。所以第二个等价条件也就说完了。

回过头来再看我们究竟在做什么？实际上就是说，要不

\tilde g \in \tilde B y, y \ge 0

，要不然就一定会存在一个

\tilde d

，使得

\tilde d^T \tilde g < 0, \tilde d^T \tilde B \ge 0, \tilde d^T \tilde C = 0

。为什么说这两个一定能成立一个，并且只能二者取其一呢？对应的其实就是下面这张图。

可以看出，左边的含义就是这个向量

是落在我们的

\tilde B

这个基张成的线性空间内的。而右边则是表示当这个

脱离

\tilde B

的控制之后，我们在

\tilde B

与

的中间插一脚作为

（当然了这里的

肯定是一个超平面了），根据这个

就可以构造出这个

。换句话说这两个条件究竟哪一个成立，取决于这个

落在哪里，那自然不可能同时成立了，因为

并不会影分身。

如果能够看明白这张图，一定程度上也就解释了我们为什么要考虑一个

，要求

Q^T C = 0

，这是因为实际上，我们希望的就是能够找到一个

\tilde d

，它能够成为一个可以区分开

与

的标志。而找到这样的标志的一个很重要的原因就是要求

与

\tilde d

是正交的。但是如果不能看出这种矩阵乘法对应的解析几何的含义，这样的思路也就无从谈起。

说完了这个引理，接下来我们终于可以来说明万众瞩目的KKT条件了。

Theorem 1: 设

x^*

是一个局部极小值，

f, c_i

连续可微，

x^*

满足LICQ条件，那么存在一个拉格朗日乘数

\lambda ^* = (\lambda_i^*)_{i \in \mathcal E \cup \mathcal I}

使得下面的条件成立

\nabla _x \mathcal L(x^* , \lambda^*) = 0, c_i(x^*) = 0(i \in \mathcal {E}), c_i(x^*) \ge 0(i \in \mathcal I) \\ \lambda_i^* \ge 0 ( i \in \mathcal{I}), \lambda_i^* c_i(x^*) = 0(i \in \mathcal{I})

仔细看一下，第二和第三个式子是约束条件，不用管。所以归根到底是要说明，如果它是局部极小值，还必须要有第一，第四和第五个条件成立。

我们证明一下这个结论。首先我们设

是由

\nabla c_i(x), i \in \mathcal{A}(x^*) \cap I

构成的矩阵，

是由

\nabla c_i(x), i \in \mathcal{E}

构成的矩阵，那么这个时候，如果我们设

K = \{x \in \mathbb{R}^n, x = By + Cw, y \ge 0\}

，那么对于

g \in \nabla f(x^*)

，根据上面的引理，要不

\nabla f(x^*) \in K

，要不

\exists d

，使得

d^T \nabla f(x^*) < 0, d^T B \ge 0, d^T C = 0

。

这里就产生了一个问题，我们要考虑一下，

d^TB \ge 0, d^TC = 0

的几何意义是什么？这个是不是我们希望的

\mathcal F(x^*)

？但是我们是不是有LICQ条件，所以换句话说，如果这个条件成立，说明它落到了切锥上。结果这个时候突然又告诉我说

d^T \nabla f(x^*) < 0

？这很显然是不可能的，因为这相当于说明了在一个一阶极小的条件下存在一个方向可以使得函数值下降。因此相当于必须要满足

\nabla f(x^*) = By + Cw = \sum_{i \in \mathcal I \cap \mathcal A(x^*)} \lambda_i \nabla c_i(x^*) + \sum_{i \in \mathcal E} \lambda_i \nabla c_i(x^*)

（这里的

\lambda_i

就是我们说的这个点的拉格朗日常数）

还是利用引理，可以得到

\lambda_i \ge 0, i \in \mathcal {I} \cap \mathcal {A}(x^*)

。这还不足够，注意到我们要找一个

\lambda^*

满足我们要的各种结论，所以人工构造是逃不掉的。但是如何构造呢？

注意我们一开始在探索最优性条件的时候我们做了什么？其实归根到底就是说，对于不等式条件，如果没有激活（可以理解为“在约束内部”，但不严谨），那么我们应该并不愁一个

\lambda_i

，因为我们一定可以找到下降方向，换句话说在这个时候

\lambda_i = 0

是最合适的。所以实际上我们可以考虑下面的构造

\lambda_i^* = \begin{cases}\lambda_i & i \in \mathcal{A}(x^*) \\ 0 & i \in \mathcal I \backslash \mathcal{A} (x^*) \end{cases}

这样的话可以得到

\nabla f(x^*) - \sum_{i \in \mathcal {I} \cup \mathcal E} \lambda_i^* \nabla c_i(x^*) = 0

，也就是第一个式子。那么对于我们的第四个和第五个条件，这也不难得到。比方说对于第四个条件，因为如果在激活的区域，我们已经证明了它的乘数一定非负，对于非激活的区域，人工设置为了0，也是非负。对于第五个条件，类似讨论它在激活与非激活集合的情况，也不难得到结论。

所以到此，我们就给出了KKT条件的来龙去脉和详细证明。KKT条件可以给极小值点提供非常不错的代数信息，为之后的带约束优化的方法也提供了很好的理论铺垫。

在这之后，我们希望说明的是，证明的核心在于用上了

\mathcal{F}(x^*) = T_\mathcal K(x^*)

。所以事实上只要我们的条件可以让这个式子满足即可。除了LICQ条件以外，其实还有一些其它可用的条件，我们这里简单的介绍一些

Definition 7: Mangasarian-Fromovitz Constraint Qualification 如果存在

，使得

\nabla c_i^T(x^*) w > 0, \forall i \in \mathcal{A}(x^*) \cap \mathcal I

，并且

\nabla c_i^T(x^*) w = 0, \forall i \in \mathcal{E}

，则称其满足MFCQ条件。 Definition 8: Abadie Constraint Qualification 如果对于点

x^*

满足

T_\mathcal K(x^*) = \mathcal{F}(x^*)

，那么称其在这个点满足ACQ条件。 Definition 9: Guignard Constraint Qualification 如果对于点

x^*

满足

\mathcal{N}_\Omega (x^*) = \mathcal{N}(\mathcal{F}(x^*))

，则称其满足GCQ条件。

这几个条件都是可以推出KKT条件的，并且相互之间存在一定的强弱关系，也即MFCQ < LICQ < ACQ < GCQ。这里有一篇回答对这几个性质也有比较系统的介绍。

https://www.zhihu.com/question/346919689/answer/833635218

事实上，关于KKT条件，很多人会关心最后的

\lambda_i

是否唯一，而这个确实也是可以保证的。

Proposition 4: 若在点

x^*

处有KKT条件和LICQ条件成立，那么

\lambda^*

唯一。

这个地方的证明可以通过KKT条件的证明过程看出端倪。注意到LICQ条件要求了梯度方向的相互独立性，所以在式子

\nabla f(x^*) = By + Cw = \sum_{i \in \mathcal I \cap \mathcal A(x^*)} \lambda_i^* \nabla c_i(x^*) + \sum_{i \in \mathcal E} \lambda_i^* \nabla c_i(x^*)

中，我们会得到

B, C

的相互独立性，这样的话

\lambda_i^*

其实就固定了，因为基本的线性代数告诉我们，如果不固定就违背了线性无关的定义。

好的，不如我们用一个机器学习的例子来解释KKT条件的应用吧。

Example 4: 考虑支持向量机（Support Vector Machine）模型，并利用其做分类。那么在下面的图中，边界上以及边界内的点因为算是约束条件被激活的地方，所以其对应对偶问题，对应的拉格朗日参数

\alpha^* > 0

，也即改变这个点的值，会对优化问题的解产生影响，也即分类超平面会变化。反过来，如果说点不在边界上，那么对应的参数

\alpha^* = 0

，所以改变这个点的值不会对优化问题的解产生影响。因此支持向量机的模型训练结果其实只会受到少数点的制约，因此对异常值的影响是可以忽略不计的。

关于支持向量机的严格问题建模和性质推导，可以参考这视频中对应的部分。

https://www.bilibili.com/video/BV1ZK4y1b7Xt#reply2893286371

关于KKT条件本身，似乎也就差不多了。但是正如驻点会出现鞍点这样的诡异的情况一样，我们在KKT条件中也不一定能保证100%的极小值。所以我们还需要给出一些二阶条件。当然了，这一部分的证明可以参考Numerical Optimization的P332-333，我们这里就不给出详细说明了。

Proposition 5: 设

x^*

为局部极小值，

f, c_i

都是二阶连续可微的函数，LICQ条件在

x^*

处也成立，设

\lambda^*

为满足KKT条件的点的拉格朗日乘数，那么有

w^T \nabla_{xx}^2 \mathcal{L}(x^*, \lambda^*)w \ge 0, \forall w \in \mathcal{C}(x^*, \lambda^*)

，其中

\mathcal{C}(x^*, \lambda^*) = \{w \in \mathcal{F}(x^*): \nabla c_i^T(x^*) w = 0, \forall i \in \mathcal{A}(x^*) \cap \mathcal I, \lambda_i^* > 0\}

。 Proposition 6: 设

x^*

为KKT条件满足的点，

\lambda^*

为对应的拉格朗日乘数，并且有

w^T \nabla_{xx}^2 \mathcal{L}(x^*, \lambda^*)w > 0, \forall w \in \mathcal{C}(x^*, \lambda^*), w \ne 0

，那么

x^*

是一个严格的极小值。

这里的Proposition 5其实就是说，在KKT条件无法给出极小值判定的时候，我们可以通过一些二阶条件来判断，这里的

其实就是搜索方向。而Proposition 6也是类似的，但要注意Proposition 6中并没有添加额外的约束限制。

最后我们给出互补松弛性的概念。

Definition 10: 如果在

x^*

处，要不

\lambda_i^* = 0

，要不

c_i(x^*) = 0

，但不同时成立，则称其满足互补松弛条件。换句话说，对于激活的约束，若

\lambda_i^* > 0

则称其非退化，否则称为退化。

这个性质有的时候可以帮助我们观察一下极值点在约束上的性态。

到此，我们终于算是把非线性规划问题中的极值性质研究的差不多了。在之后的更加具体的带约束优化问题中，我们都会依赖这一节的很多理论的内容。

小结

本节我们主要关注了非线性规划问题的极值性质，从一开始对于约束的探索，到之后搭建几何到代数的桥梁，再到最后利用这些思想方法证明带约束优化中极为重要的KKT条件。虽然说KKT条件只是一个充分条件，很像是无约束优化中的驻点的地位，但是对于优化这个领域来说，这已经算是很不错的成果了。

下一节我们会进入到线性规划的部分，介绍一些运筹学中很常见的算法，并适当的给出一些实际的计算实例。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-07-24，如有侵权请联系 cloudcommunity@tencent.com 删除

definition

optimization

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

definition

optimization