非线性规划 - Ciallo Wiki

1 非线性规划的基本概念

1.1 问题定义与标准形式

非线性规划指在决策变量取实数或向量的情况下，目标函数与约束函数通常均为非线性形式的优化问题。其典型写法可分为无约束与带约束两类。带约束情形常用“等式约束 + 不等式约束”的组合来刻画，例如把决策变量记为 \(x\in\mathbb{R}^n\)，将目标表示为 \(f(x)\)，等式约束表示为 \(h(x)=0\)，不等式约束表示为 \(g(x)\le 0\)。

在实践中还会使用“标准形式/统一符号”的表述，以便统一讨论最优性条件与算法。例如将问题写为：在约束集上选择 \(x\)，使目标函数达到最小化或最大化。是否“标准形式”完全一致，取决于研究者或求解器采用的符号约定，但核心结构是“目标函数 + 约束集合”。

1.2 目标函数与约束的非线性特征

非线性规划之所以与线性规划不同，通常在于以下原因：

目标函数非线性：曲率、弯折或非凸结构会导致全局结构不易解析。
约束函数非线性：可行域边界可能是曲面而非超平面，局部几何显著影响可行性与最优解位置。
可行域连通性变化：同一不等式约束可能造成多段可行区域，使得“局部最优”与“全局最优”差距更大。

这些非线性特征使得解的性质依赖于导数、曲率以及约束在候选点附近的几何形态。

1.3 可行域、可行点与可行方向

可行域是所有满足约束条件的决策变量的集合，常记为 \[ \mathcal{F}=\{x\mid h(x)=0,\ g(x)\le 0\}. \] 可行点是集合 \(\mathcal{F}\) 中的具体向量。可行方向用于描述在某点附近如何“沿着某个方向移动仍可能保持可行”。由于不等式约束会在边界附近改变可行性，可行方向的刻画往往与约束的活跃程度（即哪些不等式约束在该点取等号）相关。

从几何角度看，局部可行方向集合反映了约束曲面的切空间结构，是推导一阶或二阶最优性条件的基础。

1.4 目标：全局最优、局部最优与可接受解

非线性问题通常不具备像线性规划那样依赖全局线性结构求得最优的便利，因此需要区分不同“最优”概念。

全局最优：在整个可行域内取得最小值（或最大值）的点。
局部最优：存在邻域，在该邻域内可行点所对应的目标值不优于该点（即无法通过足够小的扰动获得更好值）。
可接受解：在数值算法中，往往还会考虑满足一定约束容差与最优性指标（例如驻点残差或互补性残差）后给出的近似解。

在工程计算中，“可接受解”并不等同于严格数学意义的最优，但它满足求解器设定的精度与稳定性标准，便于在不确定数据与有限迭代下落地使用。

2 数学建模与实例化

2.1 从实际问题到优化模型

非线性规划首先是一种建模活动：把现实系统的目标、资源与限制转换为数学对象。一般流程包括：

明确决策变量：系统中可以选择或调节的量。
写出目标函数：用损失、成本、效益或偏差刻画需要优化的方向。
列出约束：来自物理定律、工程上限、预算、合规条件或安全裕度等。
检查模型假设与数据可得性：例如需要可微性还是只要求函数可评估。

这一过程决定了问题是否能使用成熟算法求解，以及求解代价与可解释性如何平衡。

2.2 变量、参数与约束的工程含义

在模型中：

变量代表需要优化的决策量，例如控制输入、设计尺寸、权重系数或投资分配比例。
参数是已知或估计的常量，如材料性质、需求预测、利率、容量等。
约束表达“必须满足”的要求。例如上限约束常写为 \(g(x)\le 0\)，等式约束常用于守恒关系或配平条件。

合理的变量与约束设计能够改善数值表现，例如减少尺度差异、提高约束的可辨识性，从而减少迭代失败或精度不足。

2.3 常见建模模式（最小化误差、资源约束等）

常见目标/约束结构包括：

