非线性规划

非线性规划 (Nonlinear Programming, NLP)

非线性规划 (Nonlinear Programming, NLP) 是运筹学和数学优化的一个核心分支，致力于解决目标函数或约束条件中至少包含一个非线性函数的优化问题。与更简单的线性规划 (Linear Programming, LP) 相对，非线性规划处理的问题形式更普遍，更能精确地模拟现实世界中复杂的经济、金融和工程系统。

数学表述

一个标准的非线性规划问题可以表示为寻找一组决策变量 $x = (x_1, x_2, \ldots, x_n)$，使得：

最小化:

服从于:

其中：

• $x \in \mathbb{R}^n$ 是 决策变量 (Decision Variables) 的向量。
• $f: \mathbb{R}^n \to \mathbb{R}$ 是 目标函数 (Objective Function)，它是我们要最小化（或最大化）的函数。
• $g_i: \mathbb{R}^n \to \mathbb{R}$ 是一组 不等式约束函数 (Inequality Constraint Functions)。
• $h_j: \mathbb{R}^n \to \mathbb{R}$ 是一组 等式约束函数 (Equality Constraint Functions)。

问题的核心特征在于，函数 $f(x)$、$g_i(x)$ 或 $h_j(x)$ 中至少有一个是非线性函数。如果所有这些函数都是线性的，那么该问题就退化为一个线性规划问题。

满足所有约束条件的决策变量 $x$ 的集合构成了问题的 可行域 (Feasible Region)。非线性规划的目标就是在可行域内找到一个点 $x^*$，使得目标函数 $f(x)$ 的值达到最小。

与线性规划 (LP) 的关键区别

理解非线性规划的最佳方式之一是将其与线性规划进行对比。

• 函数形式：线性规划中目标函数和所有约束都是线性函数；非线性规划中目标函数或至少一个约束是非线性函数。
• 可行域：线性规划的可行域是一个凸多面体 (convex polyhedron)；非线性规划的可行域可以是任何形状，可能是非凸的、甚至是不连通的。
• 最优解位置：线性规划若存在最优解，则至少有一个最优解位于可行域的某个顶点上；非线性规划的最优解可以位于可行域的任何位置——内部、边界或顶点。
• 解的性质：线性规划中任何局部最优解都是全局最优解；非线性规划中可能会存在多个局部最优解 (Local Optima)，找到的解不一定是全局最优解 (Global Optimum)。
• 求解算法：线性规划使用单纯形法 (Simplex Method) 或内点法 (Interior-Point Methods)，可以在有限时间内找到全局最优解；非线性规划的算法多样，如梯度下降法、牛顿法、序列二次规划等，通常只能保证收敛到局部最优解。

非线性规划中的核心概念

凸性 (Convexity)

凸性是 NLP 理论中的一个分水岭。一个优化问题如果其目标函数是凸函数，且可行域是凸集，则被称为 凸优化 (Convex Optimization) 问题。

• 凸集 (Convex Set)：一个集合 $S$ 是凸的，如果对于集合中任意两点 $x, y \in S$，连接这两点的线段上的所有点也都属于该集合。即，对于任意 $\lambda \in [0, 1]$，都有 $\lambda x + (1-\lambda)y \in S$。
• 凸函数 (Convex Function)：一个函数 $f$ 是凸的，如果其定义域是凸集，并且对于定义域中任意两点 $x, y$ 和任意 $\lambda \in [0, 1]$，都有 $f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)$。几何上，函数图形上任意两点之间的弦都在这两点之间的函数图形的上方。

凸优化的重要性在于：对于一个凸优化问题，任何局部最优解都是全局最优解。这极大地简化了求解过程，因为算法一旦找到一个局部最小值，就可以停止并宣布其为全局最优解。许多针对一般 NLP 的算法在应用于凸问题时，具有更强的理论保证和更好的实际表现。

最优性条件：KKT 条件

对于有约束的非线性规划问题，我们如何判断一个点是否为最优解？卡罗需-库恩-塔克条件 (Karush-Kuhn-Tucker Conditions, KKT) 提供了一阶必要条件。对于满足某些正则性条件（如约束规范）的问题，KKT 条件是局部最优解的必要条件。对于凸优化问题，KKT 条件是全局最优解的充分条件。

