KNOWECON WIKI

ARTICLE

Nonlinear Programming

非线性规划 (Nonlinear Programming) 非线性规划（Nonlinear Programming, NLP）是最优化理论的核心分支，研究目标函数或约束条件中至少有一个是非线性函数的优化问题。其标准形式为： 其中 x R^n 为决策变量，f: R^n R 为目标函数，g_i 为不等式约束，h_j 为等式约束。当 f, g_i, h_j 至少有

浏览 0 更新 2025-10-31

非线性规划 (Nonlinear Programming)

非线性规划（Nonlinear Programming, NLP）是最优化理论的核心分支，研究目标函数或约束条件中至少有一个是非线性函数的优化问题。其标准形式为：

min⁡xf(x)s.t.gi(x)≤0,i=1,…,mhj(x)=0,j=1,…,p\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \end{aligned}

其中 x∈Rn\mathbf{x} \in \mathbb{R}^n 为决策变量，f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} 为目标函数，gig_i 为不等式约束，hjh_j 为等式约束。当 f,gi,hjf, g_i, h_j 至少有一个是非线性函数时，问题即为非线性规划。与之相对，若所有函数均为线性，则退化为线性规划。

非线性规划在经济分析中占据核心地位，因为大多数经济关系本质上是非线性的：边际效用递减、规模报酬变化、无差异曲线的凸性、以及生产函数中的替代弹性等，几乎都无法用线性函数充分刻画。

问题的分类

非线性规划问题可根据函数性质进一步分类：

  • 无约束优化：m=p=0m = p = 0，仅最小化 f(x)f(\mathbf{x})。经典条件为一阶梯度为零（∇f(x∗)=0\nabla f(\mathbf{x}^*) = \mathbf{0}）且海塞矩阵正定。
  • 凸规划：若 ff 为凸函数，所有 gig_i 为凸函数（即约束集为凸集），则问题为凸规划。凸规划的局部最优解自动是全局最优解，这是非线性规划中最重要的"好性质"。
  • 二次规划：ff 为二次函数，约束为线性函数。均值-方差模型（Markowitz 投资组合选择）即为典型的二次规划问题。
  • 几何规划：目标函数和约束均为正项式（posynomial），在工程设计和Cobb-Douglas生产优化中有特殊应用。
  • 可分规划：目标函数可分解为单变量函数之和，即 f(x)=∑kfk(xk)f(\mathbf{x}) = \sum_k f_k(x_k)，便于使用动态规划或逐次线性近似求解。

一阶必要条件：KKT 条件

非线性规划理论中最重要的结果是Karush-Kuhn-Tucker 条件（KKT 条件）。对于上述标准形式，定义拉格朗日函数：

L(x,μ,λ)=f(x)+∑i=1mμigi(x)+∑j=1pλjhj(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^{m} \mu_i g_i(\mathbf{x}) + \sum_{j=1}^{p} \lambda_j h_j(\mathbf{x})

在适当的约束规范（constraint qualification，如线性独立约束规范 LICQ 或 Slater 条件）下，若 x∗\mathbf{x}^* 是局部最优解，则存在乘子 μ∗≥0\boldsymbol{\mu}^* \geq \mathbf{0} 和 λ∗\boldsymbol{\lambda}^*，满足以下 KKT 条件：

稳定性:∇xL(x∗,μ∗,λ∗)=0原始可行性:gi(x∗)≤0,hj(x∗)=0对偶可行性:μi∗≥0互补松弛:μi∗⋅gi(x∗)=0,∀i\begin{aligned} \text{稳定性:} \quad & \nabla_{\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\mu}^*, \boldsymbol{\lambda}^*) = \mathbf{0} \\ \text{原始可行性:} \quad & g_i(\mathbf{x}^*) \leq 0, \quad h_j(\mathbf{x}^*) = 0 \\ \text{对偶可行性:} \quad & \mu_i^* \geq 0 \\ \text{互补松弛:} \quad & \mu_i^* \cdot g_i(\mathbf{x}^*) = 0, \quad \forall i \end{aligned}

互补松弛条件是理解经济均衡的关键：若某一约束在最优解处非紧（gi(x∗)<0g_i(\mathbf{x}^*) < 0），则其对应的影子价格 μi∗\mu_i^* 必须为零——即资源未被充分利用时，其边际价值为零。反之，若影子价格为正，则约束必然是紧的。

二阶条件与加边海塞矩阵