最小化误差：例如最小二乘型目标或带权误差，以拟合观测或跟踪参考。
资源约束：预算、功耗、载荷或时间等限制，通常表现为不等式约束。
设计可行性：几何、强度或稳定性条件，往往是非线性不等式组合。
配平与守恒：等式约束用于刻画严格关系，如质量守恒或平衡条件。

这些模式在工程与应用科学中反复出现，使得建模虽复杂但可遵循相对固定的“模板”。

2.4 规模与可解性因素（维度、稀疏性、可微性）

可解性与问题规模密切相关。常见影响因素包括：

维度 \(n\)：变量越多，计算与线性代数开销通常更高。
稀疏性：若梯度与 Hessian 具有稀疏结构，可显著降低存储与求解成本。
可微性：多数算法依赖梯度或二阶信息；不可微或噪声较强的场景可能需要替代策略（如非光滑方法或近似）。
约束的尺度差异：当不同约束量纲差异大，会导致数值迭代困难，需要缩放处理。

因此，“形式正确”之外，还需要关注数值可计算性。

3 最优性条件与理论基础

3.1 可微与不可微情形的区分

理论分析通常先在可微设定下展开：目标函数与约束函数至少可求一阶导（更进一步可能要求二阶可导）。可微性保证梯度、切空间与曲率信息可用，从而推导一阶驻点与二阶性质。

若不可微，则梯度概念需要替换为次梯度、广义导数或以算法层面的近似为主。由于本章主要讨论最优性条件，重点放在可微框架下的核心结论。

3.2 一阶与二阶最优性条件

一阶最优性条件反映“在可行方向上无法实现下降”。对可微问题，一阶条件常导出在候选最优点处的驻点特征（或对约束问题的驻点方程）。二阶最优性条件则进一步利用曲率信息，用于区分局部极小、鞍点或局部极大。

直观上，一阶决定“有没有更优方向”，二阶决定“当前点的形状朝上还是朝下”。

3.3 KKT条件与拉格朗日乘子解释

KKT条件（Karush–Kuhn–Tucker条件）是处理带等式与不等式约束的常用最优性准则。其核心包含：

拉格朗日驻点：目标梯度与约束梯度的线性组合在候选点平衡。
原始可行性：候选点满足等式与不等式约束。
对偶可行性：与不等式约束相关的乘子非负（在常见约定下）。
互补松弛：不等式约束“未激活”时对应乘子为零；激活时乘子可能为正。

拉格朗日乘子可以被理解为约束的“影子价格”或“敏感度系数”：它衡量当放松某个约束时，目标值变化的边际影响倾向。

3.4 约束资格条件（如LICQ等）及其作用

KKT条件的适用通常需要额外的“约束资格条件”。这些条件用于排除约束梯度在候选点附近出现退化，从而保证拉格朗日乘子的存在性与更可靠的最优性表述。常见例子包括 LICQ（线性无关约束资格）等。

在几何层面，约束资格条件要求活跃约束的法向方向不要彼此完全“重叠”，使切空间结构具备合理维度。没有资格条件时，KKT可能仍给出必要条件，但可能在解释或数值鲁棒性上变差。

3.5 第二阶充分条件与稳定性直觉

二阶充分条件用于保证候选点确为局部极小（或至少排除鞍点/极大）。它通常涉及对某种二阶“拉格朗日形式”在切空间方向上的正定性检验。其意义在于：不仅在一阶层面无可行下降方向，在二阶层面也呈现“向上弯曲”，从而对局部最优提供更强保证。

从算法角度看，若第二阶充分条件成立，牛顿类或二阶近似法更容易表现良好，因为附近的局部结构更稳定。

4 可行性、对偶性与凸性边界

4.1 原问题与对偶问题概念

非线性规划常通过对偶性将原问题（primal）映射到对偶问题（dual）。对偶问题通过引入拉格朗日乘子，把约束信息融入目标，从而形成一个在乘子空间上优化的等价或近似问题。

