简单百科
最优化

最优化

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

17世纪，英国科学家艾萨克·牛顿（Isaac Newton）创立微积分的时代，就已提出极值问题，1847年，法国数学家奥古斯丁-路易·柯西（Cauchy）研究了函数值沿什么方向下降最快的问题，提出了最速下降法。20世纪40年代后，随着生产和科学研究突飞猛进地发展，最优化理论和算法得以迅速发展，并不断完善，逐步成为一门系统的学科。20世纪50年代以后，人们从一些自然现象和规律中受到启发，提出了许多求解复杂优化问题的新方法，例如模拟退火算法、遗传算法及蚁群系统启发式算法等。近半个世纪以来，最优化得到了充分研究，在理论上取得了非常重要的研究成果，在实际应用中正在发挥越来越大的作用，如计算机科学、工程学、运筹学、经济学等，并且最优化已经成为发展迅速、内容丰富、应用广泛的活跃学科。

最优化常用算法有优化算法、迭代法、启发式算法，主要子领域包括多目标规划及整数规划等。其中常见优化问题有连续和离散优化问题、无约束和约束优化问题等。

定义

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

最优化问题的一般形式为：。

其中是中的集合，是上的实值函数。是英文（极小化）的缩写。称为目标函数，称为可行域，可行域中的点称为可行点。

最优化在不同的意义下，有不同的标准，它的范围广泛，无法在短时间内系统又全面地介绍，这里来介绍最优化的一个重要分支—数学规划。数学规划指的是对个变量对单目标（或多目标）函数求极小（或极大）。

其数学表达式为：

，

这里表示求极小，意思是受限制于···，是维向量，其分量为。在问题中称为目标函数，称为约束条件。若求极大，可以将目标函数写成，若不等式约束可以写成。

在问题中，若均是线性函数，则得到的规划称为线性规划，其一般表达式为：

，

。

在问题中，中之一是非线性函数，则称为非线性规划，若去掉问题的约束条件，则得到：

，

称为无约束最优化问题，因此也称问题为约束最优化问题。

简史

17世纪，英国科学家艾萨克·牛顿（Isaac Newton）创立微积分的时代，就已提出极值问题，后来约瑟夫·拉格朗日（Lagrange）研究一个函数在一组等式约束条件下的极值问题时提出了乘数法。1847年，法国数学家奥古斯丁-路易·柯西（Cauchy）研究了函数值沿什么方向下降最快的问题，提出了最速下降法，这也是最优化研究历史上的第一种数值方法。1939年，苏联数学家康托洛维奇（Л.В.Канторович）提出了解决下料问题和运输问题这两种线性规划的求解方法。

人们关于最优化问题的研究工作，随着历史的发展不断深入。20世纪40年代以来，生产和科学研究突飞猛进地发展，特别是电子计算机日益广泛应用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具，最优化理论和算法才得以迅速发展，并不断完善，逐步成为一门系统的学科。 1947年，美国科学家丹齐克（Dantzig）提出了求解线性规划问题的单纯形法，为线性规划的理论和算法奠定了基础。 1951年，由托马斯·库恩（Kuhn）和塔克（Tucker）完成了非线性规划的理论基础性工作。20世纪50年代以后，人们从一些自然现象和规律中受到启发，提出了许多求解复杂优化问题的新方法，例如模拟退火算法，遗传算法及蚁群系统启发式算法等。近半个世纪以来，最优化得到了充分研究，在理论上取得了非常重要的研究成果，在实际应用中正在发挥越来越大的作用，已经成为发展迅速、内容丰富、应用广泛的活跃的学科。

优化问题分类

连续和离散优化问题

根据变量是连续还是离散，最优化问题可以分为连续和离散优化问题两大类。

连续优化问题

