[科普中国]-局部最优

基本概念最优化问题

最优化（Optimization），就是在复杂环境中遇到的许多可能的决策中，挑选“最好”的决策的科学1。

例如，工程设计中，怎样选择设计参数，使得设计方案能以尽量低的成本预算满足设计要求；资源分配中，怎样分配有限资源，使得在满足各方面需求的情况下最大化经济效益；生产安排中，怎样选择生产方案能在产量、质量和利润中找到符合要求的平衡点；还有在城市规划、军事指挥、生活安排等方方面面都存在着最优化问题2。

全局最优针对一定条件/环境下的一个问题/目标，若一项决策和所有解决该问题的决策相比是最优的，就可以被称为全局最优。

将上述定义用数学公式表示为：在无限制环境集合R内，假设限制条件/环境为集合D（D包含于R），问题代价或目标函数为f(x)，其中x指决策，那么全局最优就是指决策满足

或

其中对目标函数去最大值还是最小值根据具体问题和要求而确定。

局部最优和全局最优不同，局部最优不要求在所有决策中是最好的。

针对一定条件/环境下的一个问题/目标，若一项决策和部分解决该问题的决策相比是最优的，就可以被称为局部最优。

将上述定义用数学公式表示为：按照上一节的定义，对于D内的一个子集，局部最优就是指决策满足

或

可以看到，局部最优不一定是全局最优，全局最优一定是局部最优。

最优化问题最优化问题类型根据不同的划分角度，最优化问题可以划分为不同的类型，对几个常用的类别举例如下。

针对是否有约束条件D，可以划分为无约束最优化问题和有约束最优化问题；

针对目标数，可以划分为单目标优化问题和多目标优化问题；

针对约束条件的性质，可以对规划问题划分为线性规划和（曲线）非线性规划。

最优化问题解法对不同的最优化问题，有不同的决策方法和算法。

对于无约束条件的最优化问题，常用的方法有牛顿法、共轭方向法、梯度求解法等；

对于有约束条件的最优化问题，由于一般的问题可以用线性方程表示（或者说约束条件是线性的），所以最常见的解决算法是线性规划；对于一些复杂的问题，可能会用到非线性方程，此时就需要使用非线性规划3。线性规划有单纯形法、对偶解法、修正的单纯形法等具体算法；非线性规划对于只含等式、含不等式、凸优化、多目标优化等不同情况也有不同的解法。

局部最优局部最优的产生一般的启发式算法、贪婪算法或局部算法都很容易产生局部最优，或者说根本无法查证产生的最优解是否是全局的，或者只是局部的。这是因为对于大型系统或复杂的问题，一般的算法都着眼于从局部展开求解，以减少计算量和算法复杂度。

局部最优的意义对于优化问题，尤其是最优化问题，总是希望找到全局最优的解或策略，但是当问题的复杂度过于高，要考虑的因素和处理的信息量过多的时候，我们往往会倾向于接受局部最优解，因为局部最优解的质量不一定都是差的。尤其是当我们有确定的评判标准标明得出的解是可以接受的话，通常会接收局部最优的结果。这样，从成本、效率等多方面考虑，才是实际工程中会采取的策略。

局部最优的避免在部分工程领域，受限于时间和成本，对局部最优和全局最优可能不会进行严格的检查，但是有的情况下式要求得到全局最优的，这是就需要避免产生仅仅是局部最优的结果。

对局部最优的避免有两个根本方法4：

深入研究问题的机理，对问题的机理研究的越透彻，就能更准确的找到全局最优，或划定全局最优可能的区域；

随机搜索，对机理不明的问题，解的搜索越随机陷入局部最优的可能性就越小。

对于已经陷入局部最优，或怀疑陷入局部最优的情况，一般是采取“跳出”或“重启”两种手段，也就是在当前解的基础上向其他方向搜索，或者无视当前解并在新的区域重新搜索。