当前位置：首页 > news >正文

最优化理论综述

news 2026/3/27 5:43:03

最优化理论是数学中的一个重要分支，主要研究如何在给定约束下找到目标函数的最优解（最小值或最大值）。它广泛应用于工程、经济学、机器学习等领域。以下从数学基础、优化建模、线性规划方法等方面详细总结文档内容，结构丰富，涵盖关键概念、定理和算法。文档中涉及多个图表，我会在相关描述处嵌入图片标签以增强理解。

一、数学基础

最优化理论依赖于坚实的数学工具，包括范数、导数和凸分析。这些概念是理解优化问题性质和算法的基础。

范数：用于度量向量或矩阵的大小。常见范数包括欧几里得范数（L2范数）、曼哈顿范数（L1范数）和无穷范数（L∞范数）。例如，向量的L2范数定义为 \(|x|_2 = \sqrt{\sum x_i^2}\)，矩阵的谱范数为最大奇异值。范数在优化中用于定义距离和误差度量。
导数：对于函数优化，导数（梯度、海瑟矩阵）是关键。梯度指向函数增长最快的方向，海瑟矩阵描述曲率。对于矩阵变量函数，导数计算涉及偏导数和链式法则。自动微分（如反向传播）是计算导数的有效技术，广泛用于神经网络训练。
凸分析：凸集和凸函数是优化理论的核心。凸集满足任意两点连线仍在集内，凸函数满足Jensen不等式（即函数值在两点连线下方）。凸性保证局部极小即全局极小，简化优化。例如，二次函数 \(f(x) = x^T A x + b^T x\) 是凸的当且仅当A半正定。
- 凸函数具有次梯度概念，用于不可微函数。次梯度是凸函数在某点的线性下界。闭函数（下方图闭集）与下半连续函数等价，保证解的存在性。
- 保凸运算包括非负加权和、仿射复合、取上确界等，便于构造复杂凸函数。

二、优化建模

优化建模将实际问题转化为数学形式，涉及目标函数设计、约束处理和应用实例。

目标函数设计：
- 最小二乘法：用于拟合数据，最小化误差平方和，如线性回归 \(\min |Ax - b|_2^2\)。当误差为高斯噪声时，最小二乘解等价于最大似然估计。
- 正则化：防止过拟合，如Tikhonov正则化（岭回归）添加L2范数罚项，LASSO添加L1范数罚项促进稀疏性。分组LASSO和稀疏分组LASSO处理结构化稀疏问题。
- 最大似然估计：基于概率模型估计参数，如逻辑回归中最大化似然函数。
- 损失函数：在机器学习中，常用交叉熵、Hinge损失等，结合正则项控制模型复杂度。
约束处理：
- 等价转换：如将不等式约束通过松弛变量转为等式，或使用上方图将无约束问题转为约束问题。
- 松弛技巧：将难处理的约束（如整数约束）放宽为连续约束，但需注意松弛后问题与原问题的关系。
应用模型：
- 回归分析：线性回归模型 \(b = Ax + \varepsilon\)，当 \(\varepsilon\) 为高斯噪声时，最小二乘最优；其他噪声假设导致L1范数损失等。正则化版本如岭回归、LASSO用于特征选择。
- 逻辑回归：用于二分类，模型概率为Sigmoid函数，最大似然估计化为最小化对数损失函数，常加L2或L1正则化。
- 支持向量机（SVM）：寻找最大间隔超平面。线性SVM转化为二次规划问题；软间隔SVM引入松弛变量处理误分类，等价于Hinge损失最小化。

三、线性规划专题

线性规划是优化的重要分支，研究线性目标函数和线性约束下的极值问题。

标准形式：一般形式为 \(\min c^T x\)，s.t. \(Ax = b, x \geq 0\)。通过引入松弛变量或变量替换，可将不等式约束化为标准形式。
基本性质：
- 可行域是凸多面体，最优解若存在必在极点（基本可行解）达到。基本可行解对应约束矩阵的基，非基变量为零。
- 单纯形法从基本可行解出发，通过换基迭代改进解。进基变量选最大判别数（检验数）列，离基变量由最小比值规则确定。当所有判别数非正时达到最优。
单纯形法实现：
- 计算步骤：初始化基矩阵，计算判别数，迭代换基。使用单纯形表简化计算，主元消去实现基变换。
- 退化处理：当基本可行解有零分量时可能循环，可通过扰动规则或字典序法避免。
- 两阶段法：第一阶段引入人工变量构造辅助问题，最小化人工变量和，若最优值零则得初始可行解；第二阶段解原问题。大M法在目标函数加罚项（大M乘人工变量），驱动人工变量离基。
- 例子：如运输问题、食谱问题等，演示建模和求解过程。