最优化（Optimization）是数学中的一个核心分支，研究如何在给定的约束条件下，从所有可行方案中找到使某个目标函数取极值（极大值或极小值）的最优解。最优化理论与算法广泛存在于工程设计、经济决策、机器学习、运筹管理、信号处理等几乎所有科学技术领域中。
一个标准的最优化问题可以表述为：
其中 是决策变量（向量）， 是目标函数， 是不等式约束， 是等式约束， 是定义域。若 且没有任何约束，则称为无约束优化。
根据目标函数和约束的性质，最优化可以划分为多个重要子领域。
线性规划（Linear Programming, LP）是目标函数和约束条件均为仿射函数（线性函数 + 常数项）的最优化问题。它是运筹学中最成熟、应用最广泛的分支之一。
其中 是成本向量， 是约束矩阵， 是右端向量。
每个线性规划问题都有一个对应的对偶问题。原始问题和对偶问题之间有密切的联系：
对偶理论在线性规划的敏感性分析、分解算法中发挥着重要作用。
| 算法 | 复杂度 | 适用场景 |
|---|---|---|
| 单纯形法（Simplex） | 指数级最坏情况，多项式平均 | 中小规模，稀疏矩阵 |
| 内点法（Interior Point） | 大规模问题 | |
| 椭球法（Ellipsoid） | 理论重要，实际少用 | |
| 网络单纯形法 | 多项式 | 网络流问题 |
在实际工程中使用 LP，大部分情况并不需要自己实现求解器。推荐使用成熟的求解器库：
- 商用求解器：Gurobi、CPLEX（学术免费，性能极强）
- 开源求解器：HiGHS、GLPK、SCIP
- Python 接口：
scipy.optimize.linprog（内点法 + 单纯形法可选）、PuLP（建模语言式）一个常见坑点：原始-对偶严格可行内点法的收敛性很大程度取决于问题的数值条件。当约束矩阵 近似奇异时，Cholesky 分解中的主元可能接近零，导致求解失败。此时需要做预处理——消去冗余约束、对列做尺度归一化。
凸优化（Convex Optimization）是目标函数为凸函数、可行集为凸集的最优化问题。凸优化的核心魅力在于：任何局部最优解都是全局最优解。
凸集：对于集合 中任意两点 和 ，有 。
凸函数：对于凸集定义域内的任意 和 ，有：
凸函数的一阶条件是：，即切线永远是函数的下界。
凸优化问题
├── 线性规划（LP）
├── 二次规划（QP）—— 凸二次目标 + 线性约束
├── 二次约束二次规划（QCQP）
├── 半定规划（SDP）
├── 锥规划
│ ├── 二阶锥规划（SOCP）
│ └── 半定锥规划（SDP）
└── 几何规划（GP）—— 可变换为凸形式
Karush–Kuhn–Tucker（KKT）条件是最优性条件的推广。对于凸优化问题，KKT 条件是充分必要条件：
Hugo 的经验：CVXPY 写问题非常方便，但要注意其默认求解器（ECOS）对某些病态问题收敛慢。遇到求解失败时，切换为 SCS 求解器（一阶方法，对大规模问题更稳定）或 MOSEK 往往能解决问题。此外，将问题转化为等价的锥形式（如将 范数约束转化为 SOCP）能显著提高求解效率。
非线性规划（Nonlinear Programming, NLP）指目标函数或约束条件中存在非线性函数（且不一定是凸的）的最优化问题。其复杂度远高于凸优化。
| 特性 | 说明 |
|---|---|
| 多极值 | 存在多个局部最优解 |
| 鞍点 | 梯度为零但既非极大也非极小 |
| 不可微 | 目标函数可能非光滑 |
| 病态条件 | Hessian 矩阵特征值差异大 |
梯度下降法（Gradient Descent）
牛顿法（Newton's Method）
拟牛顿法（Quasi-Newton）
共轭梯度法（Conjugate Gradient）
序列二次规划（SQP）
罚函数法（Penalty Method）
增广拉格朗日法（Augmented Lagrangian）
scipy.optimize.minimize 集成了多种算法（Nelder-Mead、BFGS、L-BFGS-B、SLSQP、trust-constr）Hugo 踩坑记录：
- 使用
scipy.optimize.minimize时，不要贪心选择 method='trust-constr' 做所有问题。它对大规模约束问题非常慢，并且容易在约束边界处震荡。对于约束较少的问题，SLSQP 是更稳定的选择。- 梯度的数值精度：当手动提供梯度但 Hessian 未提供时，数值 Hessian 近似可能引入误差。建议总是做一次有限差分梯度校验（
scipy.optimize.check_grad）。- 某些非线性约束会导致可行域为空，但求解器可能不会显式告诉你，而是返回一个不可行点。务必检查
result.success和约束违反量。
变分法（Calculus of Variations）是最优化的函数空间推广：决策变量是函数而非有限维向量。它研究如何找到使泛函 取极值的函数 。
泛函极值的必要条件由 Euler–Lagrange 方程给出：
这个方程是变分法的核心，也是物理中最小作用量原理的数学基础。
最优控制是最优化的一个重要分支，决策的是随时间变化的控制信号 ，使得系统状态 按动力学演化并最小化某个性能指标。
Pontryagin 最大值原理给出了最优控制的必要条件：
其中 是哈密顿函数， 是协态变量。
动态规划（Dynamic Programming）和 Bellman 方程 是另一条路径。在连续时间下的 Hamilton-Jacobi-Bellman（HJB）方程为：
HJB 方程是充分条件，但通常难以解析求解（高维 PDE）。
Hugo 的经验：实际工程中最优控制问题大多用直接法求解——打靶法对初始猜测极其敏感，而且协态的初值选择是门玄学。直接配点法配合 IPOPT 或 SNOPT 做 NLP 求解是业界标配。CasADi 是一个非常好用的工具，它支持自动微分和直接法最优控制建模。
当目标函数存在多个局部极值时，全局优化需要找到全局最优解。这是一类更难的问题。
模拟退火（Simulated Annealing）
遗传算法（Genetic Algorithm）
粒子群优化（PSO）
贝叶斯优化（Bayesian Optimization）
分支定界法（Branch and Bound）
Hugo 的看法：全局优化不是万能的。很多人一上来就丢给遗传算法，实际上如果问题规模中等且结构良好，用凸松弛 + 分支定界比纯启发式方法有更好的理论保证。贝叶斯优化在深度学习超参数搜索中很流行，但对于低维度（<20维）效果最好，高维时高斯过程核函数的选择很关键。
[ 最优化 ]
/ \
[凸] [非凸]
/ \ / \
[LP] [SOCP] [NLP] [全局优化]
/ \ | | |
[单纯形][内点] [锥规划] [SQP] [GA/SA/PSO]
机器学习本质上是大量的优化问题：
| 问题类型 | 损失函数 | 优化方法 |
|---|---|---|
| 线性回归 | MSE（凸二次） | 闭式解 / SGD |
| 岭回归 | MSE + 正则 | 闭式解 |
| LASSO | MSE + 正则 | 坐标下降 / FISTA |
| 逻辑回归 | Log Loss（凸） | IRLS / SGD |
| 支持向量机 | Hinge Loss（凸） | SMO / QP |
| 神经网络 | 高度非凸 | SGD / Adam / RMSProp |
| 决策树 | 信息增益（非平滑） | 贪心分裂 |
深度学习中，SGD 和 Adam 是事实标准。虽然损失函数高度非凸，但实践中 SGD 总能找到泛化能力很好的解，这至今仍是一个开放的理论问题。
在工程应用中，我的经验是：
- 不要浪费时间去实现自己的 LP/QP 求解器——这是 PhD 论文级别的工作。直接用 Gurobi 或 HiGHS。
- 检查对偶间隙——如果求解器支持，务必检查对偶信息。对偶间隙大说明问题可能是非凸的或者求解还没收敛。
- 敏感性分析很重要——不仅有最优解，还要知道解对参数变化的敏感度。对偶变量（影子价格）提供了这些信息。
- 鲁棒优化——当模型参数本身有不确定性时，考虑用鲁棒优化（Robust Optimization）或分布鲁棒优化（Distributionally Robust Optimization）来得到对数据误差不敏感的解。
- 矩阵结构利用——如果 Hessian 或约束矩阵是稀疏的、分块对角的、或带结构的（如 Toeplitz），选择能利用这些结构的求解器可以快几个数量级。
| 工具 | 类型 | 适用场景 |
|---|---|---|
| Gurobi | 商用求解器 | LP/QP/MIP/MIQP，性能最强 |
| HiGHS | 开源求解器 | LP/QP/MIP，性能接近商用 |
| CVXPY | 建模语言 | 凸优化快速原型 |
| CasADi | NLP + 最优控制 | 最优控制、动力学优化 |
| Optuna | 超参数调优 | 机器学习超参数搜索 |
| SciPy optimize | 综合工具包 | Python 环境下的通用优化 |
此页面为数学知识库的一部分。