连续优化问题是指决策变量所在的可行集合是连续的，比如平面、区间等。如稀疏优化问题的约束集合就是连续的。在连续优化问题中，基于决策变量取值空间以及约束和目标函数的连续性，可以从一个点处目标和约束函数的取值来估计该点可行领域内的取值情况，进一步地，可以根据邻域内的取值信息来判断该点是否最优。离散优化问题则不具备这个性质，因为决策变量是在离散集合上取值。因此，在实际中往往比连续优化问题更难求解。

离散优化问题

离散优化问题是指决策变量能在离散集合上取值，比如离散点集、整数集等。常见的离散优化问题有整数规划，其对应的决策变量的取值范围是整数集合。实际中的离散优化问题往往可以转化为一系列连续优化问题来进行求解，比如线性整数规划问题中著名的分支定界方法，就是松弛成一系列线性规划问题来进行求解。

无约束和约束优化问题

最优化问题的另外一个重要的分类标准是约束是否存在。无约束优化问题的决策变量没有约束条件限制，即可行集合。相对地，约束优化问题是指带有约束条件的问题。

约束优化问题

约束非线性优化问题是指：

其中，及都是定义在上的实值连续函数，且至少有一个是非线性的。是一正整数，是介于和之间的整数。被称为目标函数，被称为约束函数。如果，则问题被称为等式约束优化问题；如果都是线性函数，则称是一个线性约束优化问题；一个线性约束优化问题，如果目标函数是二次函数，则被称为二次规划问题。

无约束优化问题

无约束优化问题对应于在欧几里得空间中求解一个函数的最小值点。在某种程度上，约束优化问题就是无约束优化问题，很多约束优化问题的求解也是转化为一系列的无约束优化问题来做，常见方式有增广拉格朗日函数法、罚函数法等。

随机和确定性优化问题

随机优化问题

随机优化问题是指目标或者约束函数中涉及随机变量而带有不确定性的问题。随机优化问题中总是包含一些未知的参数。随机优化问题在机器学习、深度学习以及强化学习中有着重要应用，其优化问题的目标函数是关于一个未知参数的期望的形式。因为参数的未知性，实际中常用的方法是通过足够多的样本来逼近目标函数，得到一个新的有限和形式的目标函数。

随机优化问题可以表示成以下形式：

。

确定性优化问题

确定性优化问题中目标和约束函数都是确定的，计算步骤相比较随机性优化算法来说比较复杂。

线性和非线性规划问题

线性规划是指问题中目标函数和约束函数都是线性的。当目标函数和约束函数至少有一个是非线性的，那么对应的优化问题的称为非线性规划问题。

线性规划

线性规划问题是求一组非负变量，它们在满足一组线性等式或不等式约束的条件下，使一个线性函数达到极小或极大。即：

为了便于研究和求解，便把各种形式的线性规划问题化为线性规划的标准形式，称下列形式的线性规划问题为线性规划的标准型：

其中，为已知常数，一般，称条件为非负约束，称为成本系数或价格系数。

非线性规划

非线性规划是最优化的一个重要分支，其形式为：

即在维空间的一个子集中求函数的极小值和极小点值。如果，则以上问题被称为无约束非线性规划问题，如果是的真子集，则以上问题被称为约束非线性规划问题。

凸和非凸优化问题

凸优化问题是指最小化问题中的目标函数和可行域分别是凸函数和凸集。如果其中有一个或者两者都不是凸的，那么相应的最小化问题是非凸优化问题。因为凸优化问题的任何局部最优解都是全局最优解，其相应的算法设计以及理论分析相对非凸优化问题简单很多。

凸优化

考虑非线性规划问题：

记的约束集为：

。

如果问题的约束集是凸集，目标函数是上的凸函数，则叫做是非线性凸规划或简称凸规划。

非凸优化

在实际问题的建模中，经常更倾向于得到一个凸优化模型。另外，判断一个问题是否是凸问题也很重要。比如，给定一个非凸优化问题，一种方法是将其转化为一系列凸优化子问题来求解。此时需要清楚原非凸问题中的哪个或哪些函数导致了非凸性，之后考虑的是如何用凸优化模型来逼近原问题。

优化问题常用特殊符号

函数极值

