Nonlinear programming — 非线性规划

非线性规划 (NLP) 是数学规划和运筹学的一个分支，处理目标函数和/或至少一个约束是决策变量的非线性函数的优化问题。

NLP 是线性规划的推广，可以为更广泛的现实系统和过程建模，其中变量之间的依赖关系不是严格成比例的（即用曲线而非直线描述）。

主题与用途

非线性规划用于在以下情况中寻找最优解：

• 目标指标（利润、成本、效率等）对可控参数的依赖关系是非线性的（例如，规模报酬递减、二次成本）。
• 资源或技术过程的约束由非线性关系描述（例如，化学反应、物理定律、经济依赖关系）。

NLP 问题出现在许多领域：

• 工程设计（结构、过程优化）。
• 经济与金融（考虑风险的投资组合优化、市场建模）。
• 化学技术（反应器模式优化）。
• 机器学习（神经网络训练、支持向量机）。
• 生产过程管理。物流（考虑非线性成本）。

NLP 问题的数学表述

非线性规划的一般问题表述如下：

需要找到一组决策变量的值，以最大化或最小化一个非线性目标函数。同时，这些变量的值必须满足一个约束系统，这些约束可以表示为不等式（例如，“A 值必须小于或等于 B”）或等式（例如，“C 值必须精确等于 D”）。重要的是，描述目标或约束的函数中至少有一个是非线性的。通常还会加上变量的非负性条件，即要求其值大于或等于零。

所有满足约束条件的变量值集合构成了可行域。

与线性规划的区别

非线性规划与线性规划 (LP) 有显著不同：

• 非线性：目标函数或约束（或两者）包含非线性依赖关系。
• 可行域的性质：NLP 中的可行域可以是非凸的（与 LP 不同，LP 的可行域总是一个凸多面体）。
• 最优解的性质：NLP 的最优解不一定在可行域的顶点，它可能位于边界或域内。NLP 中可能存在非全局最优的局部最优解。
• 求解复杂性：NLP 问题通常比 LP 问题难解得多。不存在类似于单纯形法的、适用于所有 NLP 问题的通用算法。

NLP 的主要难点与挑战

解决非线性规划问题伴随着一系列困难：

• 局部极值的存在：大多数 NLP 方法只能保证找到局部最优解（在某个邻域内的最优解）。寻找全局最优解（在整个可行域内的最佳解）是一个复杂的任务，尤其对于非凸问题。
• 非凸性：如果问题是非凸的（目标函数或可行域非凸），则可能存在多个局部最优解，标准的梯度法可能会“卡”在其中一个。
• 计算复杂性：与 LP 相比，NLP 的求解算法通常需要更多的计算资源。

NLP 问题的重要类别

尽管总体上很复杂，但存在一些重要的 NLP 问题子类，人们已为其开发了有效的求解方法：

• 凸规划：在凸可行解集上最小化凸函数（或最大化凹函数）的问题。关键特性：任何局部最小值也是全局最小值。这大大简化了寻找最优解的过程。
• 二次规划：目标函数是二次函数，而所有约束都是线性的。
• 可分离规划：目标函数和约束可以表示为多个函数的和，其中每个函数仅依赖于一个变量。

NLP 问题的求解方法

非线性规划 (NLP) 问题的求解方法

I. 无约束优化方法：

• 梯度法（最速下降法、共轭梯度法）；
• 牛顿法和拟牛顿法（例如，BFGS）；
• 使用海森矩阵近似的方法。

II. 约束优化方法：

• 变换方法：
  • 罚函数法 (penalty methods)；
  • 障碍函数法 (barrier methods)。
• 直接搜索方向法：
  • 可行方向法。
• 基于最优性条件的方法：
  • 卡罗需-库恩-塔克 (KKT) 条件法；
  • 拉格朗日乘子法。
• 迭代法：
  • 序列二次规划 (SQP)；
  • 内点法。

III. 全局优化方法：

• 启发式与元启发式方法：
  • 遗传算法；
  • 模拟退火；
  • 禁忌搜索 (tabu search)。
• 确定性方法：
  • 分支定界法 (branch and bound)；
  • 针对特殊结构问题的全局优化算法。

参考文献

• Bazaraa M. S., Shetty C. M. 『非線形計画法：理論とアルゴリズム』モスクワ：ミール出版社、1982年。
• Fiacco A. V., McCormick G. P. 『非線形計画法：逐次無制約最小化法』モスクワ：ミール出版社、1972年。
• Himmelblau D. M. 『応用非線形計画法』モスクワ：ミール出版社、1975年。
• Nocedal J., Wright S. J. Numerical Optimization. — Springer, 2006. (2nd ed.)