假设问题是前面定义的标准形式，点 $x^*$ 是一个局部最优解。在满足正则性的前提下，存在一组常数 $\mu_i$（对应不等式约束）和 $\lambda_j$（对应等式约束），称为拉格朗日乘子，使得以下四个条件在 $x^*$ 处成立：

1. 平稳性 (Stationarity)： \[ \nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^p \lambda_j \nabla h_j(x^*) = 0 \] 这表明目标函数和约束函数梯度的线性组合为零，意味着在最优解处，目标函数梯度的方向被约束梯度的方向所"平衡"。
2. 原始可行性 (Primal Feasibility)： \[ g_i(x^*) \le 0, \quad \forall i=1, \ldots, m \] \[ h_j(x^*) = 0, \quad \forall j=1, \ldots, p \] 这表示最优解必须满足所有的约束条件。
3. 对偶可行性 (Dual Feasibility)： \[ \mu_i \ge 0, \quad \forall i=1, \ldots, m \] 不等式约束的拉格朗日乘子必须为非负。
4. 互补松弛性 (Complementary Slackness)： \[ \mu_i g_i(x^*) = 0, \quad \forall i=1, \ldots, m \] 该条件表明，对于任意一个不等式约束，如果该约束在最优解处不是紧的（即 $g_i(x^*) < 0$），那么其对应的拉格朗日乘子 $\mu_i$ 必须为零。反之，如果 $\mu_i > 0$，则该约束必须是紧的（$g_i(x^*) = 0$）。

KKT 条件是现代非线性规划算法设计和分析的理论基石。

常见求解算法

由于 NLP 问题的多样性和复杂性，不存在像单纯形法之于 LP 那样的"万能"算法。常见的算法类别包括：

• 梯度下降法 (Gradient Descent)：一种基本的一阶迭代算法，通过沿着目标函数梯度的反方向移动来逐步逼近局部最小值。适用于无约束或简单约束的问题。
• 牛顿法 (Newton's Method)：一种二阶算法，利用目标函数的二阶导数（Hessian矩阵）信息来加速收敛。收敛速度快，但计算成本高。
• 拟牛顿法 (Quasi-Newton Methods)：如 BFGS 和 L-BFGS 算法，试图在不直接计算 Hessian 矩阵的情况下，近似其信息，从而在计算效率和收敛速度之间取得平衡。
• 序列二次规划 (Sequential Quadratic Programming, SQP)：一种处理有约束 NLP 问题的强大方法。在每次迭代中，它通过求解一个二次规划子问题来确定搜索方向。
• 内点法 (Interior-Point Methods)：也称为障碍法，通过在一系列修改后的目标函数（加入了惩罚项以避免违反约束）上进行迭代来求解问题。它在处理大规模问题时非常有效。

在经济、金融与统计中的应用

非线性规划在定量学科中有着广泛的应用：

• 经济学： \begin{itemize}
• 效用最大化：消费者在预算约束下，选择商品组合以最大化其非线性的效用函数。
• 利润最大化：企业在面对非线性的需求曲线或成本函数时，决定产量和价格以最大化利润。
• 一般均衡模型：在 CGE 模型中，求解市场出清的均衡价格和数量通常需要解一个复杂的非线性方程组或优化问题。

\item 金融学：

• 投资组合优化：经典的马科维茨模型旨在最小化投资组合的方差（一个二次函数），同时满足期望收益率的约束。这本质上是一个二次规划 (Quadratic Programming, QP) 问题，是 NLP 的一个特例。
• 衍生品定价：在一些复杂的期权定价模型中，校准模型参数以匹配市场价格是一个非线性最小二乘问题。

\item 统计学：

• 最大似然估计 (Maximum Likelihood Estimation, MLE)：许多统计模型的参数估计涉及到最大化对数似然函数。这个函数通常是高度非线性的，其求解过程就是一个无约束的非线性规划问题。
• 非线性最小二乘法 (Nonlinear Least Squares)：当拟合的模型对参数是非线性时，需要通过最小化残差平方和来估计参数，这是一个 NLP 问题。

\end{itemize}