无约束极值

或。

这里是定义在维空间上的可微函数。

约束极值

或；

满足于，。

临界点与极值的分类

存在性

优化问题

。

考虑一个适当且闭的函数，假设下面三个条件中任意一个成立：

（1）是有界的；

（2）存在一个常数使得下水平集是非空且有界的；

（3）是强制的，即对于任一满足的点列，都有，那么问题的最小值点集是非空且紧的。

最优性条件

一阶最优性条件

一阶必要条件

假设在全空间可微。如果是一个局部极小点，那么。

二阶最优性条件

二阶必要条件

如果是的一个局部极小点，那么。

二阶充分条件

如果在点处有，成立，那么为的一个局部极小点。

理论

主要理论

多目标规划

在一个具体的优化问题中，有的指标可能要求最小化，有的则要求最大化；有的约束可能是“”，有的则可能是“”。但是，总可以通过乘以，使它们化成下面多目标规划的标准形式：

；

，

其中，，称为决策向量，所在的空间称为决策空间；称为目标函数，所在的空间称为目标空间，称为约束函数。多目标规划问题亦称为向量最优化问题。多目标规划问题实际上是将决策空间的一个区域映射到目标空间的一个区域，所以问题涉及到两个集合概念：

，称为的可行域；

，称为值域。

整数规划

不同于线性规划，整数规划要求优化变量必须取整数值，而不能是分数值。一般形式如下：

其中，是给定的矩阵和向量，是整数集合。如果只要求部分是整数，该问题被称为混合整数规划问题。

主要算法

优化算法

单纯形法

单纯形法同其他的数值求解方法一样是一种迭代法，它根据线性规划问题的特点在问题可行域的顶点中逐步确定问题的最优解，在每一个是基本可行解的迭代点，如果它不是最优的，单纯形法从与该顶点相连结的边中确定一个使目标函数值下降的边，沿该边移动可以确定一个与该顶点相邻且目标函数又优于该顶点的新顶点（新的基本可行解）。由于可行域的顶点数是有限的，如果每一次的移动都能使目标函数值下降，则经过有限次的移动方法必终止于问题的一个最优顶点。

考察线性规划问题：

。

设为一个基本可行解，单纯形方法首先检验它的最优性。如果它不是最优的，确定与该顶点相连的一条使目标函数下降的边；接下来确定沿这个边移动多远可以到达另一个更优的相邻顶点，也就是得出一个新的基本可行解。

启发式算法

模拟退火算法

模拟退火算法是一种基于迭代求解策略的随机寻优算法，其算法思想来源于物理中的固体降温退火过程与数学中的许多组合优化问题之间的相似性。物理中固体在退火过程中，主要有三大物理过程：

升温过程

当固体物质温度升高时，物质内部粒子能量升高，粒子的运动增强，当温度升高到一定程度，内部粒子运动脱离其平衡位置，固体就会熔化成为液体状态。

等温过程

当物质温度降低到恰好与周围环境相同时，物质将暂时停止向周围环境散发热量。此时，物质温度保持不变，但是物质内部的粒子自由能会逐渐降低，当物质内部粒子的自由能降低到当前物质温度所蕴含的能量能够维持的最低状态时，物质会进入平衡态。物质温度保持不变，但内部粒子自由能减少到达到平衡态的整个过程就是等温过程。

冷却过程

物质温度降低到一定程度后，物质内部的粒子能量逐渐减少，粒子运动逐渐减弱，直至所有粒子运动渐趋稳定。此时，物质内部系统能量下降到当前环境中的最低值，物质内部粒子将重新进入平衡状态。表现在外就是物质重新凝结成为固态，此时的物质内部能量比熔化前的固体状态更低。

遗传算法

遗传算法算法是根据大自然中生物体进化规律而设计提出的，该算法通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。

选择

从群体中选择优胜个体、淘汰劣质个体的操作叫选择。选择映射有时又称为再生算子。选择的目的是把优化的个体（或解）直接遗传到下一代或通过联会交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子包括适应度比例方法、随机遍历抽样法、局部选择法。

