类型b：

本文档摘自《Wiley Encyclopedia of Computer Science and Engineering》中由Daniel Solow（Case Western Reserve University）撰写的“Linear and Nonlinear Programming”条目，出版于2008年。该条目系统性地介绍了线性规划（Linear Programming, LP）与非线性规划（Nonlinear Programming, NLP）的核心理论、算法及应用，并对比了两者的差异与挑战。以下是其主要内容的分点阐述：

1. 优化问题的数学定义与分类

优化问题的目标是通过调整n个变量的取值，在满足有限约束条件下最小化或最大化目标函数。文档以两个典型问题为例：
- 线性规划（LP1）：目标函数与约束均为线性，变量连续（如允许分数解）。其几何特征是可行域为凸多面体，最优解必出现在有限个极值点（extreme points）之一。
- 非线性规划（NLP1）：目标函数或至少一个约束为非线性，可行域可能非凸，最优解未必是极值点。例如，NLP1的约束包含二次函数（如$x_1^2 + x_2^2 \leq 9$）。

支持理论：线性规划的几何性质由George Dantzig（1951）提出的单纯形法（Simplex Algorithm, SA）利用，该算法通过迭代极值点寻找最优解。

2. 线性规划的求解方法与对偶理论

单纯形法分为两阶段：
- 阶段1（初始化）：寻找初始可行解或判定问题无解。
- 阶段2（迭代优化）：通过计算梯度方向（方向向量d）和步长（t）沿可行域边缘移动，直至满足最优性条件。

对偶理论（Duality Theory）是核心工具，其作用包括：
- 最优性验证：若原始问题与对偶问题的可行解目标值相等，则两者均为最优解。
- 敏感性分析：对偶变量（影子价格）量化约束右端项变化对目标函数的影响。

算法效率：单纯形法在最坏情况下需指数级迭代次数，但实践中高效；Khachian（1979）和Karmarkar（1984）提出的内点法（Interior Point Methods, IPM）虽具有多项式复杂度，但实际性能因问题结构而异。

3. 非线性规划的挑战与求解策略

与线性规划相比，非线性规划面临以下难点：
- 最优性判定困难：无全局最优的高效检验方法，仅能通过局部最优的必要条件（如梯度为零或KKT条件）停止算法。
- 收敛性问题：算法可能无限迭代，仅能逼近理论解。

无约束问题（NLP2）的求解依赖梯度下降法：
- 停止规则：$\nabla f(x) = 0$。
- 方向选择：常用负梯度方向（$- \nabla f(x)$），但共轭梯度法等可提升效率。

约束问题（NLP3）需满足KKT条件（Karush-Kuhn-Tucker Conditions）：
1. 可行性（$g_i(x) \leq 0$且乘子$u_i \geq 0$）；
2. 互补松弛（$u_i g_i(x) = 0$）；
3. 梯度条件（$\nabla f(x) + \sum u_i \nabla g_i(x) = 0$）。

算法局限性：非线性规划的求解高度依赖初始值，且易陷入局部最优，凸性假设可缓解此问题。

4. 应用与扩展领域

线性与非线性规划广泛应用于：
- 计算机科学：算法设计、资源调度；
- 工程与运筹学：供应链优化、网络流问题；
- 经济学：成本最小化模型。

相关研究方向包括整数规划（离散变量）、大规模优化、非光滑优化（Nonsmooth Optimization）及方程组求解。

文献价值与意义

本文的价值在于：
1. 系统性对比：清晰区分线性与非线性规划的理论与算法差异；
2. 历史脉络：从单纯形法到内点法的演进，反映优化领域的里程碑进展；
3. 实践指导：通过商业软件（如CPLEX、LINDO）的案例分析，强调算法在复杂问题中的实用性。

亮点：
- 对偶理论的经济学解释（如影子价格）将数学工具与实际决策关联；
- 明确指出非线性规划的求解难点，为后续研究（如凸优化、启发式算法）提供方向。

本文可作为优化领域研究者的理论参考，尤其适合需选择算法或理解模型局限性的应用场景。