关于非线性优化小记
非线性优化（Nonlinear Optimization）
1. 什么是非线性优化？
非线性优化是指 目标函数 或 约束条件 中至少有一个是非线性的优化问题。它广泛应用于工程、经济、人工智能、机器学习等领域，用于求解最优解的问题。
非线性优化通常可以表示为以下数学形式：
min x f ( x ) 或 max x f ( x ) \min_{x} f(x) \quad \text{或} \quad \max_{x} f(x) xminf(x)或xmaxf(x)
带约束条件的情况：
min x f ( x ) s.t. g i ( x ) ≤ 0 , i = 1 , 2 , . . . , m h j ( x ) = 0 , j = 1 , 2 , . . . , p \begin{aligned} \min_{x} &\quad f(x) \\ \text{s.t.} &\quad g_i(x) \leq 0, \quad i = 1, 2, ..., m \\ &\quad h_j(x) = 0, \quad j = 1, 2, ..., p \end{aligned} xmins.t.f(x)gi(x)≤0,i=1,2,...,mhj(x)=0,j=1,2,...,p
其中：
- f ( x ) f(x) f(x) 是目标函数，可能是非线性的；
- g i ( x ) g_i(x) gi(x) 是不等式约束条件；
- h j ( x ) h_j(x) hj(x) 是等式约束条件；
- x x x 是决策变量，可能是标量或向量。
2. 线性优化 vs. 非线性优化
| 特性 | 线性优化 | 非线性优化 |
|---|---|---|
| 目标函数 | 线性 | 可能是非线性 |
| 约束条件 | 线性 | 可能是非线性 |
| 可解性 | 通常可以使用线性规划（Simplex、内点法）求解 | 可能需要迭代数值方法 |
| 计算复杂度 | 通常多项式时间可解 | 可能是 NP 难问题 |
| 解的性质 | 只有一个全局最优解（凸优化） | 可能存在局部最优解 |
3. 非线性优化问题的类型
1. 无约束非线性优化（Unconstrained Nonlinear Optimization）
-
只有目标函数 f ( x ) f(x) f(x)，无约束。
-
例如：
min x f ( x ) = x 2 + sin ( x ) \min_{x} f(x) = x^2 + \sin(x) xminf(x)=x2+sin(x) -
解决方法：梯度下降法、牛顿法、共轭梯度法等。
2. 有约束非线性优化（Constrained Nonlinear Optimization）
-
存在非线性等式或不等式约束：
min x f ( x ) s.t. g ( x ) ≤ 0 , h ( x ) = 0 \begin{aligned} \min_{x} & \quad f(x) \\ \text{s.t.} & \quad g(x) \leq 0, \quad h(x) = 0 \end{aligned} xmins.t.f(x)g(x)≤0,h(x)=0 -
解决方法：拉格朗日乘子法、KKT 条件、罚函数法、SQP（序列二次规划）等。
3. 凸非线性优化（Convex Nonlinear Optimization）
- 目标函数 f ( x ) f(x) f(x) 和可行域（约束）都是凸的。
- 只要局部最优解存在，就一定是全局最优解。
- 解决方法：内点法、梯度投影法等。
4. 非凸非线性优化（Non-Convex Nonlinear Optimization）
- 目标函数或约束是非凸的，可能存在多个局部最优解。
- 解决方法：模拟退火、遗传算法、粒子群优化等启发式方法。
4. 解决非线性优化问题的方法
1. 梯度下降法（Gradient Descent）
-
适用于无约束优化问题。
-
迭代公式：
x ( k + 1 ) = x ( k ) − α ∇ f ( x ( k ) ) x^{(k+1)} = x^{(k)} - \alpha \nabla f(x^{(k)}) x(k+1)=x(k)−α∇f(x(k))
其中 α \alpha α 是学习率。
2. 牛顿法（Newton’s Method）
-
适用于二阶可微的无约束优化问题。
-
迭代公式：
x ( k + 1 ) = x ( k ) − H f ( x ( k ) ) − 1 ∇ f ( x ( k ) ) x^{(k+1)} = x^{(k)} - H_f(x^{(k)})^{-1} \nabla f(x^{(k)}) x(k+1)=x(k)−Hf(x(k))−1∇f(x(k))
其中 H f ( x ) H_f(x) Hf(x) 是 Hessian 矩阵（二阶导数矩阵）。
3. 拉格朗日乘子法（Lagrange Multipliers）
-
适用于有等式约束的优化问题：
L ( x , λ ) = f ( x ) + λ h ( x ) \mathcal{L}(x, \lambda) = f(x) + \lambda h(x) L(x,λ)=f(x)+λh(x) -
通过求解 ∇ L = 0 \nabla \mathcal{L} = 0 ∇L=0 找到候选解。
4. KKT 条件（Karush-Kuhn-Tucker Conditions）
- 适用于有约束的优化问题，是非线性规划的必要条件：
- 一阶条件（Lagrangian 取极值）
- 可行性条件
- 互补松弛条件
- 拉格朗日乘子非负性
- 在凸优化问题中，满足 KKT 条件的解就是最优解。
5. 启发式算法
- 模拟退火（Simulated Annealing, SA）：基于物理退火过程，用于逃离局部最优解。
- 遗传算法（Genetic Algorithm, GA）：基于生物进化原理，适用于高维复杂问题。
- 粒子群优化（Particle Swarm Optimization, PSO）：基于群体智能寻优。
5. 非线性优化的实际应用
非线性优化在现实世界中应用广泛，例如：
- 机器学习：神经网络训练（如反向传播算法）。
- 金融：投资组合优化（如马科维茨均值-方差模型）。
- 工程设计：结构优化（如飞机机翼形状优化）。
- 经济学：效用最大化、成本最小化问题。
- 路径规划：无人机或自动驾驶最优路径规划。
6. 总结
- 非线性优化 处理目标函数或约束为非线性的优化问题。
- 求解方法 包括梯度下降、牛顿法、KKT 条件、SQP、启发式算法等。
- 广泛应用 于机器学习、金融、工程、路径规划等领域。