最优化算法概述与分类

一、概念

最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题，比如每个企业和个人都要考虑的一个问题“在一定成本下，如何使利润最大化”等。

二、分类

1、公式求解

给出一个最优化问题精确的公式解，也称为解析解，其算法计算复杂性一般很大，只适合于求解小规模问题。

（1）线性规划的求解方法

线性规划（Linear programming，LP）是运筹学的一个重要分支，它起源于工业生产组织管理的决策问题，在数学上用来确定多变量线性函数在满足线性约束条件下的最优值。线性规划模型通常由要素——决策变量、目标函数和约束条件构成。一般来讲，决策变量是决策者为了达到预定目标而要控制的那些量，问题的求解就是找出决策变量的最终取值；目标函数是决策变量的线性函数，描述决策变量和预定目标之间的关系；约束条件是决策者在现实世界中所受到的限制，或者说决策变量在这些限制范围之内才有意义。
例：单纯形法、内点法

（2）非线性规划的求解方法

如果目标函数或约束条件中包含非线性函数，就称这种问题为非线性规划。一般来说，求解非线性规划要比线性规划困难得多，而且不像线性规划有单纯形法这样通用的方法，各个方法都有自己特定的适用范围。
例：拉格朗日乘数法

2、数值优化

在大多数情况下很难得到目标函数的公式，这时候就需要用数值计算方法近似求解得到最优点。从任一解出发，对其领域的不断搜索和当前解的替换来实现优化。根据搜索行为，它又可分为局部搜索法和启发搜索法。

（1）局部搜索法

以局部优化策略在当前解的邻域中贪婪搜索。
例：随机游走、梯度下降法、牛顿法等

（2）启发搜索法

利用一些指导规则来指导整个解空间中优良解的探索。
例：模拟退火算法、遗传算法、蚁群算法等

3、其他

其他一些求解思想，如分治法，动态规划等。