在许多情形下，对偶问题的最优值可作为原问题最优值的界。界的方向取决于约定（最大化/最小化）与对偶构造。理解对偶有助于判断解的质量、也便于设计算法（例如内点法与对偶间隙控制）。

4.2 对偶间隙与对偶可行性

对偶间隙指原问题最优值与对偶问题最优值之间的差。若对偶间隙为零，常意味着存在某种强对偶性，进而使得对偶解与原问题解在最优层面高度一致。

对偶可行性通常要求乘子满足与不等式约束相关的符号条件，并在特定约束下保证对偶函数有意义。数值算法中常利用对偶可行性和间隙来做终止判据或诊断。

4.3 凸性（目标/约束）对解性质的影响

凸性是非线性规划中最重要的“边界条件”。大致而言：

凸目标 + 凸可行域（在最小化情形）会使得局部最优具有全局最优性质。
若约束集合由凸函数描述且满足适当可行性条件，可将问题转化为凸优化范畴。

当问题落入凸优化，KKT条件往往不仅是必要条件，还是充分条件，从而使求解与验证更可靠。反之，非凸问题的存在会导致多峰结构，使得算法可能停在局部极小或鞍点附近。

4.4 局部极小、鞍点与“假最优”的识别

在非凸环境中，一阶驻点并不必然对应真正的最优。典型情况包括：

鞍点：一阶条件满足，但二阶曲率在某些方向上不满足局部极小所需的正定性。
假最优（伪最优）：从一阶角度看像最优，从二阶或全局角度却不真正优。

识别这类“假最优”通常依赖二阶信息、曲率检验或算法中加入逃逸策略（如信赖域/随机扰动/二阶修正）。

5 算法框架与求解策略

5.1 梯度型方法：下降方向与步长选择

梯度型方法以目标函数的一阶信息为核心。其关键在于确定：

下降方向：沿某种方向使目标值在局部变小。
步长选择：决定每次迭代移动的幅度，常用线搜索或固定/自适应步长策略。

对带约束问题，梯度下降通常需要与可行性处理结合，例如投影或在约束上做松弛处理。

5.2 牛顿法与拟牛顿法

牛顿法利用二阶信息（Hessian）构造局部二次近似，从而在理想情形下具有更快的收敛速度。但它对可计算与数值稳定性要求较高，例如 Hessian 可能不可逆或不适定。

拟牛顿法通过迭代更新近似 Hessian（或近似逆），在减少计算成本的同时仍保持较好的收敛性质。其有效性依赖于曲率条件与近似矩阵的正定维护。

5.3 序列二次规划（SQP）

序列二次规划将原问题在当前迭代点附近用二次模型近似，并用线性化约束构造一个二次规划子问题。子问题的解给出新的搜索方向与步长，然后再进入下一轮。

SQP 的关键优势在于它能同时利用目标二阶结构与约束一阶几何，适合处理一般非线性约束问题。实际性能还与子问题求解策略、步长控制与可行性恢复有关。

5.4 内点法与障碍函数思想

内点法通过把可行域的边界“推开”，引入障碍函数或等价的对数壁垒项，将约束违反转化为目标中的惩罚，并在迭代中逐步减弱障碍，使解向约束边界靠近。

这类方法常具有良好的全局收敛特性与数值表现，尤其在不等式约束存在时。其实现通常需要求解一系列带障碍的无约束或等式约束化子问题。

5.5 约束处理：投影、松弛与罚函数

常见约束处理策略包括：

投影：对不满足约束的迭代点进行最近可行投影，但投影本身可能计算昂贵。
松弛：允许临时违反约束，通过罚项或权重使违反在优化过程中逐渐减小。
罚函数：把约束违反直接加入目标函数，例如平方罚或对数障碍；但罚权重过大可能导致数值病态。

不同策略在“可行性优先”与“最优性优先”的权衡上各不相同。

5.6 终止准则与数值稳定性

算法通常通过以下指标终止：

目标改进幅度是否足够小；
梯度或 KKT 残差是否接近零；
约束违反程度是否低于容差；
信赖域半径或步长是否趋于极小。

