031-理论-一阶最优性条件

知识点概述

对于约束优化问题，一阶最优性条件（也称为Karush-Kuhn-Tucker或KKT条件）是判断一个点是否为局部解的必要条件。它描述了在解点处，目标函数的梯度与所有积极约束（active constraints）的梯度之间的关系。具体来说，目标函数的梯度必须可以表示为积极约束梯度的线性组合，其中不等式约束的系数（拉格朗日乘子）必须为非负。这个条件是约束优化理论和算法设计的基石。

教材原文

Theorem 12.1 (First-Order Necessary Conditions). Suppose that $x^{\ast }$ is a local solution of (12.1), that the functions $f$ and $c_i$ … are continuously differentiable, and that the LICQ holds at $x^{\ast }$. Then there is a Lagrange multiplier vector ${\lambda }^{\ast }$, with components ${\lambda }_i^{\ast },i\in \mathcal{E}\cup \mathcal{I}$, such that the following conditions are satisfied at $(x^{\ast },{\lambda }^{\ast })$: \nabla_x \mathcal{L}(x^*, \lambda^*) = 0, \tag{12.34a} c_i(x^*) = 0, \quad \text{for all } i \in \mathcal{E}, \tag{12.34b} c_i(x^*) \geq 0, \quad \text{for all } i \in \mathcal{I}, \tag{12.34c} \\lambda_i^* \geq 0, \quad \text{for all } i \in \mathcal{I}, \tag{12.34d} \\lambda_i^* c_i(x^*) = 0, \quad \text{for all } i \in \mathcal{E} \cup \mathcal{I}. \tag{12.34e}

详细解释

KKT条件是一个包含多个部分的综合性条件，适用于一般形式的非线性规划问题 $\min f(x)$ s.t. $c_i(x)=0(i\in \mathcal{E}),c_i(x)\ge 0(i\in \mathcal{I})$。

1. 拉格朗日函数 (Lagrangian)

   • KKT条件是基于拉格朗日函数定义的： $mathcalL(x,\lambda )=f(x)-{\sum }_{i\in \mathcal{E}\cup \mathcal{I}}{\lambda }_i{c}_i(x)$
   • 向量$lambda$被称为拉格朗日乘子 (Lagrange Multipliers)。

2. KKT 条件详解

   • (12.34a) 驻点条件 (Stationarity): ${\nabla }_x\mathcal{L}(x^{\ast },{\lambda }^{\ast })=\nabla f(x^{\ast })-{\sum }_{i\in \mathcal{A}(x^{\ast })}{\lambda }_i^{\ast }\nabla c_i(x^{\ast })=0$。
     • 几何意义: 在解点$x^{\ast }$，目标函数的梯度$nablaf(x^{\ast })$位于所有积极约束梯度所张成的锥（cone）中。对于只有等式约束的情况，这意味着$nablaf(x^{\ast })$是积极约束梯度的线性组合。
   • (12.34b, 12.34c) 原始可行性 (Primal Feasibility): 解$x^{\ast }$必须满足所有的等式和不等式约束。
   • (12.34d) 对偶可行性 (Dual Feasibility): 所有对应于不等式约束的拉格朗日乘子$lambd{a}_i^{\ast }$必须为非负。
     • 直观解释: $lambd{a}_i^{\ast }$衡量了约束$c_i$对解的“压力”。如果$lambd{a}_i^{\ast }>0$，放松该约束（即将$c_i(x)\ge 0$变为$c_i(x)\ge -ϵ$）将会导致目标函数值下降。因此，对于一个最小化问题，目标函数梯度$nablaf$必须“推向”可行域的内部，这意味着$nablaf$和指向可行域外部的$$\begin{gathered} - \\ nabla{c}_i \end{gathered}$$之间必须有某种对立关系，从而要求$lambd{a}_i^{\ast }\ge 0$。
   • (12.34e) 互补松弛条件 (Complementarity): $lambd{a}_i^{\ast }{c}_i(x^{\ast })=0$。
     • 意义: 这个条件非常关键。它表明，对于任何一个不等式约束$i\in \mathcal{I}$，如果它在解点$x^{\ast }$处是不积极的 (inactive)，即$c_i(x^{\ast })>0$，那么它对应的拉格朗日乘子$lambd{a}_i^{\ast }$必须为零。反之，如果一个不等式约束的乘子$lambd{a}_i^{\ast }$是严格正的，那么该约束在解点必须是积极的 (active)，即$c_i(x^{\ast })=0$。
     • 严格互补性 (Strict Complementarity): 如果对于所有积极不等式约束，其对应的乘子都严格为正，则称严格互补性成立。这是一个在算法分析中很有用的性质。

3. 约束规范 (Constraint Qualification, CQ)

   • KKT条件成立的前提是，在解点$x^{\ast }$处必须满足某个约束规范。CQ是保证可行域在$x^{\ast }$附近的几何性质能够被其线性化近似（即一阶可行方向锥 $\mathcal{F}(x^{\ast })$）所捕捉的条件。
   • 最常用也最容易验证的CQ是线性无关约束规范 (LICQ)，即要求所有积极约束的梯度向量在$x^{\ast }$处是线性无关的。如果LICQ成立，那么KKT条件中的拉格朗日乘子$lambd{a}^{\ast }$是唯一的。

学习要点

• KKT是核心: KKT条件是判断一个点是否为约束优化问题解的一阶必要条件。
• 几何图像: 想象在解点，目标函数的负梯度方向 $$\begin{gathered} - \\ nablaf \end{gathered}$$ 不能指向可行域的内部。它被积极约束的梯度“挡住”了。
• 乘子的符号: 记住不等式约束的乘子必须为非负（对于标准形式 $c_i(x)\ge 0$）。
• 互补松弛: 深刻理解“要么约束有效，要么乘子为零”的互补关系，这是区分积极与非积极约束的关键。
• 约束规范: 了解KKT条件的成立需要一个前提条件，即约束规范（如LICQ）。

实践应用

• 算法设计: 几乎所有的现代非线性规划算法，如SQP和内点法，其核心都是为了寻找满足KKT条件的点。
• 解的检验: 在得到一个候选解后，可以通过检查KKT条件是否（近似）满足来验证其是否可能是一个局部最优解。
• 敏感性分析: 拉格朗日乘子$lambd{a}_i^{\ast }$的值表示了当约束$c_i$的右端项发生微小扰动时，最优目标函数值的变化率，具有重要的经济学和工程学意义。

关联知识点

• 前置知识: 004-理论-最优性条件, 033-概念-约束规范
• 后续知识: 032-理论-二阶最优性条件, 034-理论-对偶性, 046-方法-局部SQP方法