最优化

方程$z=f(x,\ y)=-(x^{2}+y^{2})+4$的曲面图像。最大值为$(x,\ y,\ z)=(0,\ 0,\ 4)$，由蓝点标记。

西米奥内斯库函数的Nelder-Mead极小值搜索。单纯形顶点按值排序，1有最小的（$f(x)$最佳）值。

最优化指从一组可选择的方案中，根据一定标准选择最佳方案的过程，往往要在特定情况下最大化或最小化某一特定函数或变量。一般分为离散优化、连续优化两个子领域。优化问题出现在计算机科学、工程学到运筹学、经济学等所有定量学科中，几百年来求解方法的发展一直受到数学界的关注。 在更一般的方法中，优化问题往往要系统地选择输入值、计算函数值以最大化或最小化某实函数。将优化理论与技术推广到其他的表述，构成了应用数学的一个分支。更一般地说，优化包括在给定定义域（或输入）的情形下，找到某目标函数的“最佳可达值”。

优化问题

主条目：优化问题

优化问题可分为两类，取决于变量是连续还是离散：

• 离散变量的优化问题称作离散优化，当中的整数、排列或图之类对象必须属于可数集。
• 连续变量的优化问题称作连续优化，当中最优自变量要属于连续集。这类问题可以包括约束优化与多峰问题。

优化问题可用以下方式表示：

已知： 函数$f:\ A\to \mathbb {R}$从某集合A映射到实数

求： 元素$x_{0}\in A$，使$\forall x\in A,\ f_{x_{0}}\leq f(x)$（“最小化”），或使$x\in A,\ f_{x_{0}}\geq f(x)$（“最大化”）。

这样表述后，称作优化问题或数学规划问题。很多现实问题与理论问题都可用这个一般框架建模。

由于下式成立：

$f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} ),$

只需解最小化问题。只考虑最大化问题的相反观点是同理的。

物理学领域，使用这种技术提出的问题可称“能量最小化”，将函数f值视为所建模系统的能量。机器学习中，总要用损失函数持续评估模型的质量，损失函数获取极小值意味着一组可能的最优参数，同时具有最优（最小）的误差。

A通常是欧氏空间$\mathbb {R} ^{n}$的子集，一般要求A的成员需满足一组约束（等式或不等式）。f的定义域A称作搜索空间或选择集，A的元素称作候选解或可行解。

函数f有多种叫法，常见的有目标函数、判别函数、损失函数、成本函数（最小化）、效率函数、适应度函数（最大化），某些领域还有能量函数、能量泛函等等。使得目标函数取最值（取决于问题）的可行解就是最优解。

数学中，传统优化问题通常用最小化形式表示。

极值$\mathbf {x} ^{\ast }$是局部的，定义为$\exists \delta >0$，满足一定条件。例如，极小值要满足

$\forall \mathbf {x} \in A\;{\text{where}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,f(\mathbf {x} ^{\ast })\leq f(\mathbf {x} )$

这就是说，在$\mathbf {x} ^{*}$周围的一些闭球上，所有的函数值都大于或者等于在该点的函数值。

极小值至少于附近的任何元素一样好，最小值则至少与每个可行解一样好。一般来说，除非目标函数是凸函数，否则会存在多个极小值。凸优化问题中，若有位于可行集内（不位于边缘）的极小值，则它也是最小值；而非凸优化问题可能有多个极小值。

非凸问题所用的大量算法（包括大多数商业求解器）都无法区分局部最优解与全局最优解，而是将前者视作原问题的实际解。全局优化是应用数学与数值分析的一个分支，主要研究能在有限时间内收敛到非凸问题实际最优解的确定性算法。

符号

优化问题常用特殊符号表示，如下：

函数最值

$\min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)$

这是求，从实数集$\mathbb {R}$中选择x时，目标函数$x^{2}+1$的最小值。此问最小值为1，出现在$x=0$处。

相似地，

$\max _{x\in \mathbb {R} }\;2x$

是求目标函数$2x$的最大值，其中x是任意实数。由于目标函数无界，所以不存在最大值，答案是“无穷大”或“未定义”。