数值稳定性方面，常见问题包括尺度不匹配、Hessian 或雅可比矩阵病态、线搜索失败与舍入误差累积。工程上通常需要缩放、正则化以及稳健的线性代数求解策略。

6 经典问题类型与性质

6.1 无约束非线性优化

无约束情形只需要关注目标函数自身的最优性。算法通常围绕梯度与二阶信息展开，最优性条件可简化为“驻点 + 曲率判别”。由于可行性不再需要维护，问题结构更清晰，理论与算法实现通常更直接。

6.2 等式约束与不等式约束的差异

等式约束要求解严格落在某个流形上；不等式约束则允许解处于可行域内部或边界，并引入“活跃约束”的概念。不等式约束的存在使互补松弛成为KKT系统的重要组成，从而影响算法中约束线性化、乘子更新与障碍参数控制。

6.3 特定结构：二次型、分式、可分结构等

当目标或约束具有特殊形式时，能利用额外结构获得更高效率。例如：

二次型结构：可显著简化二阶信息表达，并提高子问题求解速度。
分式结构：需要处理分母为零或数值放大等问题。
可分结构：若目标由多个部分组成且变量之间联系稀疏，可用分解或块迭代降低计算量。

结构化问题常见于信号处理、统计估计、工程设计等场景。

6.4 非平滑与含约束的扩展问题概览

当函数含有绝对值、最大值、分段定义或离散化近似时，问题可能非平滑。此时传统依赖光滑梯度与 Hessian 的理论需要扩展，算法可能采用次梯度、平滑近似或专门的非光滑策略。

含约束的非平滑问题进一步增加复杂度：既要处理约束几何，又要面对目标或约束本身缺乏稳定的二阶信息。

7 复杂度与收敛性讨论

7.1 局部收敛与全局收敛的差别

局部收敛关注算法从足够接近最优点的初值出发时，迭代能否以某种速度收敛。全局收敛则更关心“从更一般的初值出发也能否最终逼近一个满足最优性条件的点”。

非凸性使得全局最优不易保证，但许多算法仍可在一定条件下证明收敛到驻点或满足KKT意义下的候选解。

7.2 梯度与Hessian可得性的影响

若梯度易得且噪声小，梯度型或拟牛顿法通常更稳定。若能可靠获得 Hessian 或高质量近似，牛顿、SQP 与内点法可加快收敛速度。

但在许多工程场景中，Hessian 的计算可能昂贵或不稳健，因此工程与软件实现常需要在“计算成本”和“收敛速度”之间取折中方案。

7.3 约束条件与收敛失败的常见原因

收敛失败可能由多种因素触发，例如：

初值不合理导致迭代远离可行区域；
约束资格不满足或退化，导致乘子与方向计算不稳定；
不可微点或数值噪声导致最优性指标难以下降；
罚权重或障碍参数设置不当，造成病态或过度保守。

对这些原因的诊断通常需要结合可行性、KKT残差、线搜索日志与子问题求解信息。

7.4 评估：迭代次数、精度与计算成本

工程评估通常权衡：

迭代次数：收敛速度快不一定代表整体耗时少；
精度：约束容差与最优性指标达到的程度；
计算成本：每步需要的梯度、Hessian或线性代数求解开销。

因此对同一问题类型，不同求解器可能呈现不同“性价比”。合理评估能够指导选型与参数调优。

8 软件与工程实践

8.1 求解器选择：面向可行性还是面向最优性

工程中常见两类侧重点：

面向可行性：优先保证约束满足，再逐步改善目标。
面向最优性：更快追求目标下降或KKT残差下降，但可能在早期允许较大约束违反。

选择依赖问题规模、约束难度和初值质量。若可行域很窄或可行初值难找，可考虑偏可行性策略的求解框架。

8.2 数值实现要点：缩放、初值与参数设置

影响显著的工程要点包括：

