约束优化的最优性条件

文章目录

• 约束优化的最优性条件
• • 1 简绍
  • 2 最优性必要条件
  • • • 几 何 必 要 条 件 \large\color{#70f3ff}{\boxed{\color{brown}{几何必要条件} }} 几何必要条件​
      • 凸 集 的 分 离 \large\color{#70f3ff}{\boxed{\color{brown}{凸集的分离} }} 凸集的分离​
      • 代 数 的 必 要 条 件 \large\color{#70f3ff}{\boxed{\color{brown}{代数的必要条件} }} 代数的必要条件​
  • 拉格朗日条件
  • • 不等式约束优化
    • 例1
    • 例2
    • 例3
    • 例4
  • 3 凸性
  • 4 最优性充分条件
  • • 例5
  • 5 约束规范
  • 6 二阶最优性条件
  • • 例6
  • 参考资料

1 简绍

约束优化问题:
KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ (P) ~ ~ ~ …
其中向量 $x=(x_1,…,x_n) $称为优化问题的变量（optimization variables），函数 $f:\quad \textbf{R}^m \rightarrow \textbf{R} $为目标函数（objective function），函数 $f(x),g(x）: \quad \textbf{R}^m \rightarrow \textbf{R} $称为约束函数（constraint functions）.

设S表示§的可行域，即
S : = { x ∈ X : g ( x ) ≤ 0 , h ( x ) = 0 } . S := \{x ∈ X : g(x) ≤ 0, h(x) = 0\}. S:={x∈X:g(x)≤0,h(x)=0}.

定 义 \large\color{magenta}{\boxed{\color{brown}{定义} }} 定义​ 如果满足 f ( x ˉ + ϵ d ˉ ) < f ( x ˉ ) f(\bar{x}+\epsilon \bar{d})<f(\bar{x}) f(xˉ+ϵdˉ)<f(xˉ) 对于所有 ϵ > 0 \epsilon>0 ϵ>0 和 ϵ \epsilon ϵ 充分小。方向 d ˉ \bar{d} dˉ 称为 f ( x ) f(x) f(x)在 x = x ˉ x=\bar{x} x=xˉ时的下降方向.则称 d ˉ \bar{d} dˉ为 f ( x ) f(x) f(x) 在点文处的下降方向。
F 0 = { d ˉ ∣ ∇ f ( x ˉ ) T d ˉ < 0 } F_{0}=\left\{\bar d \mid \nabla f(\bar{x})^{T}\bar d<0\right\} F0​={dˉ∣∇f(xˉ)Tdˉ<0}
定 义 \large\color{magenta}{\boxed{\color{brown}{定义} }} 定义​ 方向 d ˉ \bar{d} dˉ 称为 f ( x ) f(x) f(x)在 x = x ˉ x=\bar{x} x=xˉ时的可行下降方向.如果满足 x ˉ ∈ S , x ˉ + ϵ d ∈ S , \bar{x} \in S, \bar{x}+\epsilon d \in S, xˉ∈S,xˉ+ϵd∈S, 对于所有 ϵ > 0 \epsilon>0 ϵ>0 和 ϵ \epsilon ϵ 充分小。

2 最优性必要条件

几 何 必 要 条 件 \large\color{#70f3ff}{\boxed{\color{brown}{几何必要条件} }} 几何必要条件​

如果对于任何的 α > 0 α > 0 α>0,每一个 x ∈ C , α x ∈ C x∈C,αx∈C x∈C,αx∈C.那么集合 C ⊆ R n C⊆R^n C⊆Rn是锥体。

集合C是凸锥如果C是一个锥体和一个凸集。

对于 ( P ) (P) (P)，在 x ˉ ∈ S \bar{x}∈S xˉ∈S时，定义
$$
\begin{array}{}
&I(\bar{x}) = {i : g_i(\bar{x}) = 0}, \qquad &激活集、边界\

&F_0 = {d : ∇f(\bar{x})^Td < 0},\qquad &下降锥、改善\
&G_0 = {d : ∇g_i(\bar{x})^Td < 0, i ∈ I(\bar{x})}, \qquad &可行的锥,内部 \
&H_0 = {d : ∇h_i(\bar{x})^T d = 0, i = 1, · · · , l},\qquad &目标锥
\end{array}
$$
定 理 1 \large\color{magenta}{\boxed{\color{brown}{定理1} }} 定理1​假设 h ( x ) , g ( x ) h(x),g(x) h(x),g(x)是一个线性函数，即 h ( x ) = A x − b , A ∈ R l × n h(x) = Ax−b,A∈R^l×n h(x)=Ax−b,A∈Rl×n，如果 x ˉ \bar{x} xˉ是 ( P ) (P) (P)的局部最小值，则 F 0 ∩ G 0 ∩ H 0 = ∅ F_0∩G_0∩H_0 =∅ F0​∩G0​∩H0​=∅。

定 理 2 \large\color{magenta}{\boxed{\color{brown}{定理2} }} 定理2​若 x ˉ \bar{x} xˉ是一般问题 ( P ) (P) (P)的局部最小值，且梯度向量 ∇ h i ( x ˉ ) ， ∇ g i ( x ˉ ) i , = 1 ， ⋅ ⋅ ⋅ ， l ∇h_i(\bar{x})，∇g_i(\bar{x}) i ,= 1，···，l ∇hi​(xˉ)，∇gi​(xˉ)i,=1，⋅⋅⋅，l是线性无关的，则 F 0 ∩ G 0 ∩ H 0 = ∅ F_0∩G_0∩H_0 =∅ F0​∩G0​∩H0​=∅。

凸 集 的 分 离 \large\color{#70f3ff}{\boxed{\color{brown}{凸集的分离} }} 凸集的分离​

如果 p ≠ 0 p \neq 0 p​=0是一个向量，而 α α α是一个标量，则 H = { x : p T x = α } H = \{x : p^T x = α\} H={x:pTx=α}是一个超平面，且 H + = { x : p T x ≥ α } H^+ = \{x: p^T x≥α\} H+={x:pTx≥α}和 H − H ^- H−是半空间。

设 S S S和 T T T是 R n R^n Rn中的两个非空集。对于所有 x ∈ S x∈S x∈S，如果 p T x ≥ α p^T x≥α pTx≥α，对于所有 x ∈ T x∈T x∈T，如果 p T x ≤ α p^T x\leq α pTx≤α，则超平面 H = { x : p T x = α } H = \{x : p^T x = α\} H={x:pTx=α}将 S S S和 T T T分离，即 S ⊆ H + ， T ⊆ H − S⊆H^+， T⊆H^− S⊆H+，T⊆H−。另外，如果 S ∪ T S∪T S∪T不是 H H H的子集，那么 H H H就可以正确地分离 S S S和 T T T。

如果有 p T x > α p^T x>α pTx>α对所有 x ∈ S x∈S x∈S成立，而 p T x < α p^T x<α pTx<α对所有 x ∈ T x∈T x∈T，则 H H H将 S S S和 T T T严格分离。

H被认为将S和T强分离，如果对于某些 ε > 0 , p T x ≥ α + ε \varepsilon > 0, p^T x ≥ α + \varepsilon ε>0,pTx≥α+ε对所有 x ∈ S x∈S x∈S成立，和 ε > 0 , p T x ≤ α − ε \varepsilon > 0, p^T x \leq α - \varepsilon ε>0,pTx≤α−ε所有 x ∈ T x∈T x∈T成立。

定 理 3 \large\color{magenta}{\boxed{\color{brown}{定理3} }} 定理3​设 S S S是 R n R^n Rn中的一个非空闭凸集， y ∉ S y \notin S y∈/​S，则存在唯一的点 x ˉ ∈ S \bar{x}∈S xˉ∈S，其与 y y y的距离最小.而且,对于所有 x ∈ S x∈S x∈S, x ˉ \bar{x} xˉ是最小值点的充分必要条件是 ( y − x ˉ ) T ( x − x ˉ ) ≤ 0 (y−\bar{x})^T (x−\bar{x})≤0 (y−xˉ)T(x−xˉ)≤0时。

定 理 4 \large\color{magenta}{\boxed{\color{brown}{定理4} }} 定理4​设 S S S是 R n R^n Rn中的一个非空闭凸集， y ∉ S y \notin S y∈/​S，，则存在 p ≠ 0 p \neq 0 p​=0和$α ， 使 得 ，使得 ，使得H = {x : p^T x = α} 强 分 离 强分离 强分离S 和 和 和{y}$。

定 理 5 \large\color{magenta}{\boxed{\color{brown}{定理5} }} 定理5​假设 S 1 S_1 S1​和 S 2 S_2 S2​是不相交的非空闭凸集，且 S 1 S_1 S1​是有界的。那么 S 1 S_1 S1​和 S 2 S_2 S2​可以被一个超平面强分隔。

定 理 6 \large\color{magenta}{\boxed{\color{brown}{定理6} }} 定理6​(Farkas’ Lemma) 给出一个m×n矩阵 A A A和一个向量 c c c，正好有以下两方程个中的一个有解:
( 1 ) A x ≤ 0 , c T x > 0 ; ( 2 ) A T y = c , y ≥ 0. (1) Ax ≤ 0, c^T x > 0;\\ (2) A^T y = c, y ≥ 0. (1)Ax≤0,cTx>0;(2)ATy=c,y≥0.
定 理 7 \large\color{magenta}{\boxed{\color{brown}{定理7} }} 定理7​(Key Lemma) 给定维数适当的矩阵 A 、 B 、 H A、B、H A、B、H，恰好以下其中一个方程有解:
( 1 ) A x < 0 , B x ≤ 0 , H x = 0 ; ( 2 ) A T u + B T v + H T w = 0 , u ≥ 0 , v ≥ 0 , e T u = 1. \begin{aligned} &(1) Ax < 0, Bx ≤ 0, Hx = 0;\\ &(2) A^T u + B^T v + H^Tw = 0, u ≥ 0, v ≥ 0, e^T u = 1.\\ \end{aligned} ​(1)Ax<0,Bx≤0,Hx=0;(2)ATu+BTv+HTw=0,u≥0,v≥0,eTu=1.​
定 理 8 \large\color{magenta}{\boxed{\color{brown}{定理8} }} 定理8​**(Gordan’s Lemma)**给定m×n矩阵A，恰好以下两个方程中的一个有解:
( 1 ) A x < 0 , x ∈ R n ; ( 2 ) A T y = 0 , y ≥ 0 , y ≠ 0 , y ∈ R m . \begin{aligned} &(1) Ax < 0, x ∈ R^n;\\ &(2) A^T y = 0, y ≥ 0, y \neq 0, y ∈ R^m. \end{aligned} ​(1)Ax<0,x∈Rn;(2)ATy=0,y≥0,y​=0,y∈Rm.​

代 数 的 必 要 条 件 \large\color{#70f3ff}{\boxed{\color{brown}{代数的必要条件} }} 代数的必要条件​

定 理 9 \large\color{magenta}{\boxed{\color{brown}{定理9} }} 定理9​**( (F-J) 必要条件)**设 x ˉ \bar{x} xˉ是 ( P ) (P) (P)的可行解，如果 x ˉ \bar{x} xˉ是 ( P ) (P) (P)的局部最小值，则存在 ( u 0 , u , v ) (u_0, u, v) (u0​,u,v)满足
u 0 ∇ f ( x ˉ ) + ∑ i = 1 m u i ∇ g i ( x ˉ ) + ∑ i = 1 m ν i ∇ h i ( x ˉ ) = 0 u 0 , u ≥ 0 , ( u 0 , u , v ) ≠ 0 , u i g i ( x ˉ ) = 0 , i = 1 , ⋅ ⋅ ⋅ , m . u_0 \nabla f(\bar{x})+\sum_{i=1}^{m}u_i \nabla g_{i}(\bar{x})+\sum_{i=1}^{m}\nu _{i}\nabla h_{i}(\bar{x})=0\\ u_0, u ≥ 0,(u_0, u, v) \neq 0, \\ u_ig_i(\bar{x}) = 0, i = 1, · · · , m. u0​∇f(xˉ)+i=1∑m​ui​∇gi​(xˉ)+i=1∑m​νi​∇hi​(xˉ)=0u0​,u≥0,(u0​,u,v)​=0,ui​gi​(xˉ)=0,i=1,⋅⋅⋅,m.
第一个方程可以改写为
u 0 ∇ f ( x ˉ ) + ∇ g ( x ˉ ) T u + ∇ h ( x ˉ ) T v = 0 u_0 \nabla f(\bar{x})+ \nabla g_{}(\bar{x})^T u+\nabla h_{}(\bar{x})^T v=0\\ u0​∇f(xˉ)+∇g​(xˉ)Tu+∇h​(xˉ)Tv=0
对于问题§，定义拉格朗日函数:
L ( x , μ , v ) = f ( x ) + ∑ j = 1 m μ j g j ( x ) + ∑ k = 1 l v k h k ( x ) \displaystyle L\left(\mathbf{x},{\mu},{v}\right)=f(\mathbf{x})+\sum_{j=1}^m\mu_jg_j( \mathbf{x})+\sum_{k=1}^lv_kh_k(\mathbf{x})\\ L(x,μ,v)=f(x)+j=1∑m​μj​gj​(x)+k=1∑l​vk​hk​(x)
等价于
L ( x , μ , v ) = f ( x ) + μ T g ( x ) + v T h ( x ) \displaystyle L\left(\mathbf{x},{\mu},{v}\right)=f(\mathbf{x})+\mu ^Tg( \mathbf{x})+v^T h(\mathbf{x})\\ L(x,μ,v)=f(x)+μTg(x)+vTh(x)
满足 KKT 条件后极小化拉格朗日函数即可得到在不等式约束条件下的可行解。

定 理 10 \large\color{magenta}{\boxed{\color{brown}{定理10} }} 定理10​**( KKT必要条件)**设 x ˉ \bar{x} xˉ是 ( P ) (P) (P)的可行解，令$I(\bar{x})={i: g_i(\bar{x}) = 0} 。 进 一 步 ， 假 设 。进一步，假设 。进一步，假设\nabla h_{i}(\bar{x}),i = ,1, · · · , l , 和 对 于 ,和对于 ,和对于\nabla g_{i}(\bar{x}),i ∈ I(\bar{x}) 是 线 性 独 立 的 。 如 果 是线性独立的。如果 是线性独立的。如果\bar{x} 是 是 是§ 的 局 部 最 小 值 ， 那 么 存 在 的局部最小值，那么存在 的局部最小值，那么存在(u, v)$使得
∇ f ( x ˉ ) + ∇ g ( x ˉ ) T u + ∇ h ( x ˉ ) T v = 0 ( 1 ) 固 定 条 件 数 u ≥ 0 ( 2 ) 非 负 条 件 数 u i g i ( x ˉ ) = 0 , i = 1 , ⋅ ⋅ ⋅ , m . ( 3 ) 互 补 条 件 数 g ( x ˉ ) ≤ 0 ,     h ( x ˉ ) = 0 ( 4 ) 可 行 条 件 数 \begin{aligned} &\nabla f(\bar{x})+ \nabla g_{}(\bar{x})^T u+\nabla h_{}(\bar{x})^T v=0 \qquad &(1)固定条件数 \\ &u ≥ 0 & (2)非负条件数 \\ &u_ig_i(\bar{x}) = 0, i = 1, · · · , m. &(3)互补条件数\\ & g(\bar{x}) \leq 0, ~ ~ ~ h(\bar{x}) =0 &(4)可行条件数 \end{aligned} ​∇f(xˉ)+∇g​(xˉ)Tu+∇h​(xˉ)Tv=0u≥0ui​gi​(xˉ)=0,i=1,⋅⋅⋅,m.g(xˉ)≤0,   h(xˉ)=0​(1)固定条件数(2)非负条件数(3)互补条件数(4)可行条件数​

KKT 条件看起来很多，其实很好理解:

(1) ：拉格朗日取得可行解的必要条件；(3) ：称作松弛互补条件；

拉格朗日条件

拉格朗日条件是为了解决等式约束优化。问题描述：

min ⁡ x   f ( x ) s . t .     h i ( x ) = 0 , i = 1 , 2 , . . . , m \begin{aligned} &\min_{x } \ f(x) \\ &s.t. \ \ \ h_i(x) = 0 , i = 1,2,...,m \\ \end{aligned} ​xmin​ f(x)s.t.   hi​(x)=0,i=1,2,...,m​
约束条件会将解的范围限定在一个可行域，此时不一定能找到使得 ∇ x f ( x ) \nabla_xf(x) ∇x​f(x) 为 0 的点，只需找到在可行域内使得 f ( x ) f(x) f(x) 最小的值即可，常用的方法即为拉格朗日乘子法，该方法首先引入 拉格朗日乘子 λ ∈ R m \lambda \in \mathbb{R}^m λ∈Rm ，构建 Lagrangian 如下：
L ( x , λ ) = f ( x ) + ∑ i = 1 m λ i h i ( x ) L(x,\lambda) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) L(x,λ)=f(x)+i=1∑m​λi​hi​(x)
求解方法如下：首先对 Lagrangian 关于 λ \lambda λ 与 x x x 求 ：
{ ∇ x L ( x , λ ) = 0 ∇ λ L ( x , λ ) = 0 \left \{ \begin{aligned} \nabla_x L(x,\lambda)= 0 \\ \nabla_{ \lambda } L(x,\lambda)= 0 \end{aligned} \right. {∇x​L(x,λ)=0∇λ​L(x,λ)=0​
令导数为 0 ，求得 x 、 λ x 、\lambda x、λ 的值后，将 x x x 带入 f ( x ) f(x) f(x) 即为在约束条件 h i ( x ) h_i(x) hi​(x) 下的可行解。这样做的意义是什么呢? 接下来看一个直观的示例，对于二维情况下的目标函数是 f ( x , y ) f(x,y) f(x,y)，在平面中画出 f ( x , y ) f(x,y) f(x,y) 的等高线，如下图的虚线所示， 并只给出一个约束等式 h ( x , y ) = 0 h(x,y)=0 h(x,y)=0 ，如下图的绿线所示，目标函数 f ( x , y ) f(x,y) f(x,y) 与约束 h ( x , y ) h(x,y) h(x,y) 只有三种情况，相交、相切或者没有交集，没交集肯定不是解,只有相交或者相切可能是解，但相交得到的一定不是最优值，因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，这就意味着只有等高线与目标函数的曲线相切的时候，才可能得到可行解.

因此给出结论：拉格朗日乘子法取得极值的必要条件是目标函数与约束函数相切，这时两者的法向量是平行的，即
∇ x f ( x ) – λ ∇ x h ( x ) = 0 \nabla _xf(x) – \lambda \nabla_xh(x) = 0 ∇x​f(x)–λ∇x​h(x)=0
所以只要满足上述等式，且满足之前的约束 h i ( x ) = 0 , i = 1 , 2 , … , m ， h_i(x) = 0 , i = 1,2,…,m， hi​(x)=0,i=1,2,…,m，即可得到解，联立起来，正好得到就是拉格朗日乘子法。这里只是直观展示了一下拉格朗日乘子法的几何推导 ，并没有给出详细的证明。

**正则点：**对于满足约束 h 1 ( x ∗ ) = 0 , ⋯   , h m ( x ∗ ) h_{1}(\mathbf{x}^{*}) = 0, \cdots, h_{m}(\mathbf{x^{*}}) h1​(x∗)=0,⋯,hm​(x∗) 的点 x ∗ x^{*} x∗ ，如果梯度向量 ∇ h 1 ( x ∗ ) , ⋯   , ∇ h m ( x ∗ ) \nabla{h}_{1}(\mathbf{x}^{*}), \cdots, \nabla{h}_{m}(\mathbf{x}^{*}) ∇h1​(x∗),⋯,∇hm​(x∗) 线性无关，则称点 x ∗ x^{*} x∗ 为该约束的一个正则点。

已知
D h ( x ) = [ D h 1 ( x ) ⋮ D h m ( x ) ] = [ ∇ h 1 ( x ) T ⋮ ∇ h m ( x ) T ] \mathrm{D}\mathbf{h}(\mathbf{x}) = \left[ \begin{array}{c} \mathrm{D}h_{1}(\mathbf{x})\\ \vdots\\ \mathrm{D}h_{m}(\mathbf{x}) \end{array} \right] = \left[ \begin{array}{c} \nabla{h}_{1}(\mathbf{x})^{T}\\ \vdots\\ \nabla{h}_{m}(\mathbf{x})^{T} \end{array} \right] Dh(x)=⎣⎢⎡​Dh1​(x)⋮Dhm​(x)​⎦⎥⎤​=⎣⎢⎡​∇h1​(x)T⋮∇hm​(x)T​⎦⎥⎤​
拉格朗日定理：

x ∗ \mathbf{x}^{*} x∗ 为 f f f 的极值点，且为正则点，则存在 λ ∗ ∈ R m \mathbf{\lambda ^{*} }\in R^{m} λ∗∈Rm ,使得 D f ( x ∗ ) + λ T D h ( x ∗ ) = 0 T \mathrm{D}{f}(\mathbf{x}^{*}) + \mathbf{\lambda}^{T}\mathrm{D}{\mathbf{h}}(\mathbf{x}^{*}) = \mathbf{0}^{T} Df(x∗)+λTDh(x∗)=0T,极小值点存在二阶必要条件和充分条件。

不等式约束优化

当约束加上不等式之后，情况变得更加复杂，首先来看一个简单的情况，给定如下不等式约束问题：
min ⁡ x   f ( x )   s . t .    g ( x ) ≤ 0 \begin{aligned} &\min_x \ f(x) \\ & \ s.t. \ \ g(x) \le 0 \end{aligned} ​xmin​ f(x) s.t.  g(x)≤0​
对应的拉格朗日方程与图形分别如下所示：
L ( x , λ ) = f ( x ) + λ g ( x ) L(x, \lambda) = f(x) + \lambda g(x) L(x,λ)=f(x)+λg(x)
这时的可行解必须落在约束区域 g ( x ) g(x) g(x) 之内，下图给出了目标函数的等高线与约束：

由图可见可行解 x x x 只能在 g ( x ) < 0 g(x)<0 g(x)<0 或者 g ( x ) = 0 g(x)=0 g(x)=0 的区域里取得：

• 当可行解 x x x 落在 g ( x ) < 0 g(x)<0 g(x)<0的区域内，此时直接极小化 f ( x ) f(x) f(x)即可；
• 当可行解 x x x 落在 g ( x ) = 0 g(x)=0 g(x)=0 即边界上，此时等价于等式约束优化问题.

当约束区域包含目标函数原有的的可行解时，此时加上约束可行解扔落在约束区域内部，对应 g ( x ) < 0 g(x)<0 g(x)<0 的情况，这时约束条件不起作用；当约束区域不包含目标函数原有的可行解时，此时加上约束后可行解落在边界 g ( x ) = 0 g(x)=0 g(x)=0 上。下图分别描述了两种情况，右图表示加上约束可行解会落在约束区域的边界上。

以上两种情况就是说，要么可行解落在约束边界上即得 g ( x ) = 0 g(x)=0 g(x)=0 ，要么可行解落在约束区域内部，此时约束不起作用，另 λ = 0 \lambda = 0 λ=0 消去约束即可，所以无论哪种情况都会得到：
λ g ( x ) = 0 \lambda g(x) = 0 λg(x)=0
还有一个问题是 λ \lambda λ 的取值，在等式约束优化中，约束函数与目标函数的梯度只要满足平行即可，而在不等式约束中则不然，若 λ ≠ 0 \lambda \ne 0 λ​=0，这便说明 可行解 x x x 是落在约束区域的边界上的，这时可行解应尽量靠近无约束时的解，所以在约束边界上，目标函数的负梯度方向应该远离约束区域朝向无约束时的解，此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同：
− ∇ x f ( x ) = λ ∇ x g ( x ) -\nabla_x f(x) = \lambda \nabla_xg(x) −∇x​f(x)=λ∇x​g(x)
上式需要满足的要求是拉格朗日乘子 λ > 0 \lambda>0 λ>0 ，这个问题可以举一个形象的例子，假设你去爬山，目标是山顶，但有一个障碍挡住了通向山顶的路，所以只能沿着障碍爬到尽可能靠近山顶的位置，然后望着山顶叹叹气，这里山顶便是目标函数的可行解，障碍便是约束函数的边界，此时的梯度方向一定是指向山顶的，与障碍的梯度同向，下图描述了这种情况 :

可见对于不等式约束，只要满足一定的条件，依然可以使用拉格朗日乘子法解决，这里的条件便是 KKT 条件。

例1

确定 x ˉ = ( 7 6 ) \bar{x}=\left(\begin{array}{l}7 \\ 6\end{array}\right) xˉ=(76​) 是否是下面问题的最小解:
min ⁡ f ( x ) = 6 ( x 1 − 10 ) 2 + 4 ( x 2 − 12.5 ) 2  s.t.  g 1 ( x ) = x 1 2 + ( x 2 − 5 ) 2 − 50 ≤ 0 g 2 ( x ) = x 1 2 + 3 x 2 2 − 200 ≤ 0 g 3 ( x ) = ( x 1 − 6 ) 2 + x 2 2 − 37 ≤ 0 \begin{array}{ll} \min & f(x)=6\left(x_{1}-10\right)^{2}+4\left(x_{2}-12.5\right)^{2} \\ \text { s.t. } & g_{1}(x)=x_{1}^{2}+\left(x_{2}-5\right)^{2}-50 \leq 0 \\ & g_{2}(x)=x_{1}^{2}+3 x_{2}^{2}-200 \leq 0 \\ & g_{3}(x)=\left(x_{1}-6\right)^{2}+x_{2}^{2}-37 \leq 0 \end{array} min s.t. ​f(x)=6(x1​−10)2+4(x2​−12.5)2g1​(x)=x12​+(x2​−5)2−50≤0g2​(x)=x12​+3x22​−200≤0g3​(x)=(x1​−6)2+x22​−37≤0​
【解】
∇ f ( x ) = ( 12 x 1 − 120 8 x 2 − 100 ) , ∇ g 1 ( x ) = ( 2 x 1 2 x 2 − 10 ) ∇ g 2 ( x ) = ( 2 x 1 6 x 2 ) , ∇ g 3 ( x ) = ( 2 x 1 − 12 2 x 2 ) \begin{array}{l} \nabla f(x)=\left(\begin{array}{c} 12 x_{1}-120 \\ 8 x_{2}-100 \end{array}\right), \nabla g_{1}(x)=\left(\begin{array}{c} 2 x_{1} \\ 2 x_{2}-10 \end{array}\right) \\ \nabla g_{2}(x)=\left(\begin{array}{c} 2 x_{1} \\ 6 x_{2} \end{array}\right), \nabla g_{3}(x)=\left(\begin{array}{c} 2 x_{1}-12 \\ 2 x_{2} \end{array}\right) \end{array} ∇f(x)=(12x1​−1208x2​−100​),∇g1​(x)=(2x1​2x2​−10​)∇g2​(x)=(2x1​6x2​​),∇g3​(x)=(2x1​−122x2​​)​
满足如下的KKT条件：
∇ f ( x ) + u 1 ∇ g 1 ( x ) + u 2 ∇ g 2 ( x ) + u 3 ∇ g 3 ( x ) = 0 \nabla f(x)+u_{1} \nabla g_{1}(x)+u_{2} \nabla g_{2}(x)+u_{3} \nabla g_{3}(x)=0 ∇f(x)+u1​∇g1​(x)+u2​∇g2​(x)+u3​∇g3​(x)=0
u 1 g 1 ( x ) = 0 , u 2 g 2 ( x ) = 0 , u 3 g 3 ( x ) = 0 u 1 ≥ 0 , u 2 ≥ 0 , u 3 ≥ 0 g 1 ( x ) ≤ 0 , g 2 ( x ) ≤ 0 , g 3 ( x ) ≤ 0 \begin{array}{l} u_{1} g_{1}(x)=0, u_{2} g_{2}(x)=0, u_{3} g_{3}(x)=0 \\ u_{1} \geq 0, u_{2} \geq 0, u_{3} \geq 0 \\ g_{1}(x) \leq 0, g_{2}(x) \leq 0, g_{3}(x) \leq 0 \end{array} u1​g1​(x)=0,u2​g2​(x)=0,u3​g3​(x)=0u1​≥0,u2​≥0,u3​≥0g1​(x)≤0,g2​(x)≤0,g3​(x)≤0​

(1) 检查的可行性。
g 1 ( x ˉ ) = x 1 2 + ( x 2 − 5 ) 2 − 50 = 0 ≤ 0 g 2 ( x ˉ ) = x 1 2 + 3 x 2 2 − 200 = − 43 < 0 g 3 ( x ˉ ) = ( x 1 − 6 ) 2 + x 2 2 − 37 = 0 ≤ 0 \begin{array}{l} g_{1}(\bar{x})=x_{1}^{2}+\left(x_{2}-5\right)^{2}-50=0 \leq 0 \\ g_{2}(\bar{x})=x_{1}^{2}+3 x_{2}^{2}-200=-43<0 \\ g_{3}(\bar{x})=\left(x_{1}-6\right)^{2}+x_{2}^{2}-37=0 \leq 0 \end{array} g1​(xˉ)=x12​+(x2​−5)2−50=0≤0g2​(xˉ)=x12​+3x22​−200=−43<0g3​(xˉ)=(x1​−6)2+x22​−37=0≤0​
因此, x ˉ \bar{x} xˉ 满足可行性。

（2）考虑固定条件
∇ f ( x ˉ ) = ( − 36 − 52 ) , ∇ g 1 ( x ˉ ) = ( 14 2 ) ∇ g 2 ( x ˉ ) = ( 14 36 ) , ∇ g 3 ( x ˉ ) = ( 2 12 ) \begin{array}{l} \nabla f(\bar{x})=\left(\begin{array}{l} -36 \\ -52 \end{array}\right), \nabla g_{1}(\bar{x})=\left(\begin{array}{c} 14 \\ 2 \end{array}\right) \\ \nabla g_{2}(\bar{x})=\left(\begin{array}{c} 14 \\ 36 \end{array}\right), \nabla g_{3}(\bar{x})=\left(\begin{array}{c} 2 \\ 12 \end{array}\right) \end{array} ∇f(xˉ)=(−36−52​),∇g1​(xˉ)=(142​)∇g2​(xˉ)=(1436​),∇g3​(xˉ)=(212​)​
所以满足：
( − 36 − 52 ) + u 1 ( 14 2 ) + u 2 ( 14 36 ) + u 3 ( 2 12 ) = ( 0 0 ) \left(\begin{array}{l} -36 \\ -52 \end{array}\right)+u_{1}\left(\begin{array}{c} 14 \\ 2 \end{array}\right)+u_{2}\left(\begin{array}{c} 14 \\ 36 \end{array}\right)+u_{3}\left(\begin{array}{c} 2 \\ 12 \end{array}\right)=\left(\begin{array}{l} 0 \\ 0 \end{array}\right) (−36−52​)+u1​(142​)+u2​(1436​)+u3​(212​)=(00​)
3): 考虑非负和互补的条件. 因为 g 2 ( x ˉ ) < 0 , g_{2}(\bar{x})<0, g2​(xˉ)<0, 得到 u 2 = 0 , u_{2}=0, u2​=0, 所以
{ 14 u 1 + 2 u 3 = 36 2 u 1 + 12 u 3 = 52 ⟹ { u 1 = 2 > 0 u 3 = 4 > 0 \left\{\begin{array}{l} 14 u_{1}+2 u_{3}=36 \\ 2 u_{1}+12 u_{3}=52 \end{array} \Longrightarrow\left\{\begin{array}{l} u_{1}=2>0 \\ u_{3}=4>0 \end{array}\right.\right. {14u1​+2u3​=362u1​+12u3​=52​⟹{u1​=2>0u3​=4>0​
因此, x ˉ = ( 7 6 ) \bar{x}=\left(\begin{array}{l}7 \\ 6\end{array}\right) xˉ=(76​) 是 K K T \mathrm{KKT} KKT 点, 乘数是
( u 1 u 2 u 3 ) = ( 2 0 4 ) \left(\begin{array}{l} u_{1} \\ u_{2} \\ u_{3} \end{array}\right)=\left(\begin{array}{l} 2 \\ 0 \\ 4 \end{array}\right) ⎝⎛​u1​u2​u3​​⎠⎞​=⎝⎛​204​⎠⎞​

例2

找到以下问题的KKT点:
min ⁡ f ( x ) = ( x 1 − 1 ) 2 + x 2  s.t.  g 1 ( x ) = x 1 + x 2 − 2 ≤ 0 g 2 ( x ) = − x 2 ≤ 0 \begin{array}{ll} \min & f(x)=\left(x_{1}-1\right)^{2}+x_{2} \\ \text { s.t. } & g_{1}(x)=x_{1}+x_{2}-2 \leq 0 \\ & g_{2}(x)=-x_{2} \leq 0 \end{array} min s.t. ​f(x)=(x1​−1)2+x2​g1​(x)=x1​+x2​−2≤0g2​(x)=−x2​≤0​
【解】
∇ f ( x ) = ( 2 x 1 − 2 1 ) , ∇ g 1 ( x ) = ( 1 1 ) , ∇ g 2 ( x ) = ( 0 − 1 ) \nabla f(x)=\left(\begin{array}{c} 2 x_{1}-2 \\ 1 \end{array}\right), \nabla g_{1}(x)=\left(\begin{array}{c} 1 \\ 1 \end{array}\right), \nabla g_{2}(x)=\left(\begin{array}{c} 0 \\ -1 \end{array}\right) ∇f(x)=(2x1​−21​),∇g1​(x)=(11​),∇g2​(x)=(0−1​)
满足如下的KKT条件：
∇ f ( x ) + u 1 ∇ g 1 ( x ) + u 2 ∇ g 2 ( x ) = 0 u 1 g 1 ( x ) = 0 , u 2 g 2 ( x ) = 0 u 1 ≥ 0 , u 2 ≥ 0 g 1 ( x ) ≤ 0 , g 2 ( x ) ≤ 0 \begin{array}{l} \nabla f(x)+u_{1} \nabla g_{1}(x)+u_{2} \nabla g_{2}(x)=0 \\ u_{1} g_{1}(x)=0, u_{2} g_{2}(x)=0 \\ u_{1} \geq 0, u_{2} \geq 0 \\ g_{1}(x) \leq 0, g_{2}(x) \leq 0 \end{array} ∇f(x)+u1​∇g1​(x)+u2​∇g2​(x)=0u1​g1​(x)=0,u2​g2​(x)=0u1​≥0,u2​≥0g1​(x)≤0,g2​(x)≤0​
即
{ 2 ( x 1 − 1 ) + u 1 = 0 1 + u 1 − u 2 = 0 u 1 ( x 1 + x 2 − 2 ) = 0 − u 2 x 2 = 0 u 1 ≥ 0 , u 2 ≥ 0 x 1 + x 2 − 2 ≤ 0 − x 2 ≤ 0 \left\{\begin{array}{l} 2\left(x_{1}-1\right)+u_{1}=0 \\ 1+u_{1}-u_{2}=0 \\ u_{1}\left(x_{1}+x_{2}-2\right)=0 \\ -u_{2} x_{2}=0 \\ u_{1} \geq 0, u_{2} \geq 0 \\ x_{1}+x_{2}-2 \leq 0 \\ -x_{2} \leq 0 \end{array}\right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​2(x1​−1)+u1​=01+u1​−u2​=0u1​(x1​+x2​−2)=0−u2​x2​=0u1​≥0,u2​≥0x1​+x2​−2≤0−x2​≤0​
如果 u 2 = 0 , u_{2}=0, u2​=0, 则 u 1 = − 1 , u_{1}=-1, u1​=−1, 不满足条件. 因此 x 2 = 0 , u 2 ≠ 0 , x_{2}=0, u_{2} \neq 0, x2​=0,u2​​=0, 然后得到
{ 2 ( x 1 − 1 ) + u 1 = 0 1 + u 1 − u 2 = 0 u 1 ( x 1 − 2 ) = 0 u 1 ≥ 0 , u 2 ≥ 0 x 1 − 2 ≤ 0 \left\{\begin{array}{l} 2\left(x_{1}-1\right)+u_{1}=0 \\ 1+u_{1}-u_{2}=0 \\ u_{1}\left(x_{1}-2\right)=0 \\ u_{1} \geq 0, u_{2} \geq 0 \\ x_{1}-2 \leq 0 \end{array}\right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​2(x1​−1)+u1​=01+u1​−u2​=0u1​(x1​−2)=0u1​≥0,u2​≥0x1​−2≤0​
如果 x 1 − 2 = 0 , x_{1}-2=0, x1​−2=0,则 u 1 = − 2 , u_{1}=-2, u1​=−2, 不满足条件. 因此
u 1 = 0 , u 2 = 1 , x 1 = 1 u_{1}=0, u_{2}=1, x_{1}=1 u1​=0,u2​=1,x1​=1
解的
x ˉ = ( 7 6 ) , u = ( u 1 u 2 ) = ( 0 1 ) \bar{x}=\left(\begin{array}{l} 7 \\ 6 \end{array}\right), u=\left(\begin{array}{l} u_{1} \\ u_{2} \end{array}\right)=\left(\begin{array}{l} 0 \\ 1 \end{array}\right) xˉ=(76​),u=(u1​u2​​)=(01​)

例3

找到以下问题的KKT点:
min ⁡ f ( x ) = 2 x 1 2 + 2 x 1 x 2 + x 2 2 − 10 x 1 − 10 x 2  s.t.  g 1 ( x ) = x 1 2 + x 2 2 − 5 ≤ 0 g 2 ( x ) = 3 x 1 + x 2 − 6 ≤ 0 \begin{array}{ll} \min & f(x)=2 x_{1}^{2}+2 x_{1} x_{2}+x_{2}^{2}-10 x_{1}-10 x_{2} \\ \text { s.t. } & g_{1}(x)=x_{1}^{2}+x_{2}^{2}-5 \leq 0 \\ & g_{2}(x)=3 x_{1}+x_{2}-6 \leq 0 \end{array} min s.t. ​f(x)=2x12​+2x1​x2​+x22​−10x1​−10x2​g1​(x)=x12​+x22​−5≤0g2​(x)=3x1​+x2​−6≤0​
【解】
∇ f ( x ) = ( 4 x 1 + 2 x 2 − 10 2 x 1 + 2 x 2 − 10 ) , ∇ g 1 ( x ) = ( 2 x 1 2 x 2 ) , ∇ g 2 ( x ) = ( 3 1 ) \nabla f(x)=\left(\begin{array}{c} 4 x_{1}+2 x_{2}-10 \\ 2 x_{1}+2 x_{2}-10 \end{array}\right), \nabla g_{1}(x)=\left(\begin{array}{c} 2 x_{1} \\ 2 x_{2} \end{array}\right), \nabla g_{2}(x)=\left(\begin{array}{l} 3 \\ 1 \end{array}\right) ∇f(x)=(4x1​+2x2​−102x1​+2x2​−10​),∇g1​(x)=(2x1​2x2​​),∇g2​(x)=(31​)
满足如下的KKT条件：
∇ f ( x ) + ∑ i = 1 2 u i ∇ g i ( x ) = 0 u i g i ( x ) = 0 , i = 1 , 2 u i ≥ 0 , i = 1 , 2 g i ( x ) ≤ 0 , i = 1 , 2 \begin{array}{l} \nabla f(x)+\sum_{i=1}^{2} u_{i} \nabla g_{i}(x)=0 \\ u_{i} g_{i}(x)=0, i=1,2 \\ u_{i} \geq 0, i=1,2 \\ g_{i}(x) \leq 0, i=1,2 \end{array} ∇f(x)+∑i=12​ui​∇gi​(x)=0ui​gi​(x)=0,i=1,2ui​≥0,i=1,2gi​(x)≤0,i=1,2​
即
{ 4 x 1 + 2 x 2 − 10 + 2 u 1 x 1 + 3 u 2 = 0 2 x 1 + 2 x 2 − 10 + 2 u 1 x 2 + u 2 = 0 u 1 ( x 1 2 + x 2 2 − 5 ) = 0 u 2 ( 3 x 1 + x 2 − 6 ) = 0 u 1 ≥ 0 , u 2 ≥ 0 x 1 2 + x 2 2 − 5 ≤ 0 3 x 1 + x 2 − 6 ≤ 0 \left\{\begin{array}{l} 4 x_{1}+2 x_{2}-10+2 u_{1} x_{1}+3 u_{2}=0 \\ 2 x_{1}+2 x_{2}-10+2 u_{1} x_{2}+u_{2}=0 \\ u_{1}\left(x_{1}^{2}+x_{2}^{2}-5\right)=0 \\ u_{2}\left(3 x_{1}+x_{2}-6\right)=0 \\ u_{1} \geq 0, u_{2} \geq 0 \\ x_{1}^{2}+x_{2}^{2}-5 \leq 0 \\ 3 x_{1}+x_{2}-6 \leq 0 \end{array}\right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​4x1​+2x2​−10+2u1​x1​+3u2​=02x1​+2x2​−10+2u1​x2​+u2​=0u1​(x12​+x22​−5)=0u2​(3x1​+x2​−6)=0u1​≥0,u2​≥0x12​+x22​−5≤03x1​+x2​−6≤0​
考虑以下情况:

（1）如果 u 1 = u 2 = 0 u_{1}=u_{2}=0 u1​=u2​=0, 则
{ 4 x 1 + 2 x 2 − 10 = 0 2 x 1 + 2 x 2 − 10 = 0 ⟹ { x 1 = 0 x 2 = 5 \left\{\begin{array}{l} 4 x_{1}+2 x_{2}-10=0 \\ 2 x_{1}+2 x_{2}-10=0 \end{array} \Longrightarrow\left\{\begin{array}{l} x_{1}=0 \\ x_{2}=5 \end{array}\right.\right. {4x1​+2x2​−10=02x1​+2x2​−10=0​⟹{x1​=0x2​=5​
因此, x 1 2 + x 2 2 − 5 = 20 > 0 , x_{1}^{2}+x_{2}^{2}-5=20>0, x12​+x22​−5=20>0, 不满足条件.

(2)如果 u 1 > 0 , u 2 = 0 , u_{1}>0, u_{2}=0, u1​>0,u2​=0, 则
{ 4 x 1 + 2 x 2 − 10 + 2 u 1 x 1 = 0 2 x 1 + 2 x 2 − 10 + 2 u 1 x 2 = 0 x 1 2 + x 2 2 − 5 = 0 3 x 1 + x 2 − 6 ≤ 0 ⟹ { x 1 = 1 x 2 = 2 u 1 = 1 u 2 = 0 \left\{\begin{array}{l} 4 x_{1}+2 x_{2}-10+2 u_{1} x_{1}=0 \\ 2 x_{1}+2 x_{2}-10+2 u_{1} x_{2}=0 \\ x_{1}^{2}+x_{2}^{2}-5=0 \\ 3 x_{1}+x_{2}-6 \leq 0 \end{array} \quad \Longrightarrow\left\{\begin{array}{l} x_{1}=1 \\ x_{2}=2 \\ u_{1}=1 \\ u_{2}=0 \end{array}\right.\right. ⎩⎪⎪⎨⎪⎪⎧​4x1​+2x2​−10+2u1​x1​=02x1​+2x2​−10+2u1​x2​=0x12​+x22​−5=03x1​+x2​−6≤0​⟹⎩⎪⎪⎨⎪⎪⎧​x1​=1x2​=2u1​=1u2​=0​
因此
x ˉ = ( 1 2 ) , u = ( u 1 u 2 ) = ( 0 1 ) \bar{x}=\left(\begin{array}{l} 1 \\ 2 \end{array}\right), u=\left(\begin{array}{l} u_{1} \\ u_{2} \end{array}\right)=\left(\begin{array}{l} 0 \\ 1 \end{array}\right) xˉ=(12​),u=(u1​u2​​)=(01​)
(3) 如果 u 1 = 0 , u 2 > 0 u_{1}=0, u_{2}>0 u1​=0,u2​>0, 则
{ 4 x 1 + 2 x 2 − 10 + 3 u 2 = 0 2 x 1 + 2 x 2 − 10 + u 2 = 0 x 1 2 + x 2 2 − 5 ≤ 0 3 x 1 + x 2 − 6 = 0 ⟹ { x 1 = 2 5 x 2 = 24 5 u 2 = − 2 5 < 0 \left\{\begin{array}{l} 4 x_{1}+2 x_{2}-10+3 u_{2}=0 \\ 2 x_{1}+2 x_{2}-10+u_{2}=0 \\ x_{1}^{2}+x_{2}^{2}-5 \leq 0 \\ 3 x_{1}+x_{2}-6=0 \end{array} \quad \Longrightarrow\left\{\begin{array}{l} x_{1}=\frac{2}{5} \\ x_{2}=\frac{24}{5} \\ u_{2}=-\frac{2}{5}<0 \end{array}\right.\right. ⎩⎪⎪⎨⎪⎪⎧​4x1​+2x2​−10+3u2​=02x1​+2x2​−10+u2​=0x12​+x22​−5≤03x1​+x2​−6=0​⟹⎩⎨⎧​x1​=52​x2​=524​u2​=−52​<0​
不满足条件.

(4) 如果 u 1 > 0 , u 2 > 0 , u_{1}>0, u_{2}>0, u1​>0,u2​>0, 则
{ x 1 2 + x 2 2 − 5 = 0 3 x 1 + x 2 − 6 = 0 \left\{\begin{array}{l} x_{1}^{2}+x_{2}^{2}-5=0 \\ 3 x_{1}+x_{2}-6=0 \end{array}\right. {x12​+x22​−5=03x1​+x2​−6=0​
不满足条件.

例4

找到以下问题的KKT点:
min ⁡ f ( x ) = x 1 2 + x 2  s.t.  g 1 ( x ) = x 1 2 + x 2 2 − 9 ≤ 0 g 2 ( x ) = x 1 + x 2 − 1 ≤ 0 \begin{array}{ll} \min & f(x)=x_{1}^{2}+x_{2} \\ \text { s.t. } & g_{1}(x)=x_{1}^{2}+x_{2}^{2}-9 \leq 0 \\ & g_{2}(x)=x_{1}+x_{2}-1 \leq 0 \end{array} min s.t. ​f(x)=x12​+x2​g1​(x)=x12​+x22​−9≤0g2​(x)=x1​+x2​−1≤0​
【解】
∇ f ( x ) = ( 2 x 1 1 ) , ∇ g 1 ( x ) = ( 2 x 1 2 x 2 ) , ∇ g 2 ( x ) = ( 1 1 ) \nabla f(x)=\left(\begin{array}{c} 2 x_{1} \\ 1 \end{array}\right), \nabla g_{1}(x)=\left(\begin{array}{c} 2 x_{1} \\ 2 x_{2} \end{array}\right), \nabla g_{2}(x)=\left(\begin{array}{c} 1 \\ 1 \end{array}\right) ∇f(x)=(2x1​1​),∇g1​(x)=(2x1​2x2​​),∇g2​(x)=(11​)
满足如下的KKT条件：
∇ f ( x ) + ∑ i = 1 2 u i ∇ g i ( x ) = 0 u i g i ( x ) = 0 , i = 1 , 2 u i ≥ 0 , i = 1 , 2 g i ( x ) ≤ 0 , i = 1 , 2 \begin{array}{l} \nabla f(x)+\sum_{i=1}^{2} u_{i} \nabla g_{i}(x)=0 \\ u_{i} g_{i}(x)=0, i=1,2 \\ u_{i} \geq 0, i=1,2 \\ g_{i}(x) \leq 0, i=1,2 \end{array} ∇f(x)+∑i=12​ui​∇gi​(x)=0ui​gi​(x)=0,i=1,2ui​≥0,i=1,2gi​(x)≤0,i=1,2​
即
{ 2 x 1 + 2 u 1 x 1 + u 2 = 0 1 + 2 u 1 x 2 + u 2 = 0 u 1 ( x 1 2 + x 2 2 − 9 ) = 0 u 2 ( x 1 + x 2 − 1 ) = 0 u 1 ≥ 0 , u 2 ≥ 0 x 1 2 + x 2 2 − 9 ≤ 0 x 1 + x 2 − 1 ≤ 0 \left\{\begin{array}{l} 2 x_{1}+2 u_{1} x_{1}+u_{2}=0 \\ 1+2 u_{1} x_{2}+u_{2}=0 \\ u_{1}\left(x_{1}^{2}+x_{2}^{2}-9\right)=0 \\ u_{2}\left(x_{1}+x_{2}-1\right)=0 \\ u_{1} \geq 0, u_{2} \geq 0 \\ x_{1}^{2}+x_{2}^{2}-9 \leq 0 \\ x_{1}+x_{2}-1 \leq 0 \end{array}\right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​2x1​+2u1​x1​+u2​=01+2u1​x2​+u2​=0u1​(x12​+x22​−9)=0u2​(x1​+x2​−1)=0u1​≥0,u2​≥0x12​+x22​−9≤0x1​+x2​−1≤0​
考虑以下情况:
(1) 如果 g 1 ( x ) < 0 , u 1 = 0 , ⟹ u 2 = − 1 , g_{1}(x)<0, u_{1}=0, \Longrightarrow u_{2}=-1, g1​(x)<0,u1​=0,⟹u2​=−1, 不满足条件.
(2) 如果 g 1 ( x ) = 0 , g 2 ( x ) < 0 , u 2 = 0 , g_{1}(x)=0, g_{2}(x)<0, u_{2}=0, g1​(x)=0,g2​(x)<0,u2​=0, 则
{ x 1 ( 1 + u 1 ) = 0 1 + 2 u 1 x 2 = 0 x 1 2 + x 2 2 − 9 = 0 ⟹ { x 1 = 0 x 2 = − 3 u 1 = 1 6 u 2 = 0 \left\{\begin{array}{l} x_{1}\left(1+u_{1}\right)=0 \\ 1+2 u_{1} x_{2}=0 \\ x_{1}^{2}+x_{2}^{2}-9=0 \end{array} \quad \Longrightarrow\left\{\begin{array}{l} x_{1}=0 \\ x_{2}=-3 \\ u_{1}=\frac{1}{6} \\ u_{2}=0 \end{array}\right.\right. ⎩⎪⎪⎨⎪⎪⎧​x1​(1+u1​)=01+2u1​x2​=0x12​+x22​−9=0​⟹⎩⎪⎪⎨⎪⎪⎧​x1​=0x2​=−3u1​=61​u2​=0​
因此
x ˉ = ( 0 − 3 ) , u = ( u 1 u 2 ) = ( 1 6 0 ) \bar{x}=\left(\begin{array}{c} 0 \\ -3 \end{array}\right), u=\left(\begin{array}{c} u_{1} \\ u_{2} \end{array}\right)=\left(\begin{array}{c} \frac{1}{6} \\ 0 \end{array}\right) xˉ=(0−3​),u=(u1​u2​​)=(61​0​)
(3) 如果 g 1 ( x ) = 0 , g 2 ( x ) = 0 , g_{1}(x)=0, g_{2}(x)=0, g1​(x)=0,g2​(x)=0, 则
{ x 1 2 + x 2 2 − 9 = 0 x 1 + x 2 − 1 = 0 ⟹ { x 1 = 1 ± 17 2 x 2 = 1 ∓ 17 2 u 2 = − 2 5 < 0 \left\{\begin{array}{l} x_{1}^{2}+x_{2}^{2}-9=0 \\ x_{1}+x_{2}-1=0 \end{array} \Longrightarrow\left\{\begin{array}{l} x_{1}=\frac{1 \pm \sqrt{17}}{2} \\ x_{2}=\frac{1 \mp \sqrt{17}}{2} \\ u_{2}=-\frac{2}{5}<0 \end{array}\right.\right. ⎩⎪⎨⎪⎧​x12​+x22​−9=0x1​+x2​−1=0​⟹⎩⎪⎨⎪⎧​x1​=21±17 ​​x2​=21∓17 ​​u2​=−52​<0​
因此
{ 2 x 1 + 2 u 1 x 1 + u 2 = 0 1 + 2 u 1 x 2 + u 2 = 0 ⟹ u 1 < 0 \left\{\begin{array}{l} 2 x_{1}+2 u_{1} x_{1}+u_{2}=0 \\ 1+2 u_{1} x_{2}+u_{2}=0 \end{array} \quad \Longrightarrow u_{1}<0\right. {2x1​+2u1​x1​+u2​=01+2u1​x2​+u2​=0​⟹u1​<0
不满足条件.

3 凸性

假设X是 R n R^n Rn中的凸集。如果 f ( x ) : x → R f(x): x→R f(x):x→R，则f(x)的水平集为集合
S α = { x ∈ X : f ( x ) ≤ α } , ∀ α ∈ R . S_α = \{x ∈ X : f(x) ≤ α\}, ∀α ∈ R. Sα​={x∈X:f(x)≤α},∀α∈R.
函数 f ( x ) f(x) f(x)是一个拟凸 x x x函数，如果对于所有的 x , y ∈ X x, y∈X x,y∈X，并且对于所有的 λ ∈ [ 0 , 1 ] λ ∈[0,1] λ∈[0,1]，有
f ( λ x + ( 1 − λ ) y ) ≤ m a x { f ( x ) , f ( y ) } . f(λx + (1 − λ)y) ≤ max\{f(x), f(y)\}. f(λx+(1−λ)y)≤max{f(x),f(y)}.
函数 f ( x ) f(x) f(x)是一个拟凹 x x x函数，如果对于所有的 x , y ∈ X x, y∈X x,y∈X，并且对于所有的 λ ∈ [ 0 , 1 ] λ ∈[0,1] λ∈[0,1]，有
f ( λ x + ( 1 − λ ) y ) ≥ m i n { f ( x ) , f ( y ) } f(λx + (1 − λ)y) ≥ min\{f(x), f(y)\} f(λx+(1−λ)y)≥min{f(x),f(y)}
如果对于所有的 x , y ∈ X x, y∈X x,y∈X，
∇ f ( x ) T ( y − x ) ≥ 0 ⇒ f ( y ) ≥ f ( x ) . ∇f(x)^T (y − x) ≥ 0 ⇒ f(y) ≥ f(x). ∇f(x)T(y−x)≥0⇒f(y)≥f(x).
则可微函数f(x)是一个伪凸函数.

命 题 \large\color{magenta}{\boxed{\color{brown}{命题} }} 命题​如果 f ( x ) f(x) f(x)是凸的，那么 f ( x ) f(x) f(x)是拟凸的。

【证明】 如果 f ( x ) f(x) f(x)是凸的，对于 λ ∈ [ 0 , 1 ] λ ∈[0,1] λ∈[0,1]，有
f ( λ x + ( 1 − λ ) y ) ≤ λ f ( x ) + ( 1 − λ ) f ( y ) ≤ m a x { f ( x ) , f ( y ) } f(λx + (1 − λ)y) ≤ λf(x)+(1-λ)f(y)≤ max\{f(x), f(y)\} f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)≤max{f(x),f(y)}

定 理 11 \large\color{magenta}{\boxed{\color{brown}{定理11} }} 定理11​函数 f ( x ) f(x) f(x)在 X X X上是拟凸的充分必要条件是，对于每一个 α ∈ R α ∈ R α∈R ， S α S_α Sα​是凸集。

【证明】假如 f ( x ) f(x) f(x) 是拟凸. 对于任意给定的值 α , \alpha, α, 假如 x , y ∈ S α x, y \in S_{\alpha} x,y∈Sα​。

设 z = λ x + ( 1 − λ ) y z=\lambda x+(1-\lambda) y z=λx+(1−λ)y ， λ ∈ [ 0 , 1 ] . \lambda \in[0,1] . λ∈[0,1]. 则 f ( z ) ≤ max ⁡ { f ( x ) , f ( y ) } ≤ α , f(z) \leq \max \{f(x), f(y)\} \leq\alpha, f(z)≤max{f(x),f(y)}≤α,所以 z ∈ S α , z \in S_{\alpha}, z∈Sα​, 说明 S α S_{\alpha} Sα​是凸集。
相反，假设 S α S_{\alpha} Sα​是每个 α . \alpha . α.的凸集 。 令 x x x和 y y y给定，并令 α = max ⁡ { f ( x ) ， f ( y ) } \alpha=\max \{f(x)， f(y)\} α=max{f(x)，f(y)}，因此在 x , y ∈ S α . x, y \in S_{\alpha} . x,y∈Sα​.中对于任意 λ ∈ [ 0 , 1 ] \lambda \in[0,1] λ∈[0,1] ，有 f ( λ x + ( 1 − λ ) y ) ≤ α = max ⁡ { f ( x ) , f ( y ) } , f(\lambda x+(1-\lambda) y) \leq \alpha=\max \{f(x), f(y)\}, f(λx+(1−λ)y)≤α=max{f(x),f(y)}, 因此 f ( x ) f(x) f(x) 是拟凸 。

定 理 12 \large\color{magenta}{\boxed{\color{brown}{定理12} }} 定理12​如果 f ( x ) f(x) f(x)是凸函数，它的水平集是凸集。

假如 X X X 在 ℜ n \Re^{n} ℜn是凸集。 可微的函数 f ( x ) : X → f(x): X \rightarrow f(x):X→ ℜ \Re ℜ 是伪凸函数 ，如果对于每一个 x , y ∈ X x, y \in X x,y∈X 下面成立
∇ f ( x ) t ( y − x ) ≥ 0 ⇒ f ( y ) ≥ f ( x ) \nabla f(x)^{t}(y-x) \geq 0 \Rightarrow f(y) \geq f(x) ∇f(x)t(y−x)≥0⇒f(y)≥f(x)
定 理 13 \large\color{magenta}{\boxed{\color{brown}{定理13} }} 定理13​可微凸函数是伪凸函数，而伪凸函数是拟凸函数。

【证明】为了证明第一个结论，我们使用梯度不等式: 如果 f ( x ) f(x) f(x)凸函数和可微, 则 f ( y ) ≥ f ( x ) + ∇ f ( x ) t ( y − x ) . f(y) \geq f(x)+\nabla f(x)^{t}(y-x) . f(y)≥f(x)+∇f(x)t(y−x). 因此,如果 ∇ f ( x ) t ( y − x ) ≥ 0 , \nabla f(x)^{t}(y-x) \geq 0, ∇f(x)t(y−x)≥0, 则 f ( y ) ≥ f ( x ) , f(y) \geq f(x), f(y)≥f(x), 因此 f ( x ) f(x) f(x) 是伪凸函数.

为了显示第二个结论，假设 f ( x ) f(x) f(x) 伪凸函数. 给定 x , y x, y x,y 和 λ ∈ [ 0 , 1 ] \lambda \in[0,1] λ∈[0,1] , 令 z = λ x + ( 1 − λ ) y . z=\lambda x+(1-\lambda) y . z=λx+(1−λ)y.如果 λ = 0 \lambda=0 λ=0 or λ = 1 , \lambda=1, λ=1, 则 f ( z ) ≤ f(z) \leq f(z)≤ max ⁡ { f ( x ) , f ( y ) } \max \{f(x), f(y)\} max{f(x),f(y)} ; 因此,假设 0 < λ < 1. 0<\lambda<1 . 0<λ<1. 令 d = y − x d=y-x d=y−x。如果 ∇ f ( z ) t d ≥ 0 , \nabla f(z)^{t} d \geq 0, ∇f(z)td≥0, 则
∇ f ( z ) t ( y − z ) = ∇ f ( z ) t ( λ ( y − x ) ) = λ ∇ f ( z ) t d ≥ 0 \nabla f(z)^{t}(y-z)=\nabla f(z)^{t}(\lambda(y-x))=\lambda \nabla f(z)^{t} d \geq 0 ∇f(z)t(y−z)=∇f(z)t(λ(y−x))=λ∇f(z)td≥0
因此 f ( z ) ≤ f ( y ) ≤ max ⁡ { f ( x ) , f ( y ) } f(z) \leq f(y) \leq \max \{f(x), f(y)\} f(z)≤f(y)≤max{f(x),f(y)}。

另一方面，如果 ∇ f ( z ) t d ≤ 0 , \nabla f(z)^{t} d \leq 0, ∇f(z)td≤0, 则
∇ f ( z ) t ( x − z ) = ∇ f ( z ) t ( − ( 1 − λ ) ( y − x ) ) = − ( 1 − λ ) ∇ f ( z ) t d ≥ 0 \nabla f(z)^{t}(x-z)=\nabla f(z)^{t}(-(1-\lambda)(y-x))=-(1-\lambda) \nabla f(z)^{t} d \geq 0 ∇f(z)t(x−z)=∇f(z)t(−(1−λ)(y−x))=−(1−λ)∇f(z)td≥0
因此, f ( z ) ≤ f ( x ) ≤ max ⁡ { f ( x ) , f ( y ) } . f(z) \leq f(x) \leq \max \{f(x), f(y)\} . f(z)≤f(x)≤max{f(x),f(y)}. 因此 f ( x ) f(x) f(x) 拟凸函数。 KaTeX parse error: Undefined control sequence: \bbox at position 1: \̲b̲b̲o̲x̲[cyan,2pt]{ }

顺便说一下，我们定义了一个可微函数 f ( x ) : X → ℜ f(x): X \rightarrow \Re f(x):X→ℜ 是伪凹函数 ，如果对于每一个 x , y ∈ X x, y \in X x,y∈X 下面成立：
∇ f ( x ) t ( y − x ) ≤ 0 ⇒ f ( y ) ≤ f ( x ) \nabla f(x)^{t}(y-x) \leq 0 \Rightarrow f(y) \leq f(x) ∇f(x)t(y−x)≤0⇒f(y)≤f(x)

4 最优性充分条件

定 理 14 \large\color{magenta}{\boxed{\color{brown}{定理14} }} 定理14​**( KKT充分条件)**设 x ˉ \bar{x} xˉ是 ( P ) (P) (P)的可行解， x ˉ \bar{x} xˉ与乘数 u , v u, v u,v一起满足KKT条件：
$$
\begin{aligned}
&\nabla f(\bar{x})+ \nabla g_{}(\bar{x})^T u+\nabla h_{}(\bar{x})^T v=0 \qquad & \
&u ≥ 0 & \
&u_ig_i(\bar{x}) = 0, i = 1, · · · , m. &\

\end{aligned}
$$
如果f(x)是伪凸函数， g i ( x ) ， i = 1 ， ⋅ ⋅ ⋅ ， m g_i(x)， i = 1，···，m gi​(x)，i=1，⋅⋅⋅，m是拟凸函数， h i ( x ) ， i = 1 ， ⋅ ⋅ ⋅ ， l h_i(x)， i = 1，···，l hi​(x)，i=1，⋅⋅⋅，l是线性函数，则 x ˉ \bar{x} xˉ是§的全局最优解.

【证明】因为每个 g i ( x ) g_{i}(x) gi​(x) 是拟凸函数, 水平集
C i : = { x ∈ X : g i ( x ) ≤ 0 } , i = 1 , … , m C_{i}:=\left\{x \in X: g_{i}(x) \leq 0\right\}, i=1, \ldots, m Ci​:={x∈X:gi​(x)≤0},i=1,…,m
是凸集。此外,因为每个 h i ( x ) h_{i}(x) hi​(x) 是线性, 集合
D i = { x ∈ X : h i ( x ) = 0 } , i = 1 , … , l D_{i}=\left\{x \in X: h_{i}(x)=0\right\}, i=1, \ldots, l Di​={x∈X:hi​(x)=0},i=1,…,l
是凸集. 因此，由于凸集的交也是一个凸集，故可行域
S = { x ∈ X : g ( x ) ≤ 0 , h ( x ) = 0 } S=\{x \in X: g(x) \leq 0, h(x)=0\} S={x∈X:g(x)≤0,h(x)=0}
是凸集。
令 I = { i ∣ g i ( x ˉ ) = 0 } I=\left\{i \mid g_{i}(\bar{x})=0\right\} I={i∣gi​(xˉ)=0} 表示活动约束的索引在 x ˉ \bar{x} xˉ.令 x ∈ S x \in S x∈S是任何点不同于 x ˉ . \bar{x} . xˉ. 则 λ x + ( 1 − λ ) x ˉ \lambda x+(1-\lambda) \bar{x} λx+(1−λ)xˉ 是可行的对于所有 λ ∈ ( 0 , 1 ) . \lambda \in(0,1) . λ∈(0,1). 因此对于 i ∈ I i \in I i∈I 有
g i ( λ x + ( 1 − λ ) x ˉ ) = g i ( x ˉ + λ ( x − x ˉ ) ) ≤ 0 = g i ( x ˉ ) g_{i}(\lambda x+(1-\lambda) \bar{x})=g_{i}(\bar{x}+\lambda(x-\bar{x})) \leq 0=g_{i}(\bar{x}) gi​(λx+(1−λ)xˉ)=gi​(xˉ+λ(x−xˉ))≤0=gi​(xˉ)
对于任何的 λ ∈ ( 0 , 1 ) , \lambda \in(0,1), λ∈(0,1), 由于 g i ( ⋅ ) g_{i}(\cdot) gi​(⋅)的值不会随着 x − x ˉ x-\bar{x} x−xˉ方向的移动而增加，所以对于 i ∈ I i \in I i∈I ，我们必须有 ∇ g i ( x ˉ ) t ( x − x ˉ ) ≤ 0 \nabla g_{i}(\bar{x})^{t}(x-\bar{x}) \leq 0 ∇gi​(xˉ)t(x−xˉ)≤0。

类似地, ∇ h i ( x ˉ + λ ( x − x ˉ ) ) = 0 , \nabla h_{i}(\bar{x}+\lambda(x-\bar{x}))=0, ∇hi​(xˉ+λ(x−xˉ))=0, 所以 ∇ h i ( x ˉ ) t ( x − x ˉ ) = 0 \nabla h_{i}(\bar{x})^{t}(x-\bar{x})=0 ∇hi​(xˉ)t(x−xˉ)=0 对于 i = 1 , … , l i=1, \ldots, l i=1,…,l

因此，KKT条件：
∇ f ( x ˉ ) t ( x − x ˉ ) = − ( ∇ g ( x ˉ ) t u + ∇ h ( x ˉ ) t v ) t ( x − x ˉ ) ≥ 0 \nabla f(\bar{x})^{t}(x-\bar{x})=-\left(\nabla g(\bar{x})^{t} u+\nabla h(\bar{x})^{t} v\right)^{t}(x-\bar{x}) \geq 0 ∇f(xˉ)t(x−xˉ)=−(∇g(xˉ)tu+∇h(xˉ)tv)t(x−xˉ)≥0
通过伪凸性， f ( x ) ≥ f ( x ˉ ) f(x) \geq f(\bar{x}) f(x)≥f(xˉ)对于任意可行 x x x。KaTeX parse error: Undefined control sequence: \bbox at position 1: \̲b̲b̲o̲x̲[cyan,2pt]{ }

对于约束优化问题:
KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ (P) ~ ~ ~ …
如果 f ( x ) 、 g ( x ) f(x)、g(x) f(x)、g(x)是凸函数， h ( x ) h(x) h(x)是线性函数，且 X X X是一个开凸集，则一般问题§称为凸规划。

定 理 15 \large\color{magenta}{\boxed{\color{brown}{定理15} }} 定理15​ KKT条件是求解凸规划最优性的充分条件。

例5

求下列问题的全局最小值:
min ⁡ f ( x ) = ( x 1 − 2 ) 2 + ( x 2 − 1 ) 2  s.t.  g 1 ( x ) = x 1 2 − x 2 ≤ 0 g 2 ( x ) = x 1 + x 2 − 2 ≤ 0 \begin{array}{ll} \min & f(x)=\left(x_{1}-2\right)^{2}+\left(x_{2}-1\right)^{2} \\ \text { s.t. } & g_{1}(x)=x_{1}^{2}-x_{2} \leq 0 \\ & g_{2}(x)=x_{1}+x_{2}-2 \leq 0 \end{array} min s.t. ​f(x)=(x1​−2)2+(x2​−1)2g1​(x)=x12​−x2​≤0g2​(x)=x1​+x2​−2≤0​
解决方案:

我们有
∇ f ( x ) = ( 2 x 1 − 4 2 x 2 − 2 ) , ∇ g 1 ( x ) = ( 2 x 1 − 1 ) , ∇ g 2 ( x ) = ( 1 1 ) \nabla f(x)=\left(\begin{array}{c} 2 x_{1}-4 \\ 2 x_{2}-2 \end{array}\right), \nabla g_{1}(x)=\left(\begin{array}{c} 2 x_{1} \\ -1 \end{array}\right), \nabla g_{2}(x)=\left(\begin{array}{c} 1 \\ 1 \end{array}\right) ∇f(x)=(2x1​−42x2​−2​),∇g1​(x)=(2x1​−1​),∇g2​(x)=(11​)
以下KKT条件成立:
∇ f ( x ) + ∑ i = 1 2 u i ∇ g i ( x ) = 0 u i g i ( x ) = 0 , i = 1 , 2 u i ≥ 0 , i = 1 , 2 g i ( x ) ≤ 0 , i = 1 , 2 \begin{array}{l} \nabla f(x)+\sum_{i=1}^{2} u_{i} \nabla g_{i}(x)=0 \\ u_{i} g_{i}(x)=0, i=1,2 \\ u_{i} \geq 0, i=1,2 \\ g_{i}(x) \leq 0, i=1,2 \end{array} ∇f(x)+∑i=12​ui​∇gi​(x)=0ui​gi​(x)=0,i=1,2ui​≥0,i=1,2gi​(x)≤0,i=1,2​
即
{ 2 ( x 1 − 2 ) + 2 u 1 x 1 + u 2 = 0 2 ( x 2 − 1 ) − u 1 + u 2 = 0 u 1 ( x 1 2 − x 2 ) = 0 u 2 ( x 1 + x 2 − 2 ) = 0 u 1 ≥ 0 , u 2 ≥ 0 x 1 2 − x 2 ≤ 0 x 1 + x 2 − 2 ≤ 0 \left\{\begin{array}{l} 2\left(x_{1}-2\right)+2 u_{1} x_{1}+u_{2}=0 \\ 2\left(x_{2}-1\right)-u_{1}+u_{2}=0 \\ u_{1}\left(x_{1}^{2}-x_{2}\right)=0 \\ u_{2}\left(x_{1}+x_{2}-2\right)=0 \\ u_{1} \geq 0, u_{2} \geq 0 \\ x_{1}^{2}-x_{2} \leq 0 \\ x_{1}+x_{2}-2 \leq 0 \end{array}\right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​2(x1​−2)+2u1​x1​+u2​=02(x2​−1)−u1​+u2​=0u1​(x12​−x2​)=0u2​(x1​+x2​−2)=0u1​≥0,u2​≥0x12​−x2​≤0x1​+x2​−2≤0​

考虑以下情况:
(1) 如果 u 1 = u 2 = 0 ⟹ x 1 = 2 , x 2 = 1 , u_{1}=u_{2}=0 \Longrightarrow x_{1}=2, x_{2}=1, u1​=u2​=0⟹x1​=2,x2​=1, 不符合可行性，放弃。
(2) 如果 u 1 = 0 , u 2 > 0 , u_{1}=0, u_{2}>0, u1​=0,u2​>0, 然后我们有
{ x 1 − x 2 − 1 = 0 x 1 + x 2 − 2 = 0 ⟹ { x 1 = 3 2 x 2 = 1 2 \left\{\begin{array}{l} x_{1}-x_{2}-1=0 \\ x_{1}+x_{2}-2=0 \end{array} \Longrightarrow\left\{\begin{array}{l} x_{1}=\frac{3}{2} \\ x_{2}=\frac{1}{2} \end{array}\right.\right. {x1​−x2​−1=0x1​+x2​−2=0​⟹{x1​=23​x2​=21​​
它不符合可行性，放弃。

(3)如果 u 1 > 0 , u 2 = 0 , u_{1}>0, u_{2}=0, u1​>0,u2​=0,则
{ x 1 2 − x 2 = 0 2 ( x 1 − 2 ) + 2 u 1 x 1 = 0 2 ( x 2 − 1 ) − u 1 = 0 \left\{\begin{array}{l} x_{1}^{2}-x_{2}=0 \\ 2\left(x_{1}-2\right)+2 u_{1} x_{1}=0 \\ 2\left(x_{2}-1\right)-u_{1}=0 \end{array}\right. ⎩⎨⎧​x12​−x2​=02(x1​−2)+2u1​x1​=02(x2​−1)−u1​=0​
放弃。

(4) 如果 u 1 > 0 , u 2 > 0 , u_{1}>0, u_{2}>0, u1​>0,u2​>0, 则
{ 2 ( x 1 − 2 ) + 2 u 1 x 1 + u 2 = 0 2 ( x 2 − 1 ) − u 1 + u 2 = 0 x 1 2 − x 2 = 0 x 1 + x 2 − 2 = 0 ⟹ { x 1 = 1 x 2 = 1 u 1 = 2 3 u 2 = 2 3 \left\{\begin{array}{l} 2\left(x_{1}-2\right)+2 u_{1} x_{1}+u_{2}=0 \\ 2\left(x_{2}-1\right)-u_{1}+u_{2}=0 \\ x_{1}^{2}-x_{2}=0 \\ x_{1}+x_{2}-2=0 \end{array} \quad \Longrightarrow\left\{\begin{array}{l} x_{1}=1 \\ x_{2}=1 \\ u_{1}=\frac{2}{3} \\ u_{2}=\frac{2}{3} \end{array}\right.\right. ⎩⎪⎪⎨⎪⎪⎧​2(x1​−2)+2u1​x1​+u2​=02(x2​−1)−u1​+u2​=0x12​−x2​=0x1​+x2​−2=0​⟹⎩⎪⎪⎨⎪⎪⎧​x1​=1x2​=1u1​=32​u2​=32​​
因此,我们得到
x ˉ = ( 1 1 ) , u = ( u 1 u 2 ) = ( 2 3 2 3 ) \bar{x}=\left(\begin{array}{l} 1 \\ 1 \end{array}\right), u=\left(\begin{array}{l} u_{1} \\ u_{2} \end{array}\right)=\left(\begin{array}{l} \frac{2}{3} \\ \frac{2}{3} \end{array}\right) xˉ=(11​),u=(u1​u2​​)=(32​32​​)
因为问题是一个凸规划，所以 x ˉ \bar{x} xˉ是一个全局最小值。

5 约束规范

回忆一下，这里所建立的KKT必要条件的表述是这样的:“ 如果 x ˉ \bar{x} xˉ是§的局部最小值并且约束条件的某些要求成立，那么KKT条件必须在 x ˉ \bar{x} xˉ处成立。 ”对使我们能够继续证明KKT条件的约束条件的附加要求被称为约束限定。

线性独立约束条件: ∇ h i ( x ˉ ) , i = , 1 , ⋅ ⋅ ⋅ , l \nabla h_{i}(\bar{x}),i = ,1, · · · , l ∇hi​(xˉ),i=,1,⋅⋅⋅,l,和 ∇ g i ( x ˉ ) , i ∈ I ( x ˉ ) \nabla g_{i}(\bar{x}),i ∈ I(\bar{x}) ∇gi​(xˉ),i∈I(xˉ)是线性无关的。

定 义 \large\color{magenta}{\boxed{\color{brown}{定义} }} 定义​点 x x x称为满足 g ( x ) < 0 且 h ( x ) = 0 g(x) < 0且h(x) = 0 g(x)<0且h(x)=0的Slater点，即 x 是 x是 x是可行的，严格满足所有不等式。

定 理 16 \large\color{magenta}{\boxed{\color{brown}{定理16} }} 定理16​ **(Slater 条件)**假设 g i ( x ) ， i = 1 ， ⋅ ⋅ ⋅ ， m g_i(x)， i = 1，···，m gi​(x)，i=1，⋅⋅⋅，m是伪凸的， h i ( x ) ， i = 1 ， ⋅ ⋅ ⋅ ， l h_i(x)， i = 1，···，l hi​(x)，i=1，⋅⋅⋅，l是线性的，而 ∇ h i ( x ) ， i = 1 ， ⋅ ⋅ ⋅ ， l ∇h_i(x)， i = 1，···，l ∇hi​(x)，i=1，⋅⋅⋅，l是线性无关的，且​§有一个Slater点。然后KKT条件是刻画最优解的必要条件。

定 理 17 \large\color{magenta}{\boxed{\color{brown}{定理17} }} 定理17​如果所有的约束都是线性的，那么KKT条件就必须用来描述一个最优解。

6 二阶最优性条件

对于问题§，定义拉格朗日函数:
L ( x , λ , μ ) = f ( x ) + ∑ j = 1 m λ j g j ( x ) + ∑ k = 1 l μ k h k ( x ) \displaystyle L\left(\mathbf{x},{\lambda},{\mu}\right)=f(\mathbf{x})+\sum_{j=1}^m\lambda_jg_j( \mathbf{x})+\sum_{k=1}^l\mu_kh_k(\mathbf{x})\\ L(x,λ,μ)=f(x)+j=1∑m​λj​gj​(x)+k=1∑l​μk​hk​(x)
等价于
L ( x , λ , μ ) = f ( x ) + λ T g ( x ) + μ T h ( x ) \displaystyle L\left(\mathbf{x},{\lambda},{\mu}\right)=f(\mathbf{x})+\lambda ^Tg( \mathbf{x})+\mu^T h(\mathbf{x})\\ L(x,λ,μ)=f(x)+λTg(x)+μTh(x)
则
∇ x L ( x , λ , μ ) = ∇ f ( x ) + ∇ g ( x ) T λ + ∇ h ( x ) T μ ∇ x x 2 L ( x , λ , μ ) = ∇ 2 f ( x ) + ∑ j = 1 m λ j ∇ 2 g j ( x ) + ∑ k = 1 l μ k ∇ 2 h k ( x ) \nabla_x\displaystyle L\left(\mathbf{x},{\lambda},{\mu}\right)=\nabla f(\mathbf{x})+ \nabla g_{}({x})^T \lambda +\nabla h_{}({x})^T \mu\\ \nabla_{xx}^2\displaystyle L\left(\mathbf{x},{\lambda},{\mu}\right)=\nabla^2 f(\mathbf{x})+\sum_{j=1}^m\lambda_j\nabla^2g_j( \mathbf{x})+\sum_{k=1}^l\mu_k\nabla^2h_k(\mathbf{x})\\ ∇x​L(x,λ,μ)=∇f(x)+∇g​(x)Tλ+∇h​(x)Tμ∇xx2​L(x,λ,μ)=∇2f(x)+j=1∑m​λj​∇2gj​(x)+k=1∑l​μk​∇2hk​(x)
定 理 18 \large\color{magenta}{\boxed{\color{brown}{定理18} }} 定理18​**(KKT二阶必要条件)假设 x ˉ \bar{x} xˉ是 ( P ) (P) (P)的局部最小值，而 ∇ h i ( x ˉ ) , i = , 1 , ⋅ ⋅ ⋅ , l \nabla h_{i}(\bar{x}),i = ,1, · · · , l ∇hi​(xˉ),i=,1,⋅⋅⋅,l,和 ∇ g i ( x ˉ ) , i ∈ I ( x ˉ ) \nabla g_{i}(\bar{x}),i ∈ I(\bar{x}) ∇gi​(xˉ),i∈I(xˉ)是线性无关的。那么 x ˉ \bar{x} xˉ必须满足KKT条件。进一步，每一个d满足:
∇ g i ( x ˉ ) T d ≤ 0 , i ∈ I ( x ˉ ) , ∇ h i ( x ) T d = 0 , i = 1 , ⋅ ⋅ ⋅ , l \nabla g_{i}(\bar{x})^T d ≤ 0, i ∈ I(\bar{x}), \\∇h_i(x)^T d = 0, i = 1, · · · , l ∇gi​(xˉ)Td≤0,i∈I(xˉ),∇hi​(x)Td=0,i=1,⋅⋅⋅,l
d ∈ Y 1 d\in Y_1 d∈Y1​还必须满足
d T ∇ x x L ( x , λ , μ ) d ≥ 0 d^T ∇_{xx}L\left(\mathbf{x},{\lambda},{\mu}\right)d ≥ 0 dT∇xx​L(x,λ,μ)d≥0
定 理 19 \large\color{magenta}{\boxed{\color{brown}{定理19} }} 定理19​(KKT二阶充分条件)**假设 x ˉ ∈ S \bar{x}∈S xˉ∈S与乘数 ( u , v ) (u, v) (u,v)一起满足KKT条件。让 I + = { i ∈ I : λ i > 0 } I^+ = \{i∈I: \lambda_i > 0\} I+={i∈I:λi​>0}和 I 0 = { i ∈ I : λ i = 0 } I^0 = \{i∈I: \lambda_i = 0\} I0={i∈I:λi​=0}。另外，假设每一个 d ≠ 0 d\neq 0 d​=0满足:
$$
\nabla g_{i}(\bar{x})^T d = 0, i ∈ I^+, \
\nabla g_{i}(\bar{x})^T d ≤ 0, i ∈ I^0,

\∇h_i(\bar{x})^T d = 0, i = 1, · · · , l
KaTeX parse error: Can't use function '$' in math mode at position 2: $̲d\in Y_2$还必须满足
d^T ∇_{xx}L\left(\mathbf{x},{\lambda},{\mu}\right)d ≥ 0
$$
那么 x ˉ \bar{x} xˉ是§的严格局部极小值。

例6

考虑以下问题:
min ⁡ f ( x ) = x 1  s.t.  g ( x ) = 3 ( x 1 − 3 ) 2 + x 2 ≥ 0 h ( x ) = ( x 1 − 3 ) 2 + x 2 2 − 10 = 0 \begin{array}{ll} \min & f(x)=x_{1} \\ \text { s.t. } & g(x)=3\left(x_{1}-3\right)^{2}+x_{2} \geq 0 \\ & h(x)=(x_1-3)^{2}+x_{2}^{2}-10=0 \end{array} min s.t. ​f(x)=x1​g(x)=3(x1​−3)2+x2​≥0h(x)=(x1​−3)2+x22​−10=0​
确定是否
x 1 = ( 2 − 3 ) , x 2 = ( 4 − 3 ) x^{1}=\left(\begin{array}{c} 2 \\ -3 \end{array}\right), \quad x^{2}=\left(\begin{array}{c} 4 \\ -3 \end{array}\right) x1=(2−3​),x2=(4−3​)
x 3 = ( 3 + 10 0 ) , x 4 = ( 3 − 10 0 ) x^{3}=\left(\begin{array}{c} 3+\sqrt{10} \\ 0 \end{array}\right), \quad x^{4}=\left(\begin{array}{c} 3-\sqrt{10} \\ 0 \end{array}\right) x3=(3+10 ​0​),x4=(3−10 ​0​)
是最优解。

解:
∇ f ( x ) = ( 1 0 ) , ∇ g ( x ) = ( 6 ( x 1 − 3 ) 1 ) , ∇ h ( x ) = ( 2 ( x 1 − 3 ) 2 x 2 ) \nabla f(x)=\left(\begin{array}{c} 1 \\ 0 \end{array}\right), \nabla g(x)=\left(\begin{array}{c} 6\left(x_{1}-3\right) \\ 1 \end{array}\right), \nabla h(x)=\left(\begin{array}{c} 2\left(x_{1}-3\right) \\ 2 x_{2} \end{array}\right) ∇f(x)=(10​),∇g(x)=(6(x1​−3)1​),∇h(x)=(2(x1​−3)2x2​​)
拉格朗日函数及其梯度和Hessian函数的表达式如下:
L ( x , u , v ) = x 1 − u ( 3 ( x 1 − 3 ) 2 + x 2 ) + v ( ( x 1 − 3 ) 2 + x 2 2 − 10 ) ∇ x L ( x , u , v ) = ( 1 − 6 u ( x 1 − 3 ) + 2 v ( x 1 − 3 ) − u + 2 v x 2 ) ∇ x x 2 L ( x , u , v ) = ( − 6 u + 2 v 0 0 2 v ) \begin{array}{l} L(x, u, v)=x_{1}-u\left(3\left(x_{1}-3\right)^{2}+x_{2}\right)+v\left(\left(x_{1}-3\right)^{2}+x_{2}^{2}-10\right) \\ \nabla_{x} L(x, u, v)=\left(\begin{array}{c} 1-6 u\left(x_{1}-3\right)+2 v\left(x_{1}-3\right) \\ -u+2 v x_{2} \end{array}\right) \\ \nabla_{x x}^{2} L(x, u, v)=\left(\begin{array}{cc} -6 u+2 v & 0 \\ 0 & 2 v \end{array}\right) \end{array} L(x,u,v)=x1​−u(3(x1​−3)2+x2​)+v((x1​−3)2+x22​−10)∇x​L(x,u,v)=(1−6u(x1​−3)+2v(x1​−3)−u+2vx2​​)∇xx2​L(x,u,v)=(−6u+2v0​02v​)​
考虑以下情况:
(1) x 1 x^{1} x1.

g ( x 1 ) = 0 , h ( x 1 ) = 0 , g\left(x^{1}\right)=0, h\left(x^{1}\right)=0, g(x1)=0,h(x1)=0, 成立 . KKT 条件：
( 1 0 ) − u ( − 6 1 ) + v ( − 2 − 6 ) = ( 0 0 ) ⟹ { u = − 3 19 < 0 v = 1 38 \left(\begin{array}{c}1 \\ 0\end{array}\right)-u\left(\begin{array}{c}-6 \\ 1\end{array}\right)+v\left(\begin{array}{c}-2 \\ -6\end{array}\right)=\left(\begin{array}{c}0 \\ 0\end{array}\right) \Longrightarrow\left\{\begin{array}{l}u=-\frac{3}{19}<0 \\ v=\frac{1}{38}\end{array}\right. (10​)−u(−61​)+v(−2−6​)=(00​)⟹{u=−193​<0v=381​​
不满足条件.

(2) x 2 x^{2} x2.

g ( x 2 ) = 0 , h ( x 2 ) = 0 , g\left(x^{2}\right)=0, h\left(x^{2}\right)=0, g(x2)=0,h(x2)=0, 成立 . KKT 条件：
( 1 0 ) − u ( 6 1 ) + v ( 2 − 6 ) = ( 0 0 ) ⟹ { u = 3 19 > 0 v = − 1 38 \left(\begin{array}{l} 1 \\ 0 \end{array}\right)-u\left(\begin{array}{l} 6 \\ 1 \end{array}\right)+v\left(\begin{array}{c} 2 \\ -6 \end{array}\right)=\left(\begin{array}{l} 0 \\ 0 \end{array}\right) \Longrightarrow\left\{\begin{array}{l} u=\frac{3}{19}>0 \\ v=-\frac{1}{38} \end{array}\right. (10​)−u(61​)+v(2−6​)=(00​)⟹{u=193​>0v=−381​​
x 2 x_{2} x2​ 是KKT点，而
∇ x x 2 L ( x 2 , u , v ) = ( − 1 0 0 − 1 19 ) Y 2 = { d ≠ 0 ∣ ∇ g ( x 2 ) T d = 0 , u > 0 ; ∇ h ( x 2 ) T d = 0 } = { d ≠ 0 ∣ 6 d 1 + d 2 = 0 ; 2 d 1 − 6 d 2 = 0 } = ∅ \begin{array}{l} \nabla_{x x}^{2} L\left(x^{2}, u, v\right)=\left(\begin{array}{cc} -1 & 0 \\ 0 & -\frac{1}{19} \end{array}\right) \\ Y_{2}=\left\{d \neq 0 \mid \nabla g\left(x^{2}\right)^{T} d=0, u>0 ; \nabla h\left(x^{2}\right)^{T} d=0\right\} \\ \quad=\left\{d \neq 0 \mid 6 d_{1}+d_{2}=0 ; 2 d_{1}-6 d_{2}=0\right\}=\emptyset \end{array} ∇xx2​L(x2,u,v)=(−10​0−191​​)Y2​={d​=0∣∇g(x2)Td=0,u>0;∇h(x2)Td=0}={d​=0∣6d1​+d2​=0;2d1​−6d2​=0}=∅​
因此, ∇ x x 2 L ( x 2 , u , v ) ≻ 0 \nabla_{x x}^{2} L\left(x^{2}, u, v\right) \succ 0 ∇xx2​L(x2,u,v)≻0 在 Y 2 , Y_{2}, Y2​, 则 x 2 x^{2} x2 是一个严格局部最优解。

(3) x 3 x^{3} x3.

g ( x 3 ) > 0 , h ( x 3 ) = 0 , g\left(x^{3}\right)>0, h\left(x^{3}\right)=0, g(x3)>0,h(x3)=0, 成立 . 所以 u = 0 u=0 u=0,KKT 条件：
( 1 0 ) + v ( 2 10 0 ) = ( 0 0 ) ⟹ v = − 1 2 10 \left(\begin{array}{l} 1 \\ 0 \end{array}\right)+v\left(\begin{array}{c} 2 \sqrt{10} \\ 0 \end{array}\right)=\left(\begin{array}{l} 0 \\ 0 \end{array}\right) \Longrightarrow v=-\frac{1}{2 \sqrt{10}} (10​)+v(210 ​0​)=(00​)⟹v=−210 ​1​
x 3 x_{3} x3​ 是KKT点，而
∇ x x 2 L ( x 3 , u , v ) = ( − 1 10 0 0 − 1 10 ) Y 1 = { d ∣ ∇ h ( x 3 ) T d = 0 } = { d ∣ 2 10 d 1 + 0 ⋅ d 2 = 0 } = { d ∣ d = ( 0 , d 2 ) T } \begin{aligned} \nabla_{x x}^{2} L &\left(x^{3}, u, v\right)=\left(\begin{array}{cc} -\frac{1}{\sqrt{10}} & 0 \\ 0 & -\frac{1}{\sqrt{10}} \end{array}\right) \\ Y_{1} &=\left\{d \mid \nabla h\left(x^{3}\right)^{T} d=0\right\} \\ &=\left\{d \mid 2 \sqrt{10} d_{1}+0 \cdot d_{2}=0\right\} \\ &=\left\{d \mid d=\left(0, d_{2}\right)^{T}\right\} \end{aligned} ∇xx2​LY1​​(x3,u,v)=(−10 ​1​0​0−10 ​1​​)={d∣∇h(x3)Td=0}={d∣210 ​d1​+0⋅d2​=0}={d∣d=(0,d2​)T}​
因此 , d ≠ 0 , d T ∇ x x 2 L ( x 3 , u , v ) d = − d 2 2 10 < 0 \mathrm{}, d \neq 0, d^{T} \nabla_{x x}^{2} L\left(x^{3}, u, v\right) d=-\frac{d_{2}^{2}}{\sqrt{10}}<0 ,d​=0,dT∇xx2​L(x3,u,v)d=−10 ​d22​​<0 在 Y 1 , Y_{1}, Y1​, 则 x 3 x^{3} x3 不是一个局部最优。

(4) x 4 x^{4} x4.

g ( x 4 ) > 0 , h ( x 4 ) = 0 , g\left(x^{4}\right)>0, h\left(x^{4}\right)=0, g(x4)>0,h(x4)=0, 成立 .

KKT 条件：
( 1 0 ) + v ( − 2 10 0 ) = ( 0 0 ) ⟹ v = 1 2 10 \left(\begin{array}{c} 1 \\ 0 \end{array}\right)+v\left(\begin{array}{c} -2 \sqrt{10} \\ 0 \end{array}\right)=\left(\begin{array}{l} 0 \\ 0 \end{array}\right) \Longrightarrow v=\frac{1}{2 \sqrt{10}} (10​)+v(−210 ​0​)=(00​)⟹v=210 ​1​
x 4 x_{4} x4​ 是KKT点，而
∇ x x 2 L ( x 4 , u , v ) = ( 1 10 0 0 1 10 ) Y 2 = { d ≠ 0 ∣ ∇ g ( x 4 ) T d ≥ 0 , u = 0 ; ∇ h ( x 4 ) T d = 0 } = { d ≠ 0 ∣ − 6 10 d 1 + d 2 ≥ 0 ; − 2 10 d 1 + 0 ⋅ d 2 = 0 } = { d ≠ 0 ∣ d = ( 0 , d 2 ≥ 0 ) T } \begin{aligned} &\nabla_{x x}^{2} L\left(x^{4}, u, v\right)=\left(\begin{array}{cc} \frac{1}{\sqrt{10}} & 0 \\ 0 & \frac{1}{\sqrt{10}} \end{array}\right) \\ Y_{2} &=\left\{d \neq 0 \mid \nabla g\left(x^{4}\right)^{T} d \geq 0, u=0 ; \nabla h\left(x^{4}\right)^{T} d=0\right\} \\ &=\left\{d \neq 0 \mid-6 \sqrt{10} d_{1}+d_{2} \geq 0 ;-2 \sqrt{10} d_{1}+0 \cdot d_{2}=0\right\} \\ &=\left\{d \neq 0 \mid d=\left(0, d_{2} \geq 0\right)^{T}\right\} \end{aligned} Y2​​∇xx2​L(x4,u,v)=(10 ​1​0​010 ​1​​)={d​=0∣∇g(x4)Td≥0,u=0;∇h(x4)Td=0}={d​=0∣−610 ​d1​+d2​≥0;−210 ​d1​+0⋅d2​=0}={d​=0∣d=(0,d2​≥0)T}​
因此, d T ∇ x x 2 L ( x 4 , u , v ) d = d 2 2 10 > 0 d^{T} \nabla_{x x}^{2} L\left(x^{4}, u, v\right) d=\frac{d_{2}^{2}}{\sqrt{10}}>0 dT∇xx2​L(x4,u,v)d=10 ​d22​​>0 在 Y 1 , Y_{1}, Y1​, 则 x 4 x^{4} x4 是一个严格局部最优解。

参考资料

MIT 最优化课程

PRML | 《机器学习方法》-李航 |《机器学习》-周志华

http://blog.csdn.net/xianlingmao/article/details/7919597

http://blog.csdn.net/timingspace/article/details/50966105

http://blog.csdn.net/loadstar_kun/article/details/25369017

http://blog.csdn.net/johnnyconstantine/article/details/46335763

http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf

http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/Duality.pdf

http://www.cnblogs.com/jerrylead/archive/2011/03/13/1982684.html