交叉

在自然界生物进化过程中起核心作用的是生物遗传基因的重组。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

变异

变异算法的基本内容是对群体中的个体串的某些基因座上的基因值作变动。变异算法的运算过程大体如下：

1.将待解决问题的约束与优化目标等参数编码到染色体中，形成问题参数与染色体的对应关系，构成染色体编码空间；

2.根据问题的参数设定恰当的适应度函数；

3.设置进化过程中的相关操作映射，主要有交叉算子、变异算子、选择算子等；

4.根据问题确定合适的遗传算法参数，包含种群规模、交叉概率、变异概率等参数；

5.生成初始种群；

6.对种群中的所有个体进行适应度函数值计算；

7.判断种群是否满足算法终止条件，若满足条件则输出该种群中适应度值最高的个体；如果不满足算法终止条件，则继续后续的操作过程；

8.对种群进行选择、交叉、变异运算，产生新的种群；

9.重复步骤6，7，8产生种群，直至满足算法终止条件。

迭代法

最速下降法

最速下降法以负梯度方向作为极小化算法的下降方向，又称梯度法，是无约束最优化中最简单的方法。设函数在附近连续可微，且，由展式：

。

可知，若记，则满足的方向是下降方向。当取定后，的值越小，即的值越大，函数下降得越快。由不等式：，

故当且仅当时，最小，从而称是最速下降方向。最速下降法的迭代格式为：。

这个方法的计算步骤如下：

1.给出；

2.计算；如果，则停止；

3.由一维搜索求步长因子，使得；

4.计算；

5.，转步骤。

牛顿法

牛顿法的基本思想是利用目标函数在迭代点处的二次展开作为模型函数，并利用这个二次模型函数的极小点序列去逼近目标函数的极小点。

设二次连续可微，，矩阵正定。在附近用二次展开近似，

，

其中为的二次近似。将上式右边极小化，即令：，

得：，

这就是牛顿法迭代公式，相应的算法称为牛顿法。

拟牛顿法

考虑目标函数在当前点处的二次模型：，

其中，是对称正定矩阵，是近似，它将在每次迭代中进行校正，极小化这个二次模型得到：，

从而新的迭代点为：，

其中，是线性搜索步长因子，上述迭代称为拟牛顿迭代，他与牛顿迭代的主要区别在于中，用近似代替了艾萨克·牛顿迭代中的矩阵。

设：在开集上二次连续可微，在附近的二次近似为：

，

对上式两边求导，有：。

令，得：。

令：，

成为。

显然，如果是正定二次函数，上述关系式精确成立。要求在拟牛顿法中构造出来的近似满足这种关系，从而得到：。

上式称为拟牛顿条件或拟牛顿方程。一般的拟牛顿算法如下：

1.给出初始点；

2.如果，停止；

3.解得搜索方向；（或计算）；

4.由线性搜索求步长因子，并令；

5.校正产生（或校正产生），使得拟牛顿条件成立；

6.，转步骤。

共轭梯度法

共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合。因此，存储量少，计算方便。

记：，

左乘，并使得，得。（公式）

另外常用的三个公式为：

，（公式）

。（公式）

对于正定县二次函数，若采用精确线性搜索，以上几个关于的共轭梯度公式等价。但在实际计算中，公式和公式最常用。由于强线性搜索准则并不保证方法的方向是下降的，如果定义参数：，

其中由定义，则方法具有下降性质，这样的方法称为方法。

注意到对于正定二次函数：，

其中是方程组的残量，以及

，

给出如下关于正定县二次函数极小化的共轭梯度法算法：

1.初始步：给出，计算，令；

2.如果，停止；

3.计算

，

。

4.令，转步骤。

二次罚函数法

罚函数法是一类不可行点的方法，对初始点的选取没有可行性的限制，对不可行约束采用不同的惩罚函数，就形成不同的罚函数方法。其中最简单也经常采用的是二次罚函数方法，二次罚函数由目标函数加上惩罚项组成，其中惩罚项是约束违反函数的平方。