缩放：把变量与约束量纲调整到相近范围，减少数值误差放大。
初值：好的初值可降低迭代次数并减少失败风险；必要时可使用启发式或可行性恢复步骤。
参数设置：如容差、线搜索参数、惩罚或障碍参数更新规则。过紧可能导致慢或不收敛，过松可能得到不可靠解。

8.3 稀疏与大规模计算的工程技巧

对大规模问题，通常采用：

稀疏存储与稀疏线性代数求解；
自动微分或导数近似以减少手工实现误差；
分块或分解策略利用结构降低计算复杂度。

若 Hessian 或雅可比呈现局部耦合，可显著提高求解效率。

8.4 结果验证：KKT检验与敏感性复核

得到候选解后，一般会进行验证：

计算并检查 KKT 残差、互补性与约束违反情况；
对关键约束检查活跃集是否与理论一致；
进行轻微扰动或参数变化试算，观察解的稳定性（敏感性复核）。

这类验证可降低“数值上像最优但理论不稳”的风险，也有助于发现建模或导数实现问题。

9 相关领域与扩展

9.1 与线性规划、二次规划的关系

线性规划是非线性规划的特例：当目标与约束都为线性时，问题结构简化，常能利用成熟的单纯形或内点框架求得全局最优。二次规划通常对应某类特殊非线性形式（目标为二次函数、约束为线性），它在算法上与非线性规划存在继承关系，例如内点法与牛顿类思想可做对应延伸。

9.2 与变分不等式、互补问题的联系

一些约束优化或纳什均衡类问题可以转化为互补问题或相关的变分不等式表述。非线性规划中的互补松弛结构与互补问题有形式上的相通之处，因此在更广泛的均衡建模中，相关算法与理论会发生迁移。

9.3 与最优控制、模型预测控制的对应

最优控制将时间演化系统纳入决策过程，通常形成随时间展开的非线性约束优化问题。模型预测控制通过在滚动时域内反复求解有限时域的优化子问题，本质上也是非线性规划（或其近似形式）框架的一种工程落地。

9.4 与机器学习中的常见训练目标的映射（梗式理解：把损失函数当作“地形”，优化算法当作“爬坡者”）

在机器学习中，训练常被表述为最小化某个损失函数，同时可能加入正则项与约束条件。这些损失函数与正则项通常是非线性且非凸的，因此可以被视为非线性规划的一个实例化形式。用“梗式理解”来说：把损失函数当作“地形”，梯度/牛顿/拟牛顿或内点等优化器就是“爬坡者”，负责在这片地形上找一个合适的“低点”；但地形可能布满坑洼与山脊，爬到哪里往往取决于初始位置与算法策略。

10 常见术语与速查

10.1 常用记号表（变量、约束函数、拉格朗日量）

常见记号包括：

决策变量 \(x\)；
目标函数 \(f(x)\)；
等式约束 \(h(x)\)；
不等式约束 \(g(x)\)；
拉格朗日量 \(L(x,\lambda,\mu)\)，其中 \(\lambda\) 对应等式约束的乘子，\(\mu\) 对应不等式约束的乘子（常见约定下 \(\mu\ge 0\)）。

这些记号构成 KKT 条件与算法实现的语言基础。

10.2 典型概念：可行域、KKT、鞍点、局部最优

可行域：所有满足约束的点构成的集合。
KKT：带约束最优性的条件组，包含驻点、可行性、对偶与互补。
鞍点：一阶满足但二阶无法保证局部极小的驻点类型。
局部最优：在邻域内不再能通过小扰动改善目标的解。

这些概念在分析与排错中反复出现。

10.3 阅读公式时的变量角色速记

在读带约束优化的公式时可用以下速记：

看 目标函数 \(f(x)\)：决定要“优化”的量；
看 约束函数 \(h(x), g(x)\)：决定哪些方向“不能随便走”；
看 拉格朗日量 \(L\)：把目标与约束统一到乘子加权的表达中；
看 乘子符号：通常等式对应任意符号，不等式对应非负（常见约定）。

理解这些角色，能更快判断公式在表达“可行性”“最优性”还是“对偶信息”。