最佳输入

主条目：极值点

${\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,$

或等价的

${\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].$

这是求参数x在区间$(-\infty ,\ -1]$时，能使目标函数$x^{2}+1$取最值的值。此问题的答案是$x=-1$，因为$x=0$不可行，不属于可行集。

相似地，

${\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,$

或等价的

${\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,$

表示使目标函数$x\cos y$取最大值的$\{x,\ y\}$对，且x要满足约束：位于区间$[-5,\ 5]$内。此问题的答案是$\{5,\ 2k\pi \}$与$\{-5,\ (2k+1)\pi \}$，其中k的范围是所有整数。

算符$\operatorname {arg\,min} ,\ \operatorname {arg\,max}$有时也作${\text{argmin}},\ {\text{argmax}}$，分别代表最小值点与最大值点。

历史

皮埃尔·德·费马与约瑟夫·拉格朗日发现了基于微积分的公式以确定最优值，艾萨克·牛顿与卡尔·弗里德里希·高斯提出迭代法以逼近最优值。

用于部分优化情形的“线性规划”（linear programming）是乔治·伯纳德·丹齐格提出的，不过其中大部分理论是列昂尼德·坎托罗维奇于1939年提出的。丹齐格在1947年提出单纯形法，冯·诺依曼等人也在同时期致力于线性规划的理论研究（如对偶）。

其他著名的最优化研究者有：

• 理查德·贝尔曼
• 德梅萃·博赛卡斯
• Michel Bierlaire
• Stephen P. Boyd
• Roger Fletcher
• Martin Grötschel
• Ronald A. Howard
• 弗瑞兹·约翰
• Narendra Karmarkar
• 威廉·卡鲁什
• Leonid Khachiyan
• Bernard Koopman
• 哈罗德·W·库恩
• 洛瓦兹·拉兹洛
• 大卫·伦伯杰
• 阿尔卡迪·内米罗夫斯基
• 尤里·涅斯捷罗夫
• 列夫·庞特里亚金
• R. Tyrrell Rockafellar
• Naum Z. Shor
• 阿尔伯特·W·塔克

主要分支

• 线性规划：当目标函数f是线性函数而且集合A是由线性等式函数和线性不等式函数来确定的， 我们称这一类问题为线性规划
• 整数规划：当线性规划问题的部分或所有的变量局限于整数值时， 我们称这一类问题为整数规划问题
• 二次规划：目标函数是二次函数，而且集合A必须是由线性等式函数和线性不等式函数来确定的。
• 分数规划：研究的是如何优化两个非线性函数的比例。
• 非线性规划：研究的是目标函数或是限制函数中含有非线性函数的问题。
• 随机规划：研究的是某些变量是随机变量的问题。
• 动态规划：研究的是最优策略基于将问题分解成若干个较小的子问题的优化问题。
• 组合最优化：研究的是可行解是离散或是可转化为离散的问题。
• 无限维最优化：研究的是可行解的集合是无限维空间的子集的问题，一个无限维空间的例子是函数空间。
• 凸优化研究目标函数为凸函数（最小化）或凹函数（最大化），且约束集为凸集的问题。这可以看成非线性规划的特例，或凸二次规划的推广。
  • 线性规划（LP），是凸规划的一种，研究目标函数f为线性函数、约束只包含线性等式与不等式的问题。若这种约束集是有界集合，又称作多面体或多胞形。
  • 二阶锥规划（SOCP）是凸规划的一种，包括某些类型的二次规划。
  • 半正定规划（SDP）是凸规划的一个子领域，其中底变量是半正定矩阵，它是线性规划与凸二次规划的推广。
  • 锥规划是凸规划的一般形式。LP、SOCP、SDP都是其特例。
  • 几何规划是一种表示不等式约束的正项式、表示等式约束的单项式化为凸规划的技术。
• 整数规划研究部分或所有变量取整数值的线性规划，不属于凸规划，往往比常规线性规划困难很多。
• 二次规划允许目标函数包含二次项，而可行集须用线性等式与不等式指定。若有特殊形式的二次项，则属于凸规划。
• 分式规划研究两非线性函数之比的优化。一类凹分式规划可转为凸优化问题。
• 非线性规划研究目标函数和/或约束包含非线性部分的一般情形。可能属于凸规划也可能不属于，规划是否为凸一般会影响求解难度。
• 随机规划研究某些约束或参数取决于随机变量的问题。
• 稳健优化类似于随机规划，试图捕捉优化问题基础数据中的随机性。稳健优化试图找到在不定集定义的不确定性的所有可能下，都有效的解。
• 组合优化关注可行解集离散，或可简化为离散情形的问题。
• 随机优化用于搜索过程中的随机（噪声）函数测量或随机输入。
• 无穷维优化研究可行解集为无穷维空间（如函数空间）子集的情形。
• 启发式与元启发算法对待优化问题（几乎）不做假设。启发式算法一般不能保证找到最优解，而可用于找到很多复杂优化问题的近似解。
• 约束满足研究目标函数f为常数的情形（常见于人工智能领域，特别是自动推理）。
  • 约束编程是一种编程范式，变量间关系表为约束。
• 分离规划（disjunctive programming）研究必须满足至少一个约束，而非所有约束的问题。分离规划尤其适用于调度。
• 空间映射是工程系统建模与优化的概念，利用具有物理意义的代理模型，达到保持模型精度，而减小计算量的效果。

在一些子领域中，这些技术用于动态环境（随时间变化的决策）中的优化：

• 变分法是指找到实现某目标的最佳方法，如找到边界为特定曲线，而面积尽可能小的曲面。
• 最优控制是变分法的推广，引入了控制策略。
• 动态规划是解随机优化问题的一种方法，具有随机、未知的模型参数，其优化策略基于将问题分割为子问题。描述子问题间关系的方程叫做贝尔曼方程。
• 均衡约束数学规划问题的约束包含变分不等式或互补式。

多目标优化

主条目：多目标优化

在优化问题中加入多个目标，会增加问题复杂性。例如，优化结构设计时人们希望设计轻而坚固。两目标发生冲突时，就要做出权衡：可能有一种最轻的设计、一种最坚固的设计与无数种重量与强度相折中的设计。牺牲一项标准，改进另一项标准的折衷设计集合称作帕累托集，据最佳设计的重量与强度绘制的曲线叫帕累托前沿（Pareto frontier）。

若设计不被其他设计支配，就是“帕累托最优”的（等同于“帕累托有效”，或在帕累托集合中）：被支配设计在某些方面比别的设计差，而在任何方面都不比别的设计好。

帕累托最优给出了理想目标，而没有对目标的组合进行相对评定。在帕累托最优方案中进行选择的任务属于决策者。

多目标优化问题可进一步推广为向量优化，其中（部分）排序不再由帕累托排序给出。

多峰、全局优化

优化问题通常是多峰的，即拥有多个好的解决方案，它们可能都是全局最优解（成本函数值相同）。获得所有（或至少一部分）解是多峰优化的目标。

经典优化技术采用的迭代法面对多峰问题的表现并不令人满意，因为即使运行起点不同，也不能保证获得不同的解。

对可能存在多个极值的全局优化问题，常用算法有进化算法、贝叶斯优化与模拟退火等。

临界点与极值的分类

可行性问题

可满足性问题又称可行性问题，是指在不考虑目标值的情况下找到任何可行解的问题。可以视为数学优化的一种特例，即每个解的目标值都相同，于是每个解都是最优解。

很多优化算法都要从可行点出发。获得可行点的一种方法是用松弛变量放松可行性条件，只要有足够的松弛变量，任何起点都是可行的。然后，最小化该松弛变量，直到松弛不为正。

存在性

卡尔·魏尔施特拉斯的极值定理指出，紧集上的连续实值函数会达到其最值。更一般地，紧集上的下半连续函数会达到其最小值，紧集上的上半连续函数会达到其最大值。

最优性的必要条件

费马引理指出，无约束问题的最优点是驻点，即目标函数的一阶导或梯度为零（见导数判别法）。更一般地，最优点可能出现在临界点，即目标函数的一阶导或梯度为零或未定义，或在选择集的边界上。一阶条件（组）是指令内部最优点处的一阶导等于零的方程（组）。

等式约束问题的最优点可用拉格朗日乘数法找到。带等式和/或不等式约束的问题的最优值可由卡鲁什-库恩-塔克条件求得。

最优性的充分条件

一阶导检验可以识别可能是极值的点，但不能区分极小值与极大值。无约束问题的目标函数二阶可微时，可通过检验二阶导（矩阵，叫做黑塞矩阵）来区分；有约束问题中，可检验目标函数与约束条件的二阶导矩阵（称作有界黑塞矩阵）。区分极大极小值与其他驻点的条件叫做二阶条件（见导数判别法）。若候选解满足一阶条件，则满足二阶条件便足以确定至少是局部最优。

最优解的敏感性与连续性

包络定理描述了基本参数变化时，最优解的值如何变化。计算这种变化的过程称为比较静力学。

Claude Berge（1963）提出的极大值定理描述了最优解作为基本参数之函数的连续性。

最优解的计算

主条目：卡鲁什-库恩-塔克条件

参见：临界点 (数学)、微分学、梯度、黑塞矩阵、正定矩阵、利普希茨连续、拉德马赫定理、凸函数和凸分析

对目标函数二阶可微的无约束问题，可通过寻找梯度为零的点（驻点）确定一些临界点。更一般地，对凸函数及其他局部利普希茨函数的最小化问题，零次梯度意味着已找到极小值。

此外，临界点还可根据黑塞矩阵的正定性分类：若临界点处的黑塞矩阵是正定的，则是极小值；若是负定的，则是极大值；若是不定的，则是某种鞍点。

在拉格朗日乘数的帮助下，有约束问题往往可以转为无约束问题。拉格朗日松弛法也能为困难的约束问题提供近似解。

目标函数是凸函数时，极小值也就是最小值。对凸函数的最小化，存在高效的数值技术，如内点法。

全局收敛

更一般地，若目标函数不是二次函数，那么很多优化方法都会用其他方法确保某些迭代子列收敛到最优解。第一种仍很流行的是线搜索，这种方法沿一个维度对函数进行优化。第二种越来越流行的，是置信域方法。线搜索与置信域方法都被用于现代不可微优化中。通常，全局优化器比先进的局部优化器（如BFGS算法）慢得多，因此通常可从不同起点启动局部优化器，构建高效的全局优化器。

计算优化技术

求解时往往使用有限步内终止的算法，或（在某些类的问题上）收敛到解的迭代法，或尽可能为某些问题提供近似解的启发式算法（迭代不一定收敛）。

优化算法

• 乔治·伯纳德·丹齐格为线性规划提出的单纯形法
• 单纯形法的推广，为二次规划与线性分式规划设计
• 特别适用于网络优化的单纯形法变体
• 组合算法
• 量子优化算法

迭代法

主条目：迭代法

迭代法用于解非线性规划，依其求值的是黑塞矩阵、梯度或函数值而有所不同。求黑塞矩阵（H）和梯度（G）可以提高收敛速度，但对变化足够平滑的函数，这会增加每次迭代的计算复杂度（计算成本），有时可能会过高。

优化器的一个重要指标就是所需的函数求值次数，因为这往往需要大量计算，通常比优化本身的计算量大得多，因为优化器要对N个变量进行操作。导数为此类优化器提供了详细信息，但算起来更困难。例如，近似梯度至少要求N+1次函数值。二阶导的近似（黑塞矩阵需要）每次迭代要求N²次函数值，例如牛顿法，而更简单的纯梯度优化器则只需要N次。优化器的选择取决于具体问题。

• 需要黑塞矩阵的方法（或用差分计算近似值）：
  • 牛顿法
  • 序列二次规划：基于牛顿法，适于中小尺度约束问题。某些版本可处理高维问题。
  • 内点法：这是一大类用于约束优化的方法，其中有些只使用（次）梯度信息，另一些则需要黑塞矩阵。
• 需要梯度的方法（或近似值，或次梯度）：
  • 坐标下降法：每次迭代更新一次坐标。
  • 共轭梯度法：针对大型问题的迭代法（理论上在二次目标函数的有限步数内终止，但在有限精度计算机上不常能达到）。
  • 梯度下降法（或“最陡下降法”“最陡上升法”）：具有历史与理论意义的（较慢）方法，在寻找巨大问题的近似解时再次受到关注。
  • 次梯度法：使用广义梯度迭代大型局部利普希茨函数的方法。根据Boris T. Polyak的观点，次梯度投影法类似于共轭梯度法。
  • 捆绑下降法（Bundle method of descent）：适用于局部利普希茨函数的中小型问题，尤其适用于凸最小化问题（类似于共轭梯度法）。
  • 椭球法：适用于目标函数为拟凸函数的小型问题的迭代法，在理论上有重要意义，特别是在确定某些组合优化问题的多项式时间复杂度方面。与拟牛顿法有相似之处。
  • 弗兰克–沃尔夫法（条件梯度法）：用于具有线性约束的特殊结构问题，特别是交通网络问题。对于一般的无约束问题简化为梯度法，而梯度法（对几乎所有问题）已经过时。
  • 拟牛顿法：适于大中型（N<1000）问题的迭代法。
  • 同时扰动随机逼近（SPSA），用于随机优化，运用随机（高效）梯度逼近。
• 只需要函数值的方法：若问题是连续可微的，那么可用有限差分法逼近梯度，这时可用基于梯度的方法。
  • 插值法
  • 模式搜索，收敛特性优于Nelder–Mead法（启发式算法，带单纯形），下详。
  • 镜像下降

启发式

主条目：启发式算法

除了（有限终止）算法与（收敛）迭代法，还有启发式算法，是指任何不能保证（数学上）找到解，但某些实际情况中有用的算法。一些著名的启发式算法：

• 差分进化算法
• 动态松弛法
• 进化算法
• 遗传算法
• 随机重启的爬山算法
• 模因算法
• Nelder–Mead法：近似最小化的流行启发式算法（不需计算梯度）
• 粒子群优化
• 模拟退火
• 随机隧道
• 禁忌搜索

应用

力学

刚体力学问题（尤其铰接刚体力学）常常需要数学规划技巧，因为可以将刚体力学视为解约束流形上的常微分方程，约束是各种非线性几何约束，如“这两点必须重合”“此曲面不得穿过其他曲面”“此点须始终位于此曲线上的某处”之类。此外，1计算接触力的问题也可由线性互补问题解决，也可看作是二次规划问题。

很多设计问题可表述为优化规划。这种应用叫做设计优化，其中一类是工程优化，最近不断发展的另一类是多学科设计优化，在很多领域都很有用，尤其适用于航空航天工程问题。

这种方法可用于宇宙学与天体物理学。

经济学与金融学

经济学与行为主体的优化密切相关，有人将经济学作为一门科学，描述为“将人类行为视作目的与稀缺性之关系的研究”，还有其他用途。现代优化理论包括传统优化理论，也与博弈论、经济均衡研究有重叠。《经济文献杂志》的JEL分类系统将数学规划、优化技术与相关主题归入JEL:C61-C63。

微观经济学中，效用最大化及其对偶问题支出最小化，都是经济优化问题。在行为一致的情形下，消费者被假定为效用最大化，公司被假定为利润最大化。此外，主体常被建模为风险厌恶者。资产定价也用最优化理论建模，不过其基础数学依赖于随机过程的优化，而非静态最优化。国际贸易理论也用最优化解释国家间的贸易模式。投资组合优化是经济学中多目标优化的一个例子。

1970年代以来，经济学家利用控制论建立了随时间变化的动态决策模型。例如，动态搜索模型用于研究劳动力市场行为。确定性模型与随机模型之间的区别至关重要。宏观经济学的动态随机一般均衡（DSGE）模型描述整个经济的动态，是工人、消费者、投资者与政府相互依赖的优化决策结果。

电气工程

优化技术在电气工程的一些常见应用如有源滤波器设计、减少超导储磁系统中的杂散磁场、微波结构的空间映射设计、手机天线、基于电磁学的设计等等。自1993年提出空间映射以来，微波组件与天线的电磁验证设计优化已广泛使用了适当的物理/经验代理模型及空间映射方法。优化技术也用于功率流分析。

土木工程

优化已广泛用于土木工程。营建管理与交通工程是土木工程中非常依赖优化的主要分支。通过优化解决的最常见的土木工程问题有道路的切割与填筑、基础设施生命周期分析、资源均衡、水资源分配、交通管理及进度优化。

运筹学

另一个广泛使用优化技术的领域是运筹学。运筹学也使用随机建模与模拟来支持改进决策。近年来，运筹学越来越多地使用随机规划模拟适应事件的动态决策；此类问题可通过大规模优化与随机优化方法来解决。

控制工程

数学优化被广泛用于现代控制器设计。模型预测控制（MPC）与实时优化（RTO）等高级控制器都采用了数学优化。这些算法在线运行，通过迭代求解约束与待控制系统模型在内的数学优化模型，反复确定决策变量的值，如工艺设备中的扼流圈开口。

地球物理

优化技术常用于地球物理参数估计。根据一组测量数据（如地震记录），通常要求底层岩石与流体的物理特性与几何形状。地球物理学中大多数问题都是非线性的，确定性方法与随机方法都有广泛使用。

分子建模

主条目：分子建模

构象异构常用非线性优化方法。

生物系统建模

主条目：生物系统建模

优化技术被用于计算系统生物学的许多方面，如建立模型、优化实验设计、代谢工程与合成生物学等。线性规划被用于计算发酵产物的最大可能产量，从多个微阵列数据集推断基因调控网络以及从高通量数据推断转录调控网络等。非线性规划被用于分析能量代谢，并被应用于代谢工程与生化途径的参数估计。

与人工智能的关系

现代的计算机科学技术和人工智能科学把最优化作为一个重要的领域来研究。我们也可以认为人工智能的一些算法，就是模拟了人类寻求实际问题最优解的过程。例如，利用人工智能方法设计软件，配合外部的电子设备例如摄像头识别人脸；利用数据挖掘和神经网络算法来寻找投资的最佳时机等。

另见

• 最优化问题
• 最值点
• 博弈论
• 运筹学
• 模糊逻辑
• 随机最优化
• 变分不等式
• 单体算法
• 内点法
• 对偶性 (优化)

参考文献

• Stephen Boyd and Lieven Vandenberghe (2004). Convex Optimization （页面存档备份，存于互联网档案馆），Cambridge University Press. ISBN 0-521-83378-7.

阅读更多

• Boyd, Stephen P.; Vandenberghe, Lieven. Convex Optimization. Cambridge: Cambridge University Press. 2004 [2024-02-03]. ISBN 0-521-83378-7. （原始内容存档于2021-12-11）. 
• Gill, P. E.; Murray, W.; Wright, M. H. Practical Optimization. London: Academic Press. 1982. ISBN 0-12-283952-8. 
• Lee, Jon. A First Course in Combinatorial Optimization. Cambridge University Press. 2004. ISBN 0-521-01012-8. 
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization 2nd. Berlin: Springer. 2006 [2024-02-03]. ISBN 0-387-30303-0. （原始内容存档于2008-05-30）. 

外部链接

• Decision Tree for Optimization Software. [2024-02-03]. （原始内容存档于2007-03-17）.  Links to optimization source codes
• Global optimization. [2024-02-03]. （原始内容存档于2022-01-29）. 
• EE364a: Convex Optimization I. Course from Stanford University. [2024-02-03]. （原始内容存档于2024-06-29）. 
• Varoquaux, Gaël. Mathematical Optimization: Finding Minima of Functions. [2024-02-03]. （原始内容存档于2024-04-16）.