对于等式约束问题：

，

二次罚函数定义为：

这里是罚参数，当趋于零时，如果约束不可行，即，则违反约束的惩罚项剧烈地增大。可以证明：当时罚函数的极小点就是原问题的极小点。因为惩罚项是二次的，所以光滑可微，这样可以使用无约束优化技术来求解得罚函数的近似极小点。二次罚函数法的算法为：

1.给定，允许参数值，初始点；

2.从开始，极小化得近似极小点；

3.当时，终止，得近似解；否则，选择新的罚参数，令，转步骤。

内点障碍函数法

内点障碍函数法通过在目标函数上引入一个关于约束的障碍项，当迭代点由可行域的内部接近可行域的边界时，障碍项将趋于无穷大来迫使迭代点返回可行域的内部，从而保持迭代点的严格可行性。

考虑不等式约束最优化问题：

定义严格可行内点区域为：，

并假设是非空的。对考虑不等式约束最优化问题，障碍函数具有如下性质：

1.在外部的值或者无定义或者是无穷的；

2.在内部都是连续可微的；

3.当趋于的边界，其值趋于。

常用的障碍函数是对数障碍函数：，

分数障碍罚函数：，

其中为自然对数，为障碍参数。

应用

物流运输

最优化问题和方法被广泛应用于物流运输中。电子商务时代下的商业物流运输路径选择是一个极其重要的问题，如何选择最优的物流运输路径，为企业提供最优质、最快捷、最经济的物流服务是所有电商企业所面临的难题。最优化商业物流运输路径选择的研究具有很大的实际应用价值，可以帮助物流企业提高运输效率，降低物流成本，并且实现更加客户化的配送服务。随着计算机技术的不断发展，最优化商业物流运输路径的研究也实现了更好的突破和发展。

土木工程

最优化问题在工程造价中主要用于成本控制方面。随着建筑行业的发展，工程造价管理越来越受到重视。建筑工程造价是指在完成建筑项目时所需要的全部费用，包括各种材料、劳动力、设备和管理费用等。在建筑项目中，造价管理是一个非常关键的工作环节，直接影响项目的进度和经济效益，实现建筑工程实现成本的最优化对于建筑工程造价的动态管理与成本控制具有重要的理论价值和实际意义。

电气工程

随着新能源行业发展得越来越快速，新能源并网规模不断扩大，但是电力系统消纳能力不足，导致资源过剩。所以，寻求更优化的能源配比是非常重要的。如在储能运行方面，可以通过建立最优化的模型来保证成本、减少电网的碳排放并提高太阳能光伏的消纳能力。

金融学

组合优化在金融投资方面应用也非常广泛，如，很多投资者会用此选择合适的股票组合，达到风险最小化和收益最大化。晋中投资中组合优化研究主要是从投资收益最大化或者投资风险最小化视角展开，达到实现收益最大化，且同时满足风险最小化的目的。

人工智能

最优化在人工智能方面应用较为广泛，如在空中机器人飞行轨迹方面。基于传统最优化方法得到的过渡轨迹在尾座式无人机实际飞行过程中可行性低和鲁棒性差的问题，优化过渡轨迹可以提高其可行性。以一种双发尾座式无人机为研究对象，通过分析机翼不同区域之间的迎角差异，构建出非线性动力学模型。基于倾转旋翼机过渡走廊研究思路，设计出一种针对尾座式无人机的过渡走廊，并通过限制爬升速率和俯仰角速率来提高过渡走廊的可行性。通过分析模型误差对过渡走廊的影响，得到一条具有最大安全裕度的目标过渡轨迹。仿真和实际飞行结果表明，所提出的过渡方法能够引导飞机快速安全地完成过渡，避免了出现高度增加过大、过渡时间过长以及作动器饱和等不利情况。

定义

简史

相关概念

最优解

凸集

凸函数

共轭函数

次梯度