Skip to content
返回搜索结果

非线性规划

提出者
Jorge Nocedal & Stephen Wright
年份
2006
类型
Continuous mathematical optimization
类别
Mathematical programming

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

非线性规划(Nonlinear programming, NLP)是数学规划的一个分支,研究目标函数或至少一个约束条件为非线性的问题。该领域由 Jorge Nocedal 和 Stephen Wright 在其 2006 年的开创性著作中进行了全面形式化。NLP 包括基于梯度的算法——如序列二次规划(SQP)、内点法和拟牛顿法——用于寻找工程、经济学和物理科学中出现的连续决策问题的局部或全局最优解。

方法背后的直觉

想象一下,在一个被雾笼罩的崎岖山地上行走,同时待在一个围栏区域内。你无法看到整个地形,因此你能感受到脚下的坡度(梯度),调整步伐方向以向下走,并在每一步都检查是否越过了围栏(约束)。如果围栏弯曲或山丘重叠,简单的直线路径将无法奏效——你必须弯曲你的路径。非线性规划正是对这一过程的数学形式化,用数学上严格的步长和方向规则取代了直观的山地行走。

历史学

非线性规划的理论基础可追溯到 Karush (1939) 和 Kuhn 与 Tucker (1951) 推导出的 KKT 条件。实际算法在 20 世纪 60-80 年代随着 SQP 方法、增广拉格朗日方法以及包括 BFGS (1970) 在内的拟牛顿更新的发展而加速。Nocedal 和 Wright 的《数值优化》2006 年第二版成为一本权威参考书,将收敛理论、线搜索和信赖域框架以及内点法综合成一个连贯的现代处理。

何时使用

当目标函数或约束条件在不显著损失精度的情况下无法线性化,且决策变量是连续的时,应使用非线性规划。典型应用场景包括具有物理定律约束的工程设计、具有非线性风险度量的投资组合优化以及具有非线性模型形式的回归。关键假设是 f 和 c 至少是二阶连续可微的(对于基于梯度的求解器),并且约束资格条件成立。当变量是整数值时,适用混合整数非线性规划(MINLP)的扩展。对于凸问题,内点法保证全局最优性;对于非凸问题,仅存在局部保证。

局限与注意事项

  • 非凸问题仅提供局部最优性保证;全局解需要额外的全局搜索策略。
  • 要求目标函数和约束条件是光滑的(至少是可微的);非光滑问题需要专门的次微分方法。
  • 当需要精确计算 Hessian 时,计算成本随问题规模的增加而显著增长。
  • 约束资格条件可能失效(例如,在退化的可行点处),导致 KKT 条件失去理论依据。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 处理广泛的现实世界问题,其中线性和二次近似不足以满足要求。
  • 成熟的算法理论,对于凸问题具有充分研究的收敛保证。
  • 高效的基于梯度的求解器(SQP、内点法)在实践中可以扩展到数千个变量。
  • 统一的拉格朗日框架自然地容纳了混合等式和不等式约束。

应用

  • 结构和航空航天工程:在应力和挠度约束下最小化重量。
  • 投资组合管理:在非线性方差(风险)预算下最大化预期回报。
  • 化学过程设计:在热力学和安全约束下优化反应器产率。
  • 机器学习:通过无约束或有约束的 NLP 求解器训练神经网络和核模型。
  • 能源系统:电力网调度中的最优潮流问题,具有非线性物理约束。

使用方式

使用方式

1

分析师定义一个标量目标函数 f(x) 在决策变量 x ∈ R^n 上进行最小化或最大化,同时伴随等式约束 c_i(x) = 0 和不等式约束 c_j(x) ≥ 0。在此阶段,识别哪些约束在候选解处是活跃的以及正则条件(约束资格)是否成立至关重要,这决定了适用的最优性理论。

公式
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}
2

Karush-Kuhn-Tucker(KKT)条件提供了局部最优的一阶必要条件。它们要求拉格朗日函数的平稳性、不等式乘子(λ_j c_j = 0)的互补松弛性、对偶可行性(λ_j ≥ 0)以及原可行性。算法通过迭代构造满足这些条件的点,并利用二阶充分性条件确认一个平稳点确实是局部最小值。

公式
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}
3

在每次迭代 k 中,算法计算一个搜索方向 p_k——通常通过 Hessian 的拟牛顿近似 B_k(例如 BFGS)或精确的二阶导数系统——以及一个满足 Wolfe 或 Armijo 条件的步长 α_k。SQP 方法通过求解二次规划子问题来获得 p_k,而内点法则添加障碍项来处理不等式约束并驱动迭代点趋向可行域的内部。

公式
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)
4

当拉格朗日函数的梯度范数和最大约束违反度均低于预设容差(ε 和 δ)时,算法终止。由于 NLP 通常是非凸的,算法可能收敛到局部最优解;当需要全局最优性时,建议从不同起始点多次重启或采用全局搜索策略(如分支定界法、多重重启法)。

公式
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \delta

常见陷阱

  • 忽略约束资格条件,在退化或不可行点处盲目应用 KKT 条件会导致虚假解。
  • 使用尺度不当的变量会导致 Hessian 近似病态,收敛缓慢或失败。
  • 在非凸情况下,接受找到的第一个局部最小值而不进行多次重启,可能会显著错过全局最优解。
  • 有限差分梯度近似会引入数值误差;强烈推荐使用解析或自动微分。

常见问题

每个线性规划也是非线性规划吗?

是的。线性规划是 NLP 的一个特例,其中目标函数和所有约束条件都是仿射的。然而,LP 有单纯形法和内点法等算法,它们利用了线性特性,比通用 NLP 求解器效率高得多;使用通用 NLP 求解器处理 LP 是浪费的,但数学上是有效的。

在什么情况下可以相信 KKT 点是全局最小值?

当 NLP 是凸的——即 f 是凸函数且可行集是凸集——任何 KKT 点都是全局最小值。对于非凸问题,此保证不成立,KKT 点仅是局部最小值(在二阶充分性条件成立的情况下)。否则,需要分支定界法或凸松弛等全局优化方法。

SQP 方法和内点法有什么区别?

SQP 迭代地求解二次规划子问题,这些子问题在局部上近似 NLP,通常适用于约束较多的中小规模问题。内点(障碍)法严格保持在可行域内部,并且对于大型稀疏问题往往具有更好的可扩展性。在适当的正则条件下,两者都具有超线性收敛性。

相关方法

参考文献

  1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

    ISBN:978-0-387-30303-1
    已复制。