KKT 条件仅是一阶必要条件。二阶充分条件涉及加边海塞矩阵（Bordered Hessian），在约束优化中，须检查拉格朗日函数的海塞矩阵在切空间上的投影是否正定或负定。具体地，对于等式约束问题，最大化需要加边海塞矩阵的最后 n−pn-p 个顺序主子式交替符号；最小化需要它们全为负。对于不等式约束，需在紧约束构成的子空间上验证相应的二阶条件。

求解算法

由于非线性规划的全局最优性难以保证（除非凸性成立），实际求解依赖于迭代算法：

  1. 梯度下降法：沿负梯度方向迭代，xk+1=xk−αk∇f(xk)\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)。简单但收敛慢。
  2. 牛顿法：利用二阶泰勒展开，迭代公式为 xk+1=xk−[∇2f(xk)]−1∇f(xk)\mathbf{x}_{k+1} = \mathbf{x}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1} \nabla f(\mathbf{x}_k)。二次收敛但每步需计算并求逆海塞矩阵，成本高。
  3. 拟牛顿法（BFGS, L-BFGS）：用迭代更新近似海塞矩阵，避免直接计算二阶导数。L-BFGS 是处理大规模无约束问题的标准选择。
  4. 序列二次规划（SQP）：在每步迭代中将原问题近似为二次规划子问题，同时线性化约束。SQP 被认为是中小规模约束非线性规划最有效的算法之一。
  5. 内点法：通过障碍函数将不等式约束纳入目标函数，使迭代点始终保持在可行域内部。Karmarkar 算法后在非线性规划中得到推广，是现代大规模优化（如 IPOPT 求解器）的基石。
  6. 增广拉格朗日法：在拉格朗日函数中加入二次罚项，结合了对偶上升和罚函数各自的优点，适合处理带等式约束的非凸问题。

经济学中的典型应用

非线性规划在经济理论和实证研究中的应用无处不在：

  • 消费者理论：效用最大化和支出最小化是对偶的非线性规划问题。前者在预算约束下最大化非线性效用函数，后者在效用约束下最小化线性支出。两者的解通过谢泼德引理和罗伊恒等式相互联系。
  • 厂商理论：利润最大化和成本最小化。生产函数（如 CES、translog）的非线性使得一阶条件产生非线性方程系统。
  • 计量经济学中的极值估计：最大似然估计（MLE）和广义矩估计（GMM）均归结为非线性优化问题。MLE 最大化对数似然函数，GMM 最小化矩条件的二次型。这些问题的维数随参数数量增长，对算法效率要求极高。
  • 一般均衡计算：可计算一般均衡（CGE）模型需要求解大规模非线性方程组，常通过将均衡条件表述为非线性互补问题（NCP）来实现。
  • 最优控制与动态规划：连续时间优化问题（如 Ramsey 增长模型）通过庞特里亚金极大值原理转化为伴随变量的非线性方程组；离散时间问题则通过Bellman 方程求解，两者本质上都是非线性规划的动态延伸。

与线性规划的比较

| 特征 | 线性规划 (LP) | 非线性规划 (NLP) | |---|---|---| | 函数形式 | 目标与约束均为线性 | 至少一个非线性 | | 最优解位置 | 总是位于可行域顶点 | 可在可行域内部或边界任意点 | | 全局最优性 | 自动保证 | 仅凸规划保证 | | KKT 条件 | 充分且必要 | 仅必要（非凸时） | | 算法复杂度 | 多项式时间（单纯形法或内点法） | NP-hard（一般非凸情形） | | 影子价格 | 对偶变量的恒定解释 | 局部有效，依赖最优解位置 |

非线性规划的"代价"在于放弃了线性规划中方便的性质——全局最优性、对偶强定理和对偶变量的全局解释。然而，它换取了对经济现实的忠实刻画，是现代数理经济学不可或缺的分析框架。

计算实践中的注意事项

在应用中需要特别注意：(1) 缩放——变量和约束的尺度差异会导致海塞矩阵病态；(2) 多起点策略——非凸问题应从不同初始点启动算法以寻找更好的局部最优解；(3) 自动微分——现代求解器（如 JuMP + Ipopt、Pyomo、GAMS）利用自动微分精确计算梯度与海塞矩阵，避免手动推导和数值误差。非线性规划的理论之美在于它统一了经济分析中从微观决策到宏观均衡的优化逻辑，而其计算实践则是连接理论模型与数据实证的桥梁。