最优化

最优化，是应用数学的一个分支。主要研究在特定情况下最大化或最小化某一特定函数或变量。

数学表述

最优化主要研究以下形式的问题：

给定一个函数$f:A\to \mathbb {R}$，寻找一个元素$\mathbf {x} ^{0}\in A$使得对于所有$A$中的$\mathbf {x}$，$f(\mathbf {x} ^{0})\leq f(\mathbf {x} )$（最小化）；或者$f(\mathbf {x} ^{0})\geq f(\mathbf {x} )$（最大化）。

这里$A$一般为欧几里得空间$\mathbb {R} ^{n}$中的子集，通常由一个$A$必须满足的约束等式或者不等式来规定。 $A$的元素被称为是可行解。函数$f$被称为目标函数，或者代价函数。一个最小化（或者最大化）目标函数的可行解被称为最优解。

这类问题有时也称为“数学规划”（譬如，线性规划）。许多现实和理论问题都可以利用这样的一般性框架来建模，成为一个最优化问题。

一般情况下，会存在若干个局部的极小值或者极大值。局部极小值$x^{*}$定义为对于一些$\delta >0$，以及所有的$x$ 满足

$\|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta$;

公式

$f(\mathbf {x} ^{*})\leq f(\mathbf {x} )$

成立。这就是说，在$\mathbf {x} ^{*}$周围的一些闭球上，所有的函数值都大于或者等于在该点的函数值。一般的，求局部极小值是容易的，但是要确保其为全域性的最小值，则需要一些附加性的条件，例如，该函数必须是凸函数。

根据以下的结论，最大化和最小化问题可以相互变换。一般情况下，最优化问题就可以只讨论最小化即可。

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

符号表示

最优化问题通常有一些较特别的符号标示方法。例如：

$\min _{x\in \mathbb {R} }\;x^{2}+1$

这是要求表达式$x^{2}+1$的最小值，这里x取值为全体实数，$\mathbb {R}$。这个问题的最小值应该是$1$，当$x=0$。

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

这是要求表达式$2x$的最大值，同样地，$x$在全体实数上取值。对于这个问题，由于该表达式不是有上界的，因此不存在最大值，因此，答案应该是无限大，或者是不可定义的。

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

这是求使表达式x²+1 达到最小值时x的值。在这里x被限定在区间[-∞ ,-1]之间，所以上式的值是-1。

主要分支

• 线性规划：当目标函数f是线性函数而且集合A是由线性等式函数和线性不等式函数来确定的， 我们称这一类问题为线性规划
• 整数规划：当线性规划问题的部分或所有的变量局限于整数值时， 我们称这一类问题為整数规划问题
• 二次规划：目标函数是二次函数，而且集合A必须是由线性等式函数和线性不等式函数来确定的。
• 分数规划：研究的是如何优化两个非线性函数的比例。
• 非线性规划：研究的是目标函数或是限制函数中含有非线性函数的问题。
• 随机规划：研究的是某些变量是随机变量的问题。
• 动态规划：研究的是最优策略基于将问题分解成若干个较小的子问题的优化问题。
• 组合最优化：研究的是可行解是离散或是可转化为离散的问题。
• 无限维最优化：研究的是可行解的集合是无限维空间的子集的问题，一个无限维空间的例子是函数空间。

算法

对于无约束的优化问题， 如果函式是二次可微的话，可以通过找到目标函数梯度为0（也就是拐点）的那些点来解决此优化问题。我们需要用黑塞矩阵来确定此点的类型。如果黑塞矩阵是正定的话，该点是一个局部最小解， 如果是负定的话，该点是一个局部最大解，如果黑塞矩阵是不定的话，该点是某种鞍点。

要找到那些拐点，我们可以通过猜测一个初始点，然后用比如以下的迭代的方法来找到。

• 梯度下降法
• 牛顿法
• 共轭梯度法
• 线性搜索
• 置信域方法

如果目标函数在我们所关心的区域中是凸函数的话，那么任何局部最小解也是全局最优解。现在已经有稳定，快速的数值计算方法来求二次可微地凸函数的最小值。

有約束條件的约束问题常常可以通过拉格朗日乘数转化为非约束问题。

其他一些流行的方法有：

• 遗传算法
• 神经网络
• 微粒群算法
• 模拟退火
• 支持向量机
• 蚁群算法
• 类免疫演算法
• 演化策略
• 差分进化算法

與人工智能的關係

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

参考文献

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

参閲

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

外部链接

• NEOS Guide
• Online curve and surface fitting
• Xpress-MP - Optimization software free to students （页面存档备份，存于互联网档案馆）