最优化
维基百科，自由的百科全书
最优化，是应用数学的一个分支，主要研究以下形式的问题：
- 给定一个函数
，寻找一个元素
使得对于所有A中的
，
（最小化）；或者
（最大化）。
这类定式有时还称为“数学规划”（譬如，线性规划）。许多现实和理论问题都可以建模成这样的一般性框架。
典型的，A一般为欧几里德空间
中的子集，通常由一个A必须满足的约束等式或者不等式来规定。 A的元素被称为是可行解。函数f被称为目标函数，或者费用函数。一个最小化（或者最大化）目标函数的可行解被称为最优解。
一般情况下，会存在若干个局部的极小值或者极大值。局部极小值x * 定义为对于一些δ > 0，以及所有的x 满足
;
公式
成立。这就是说，在
周围的一些闭球上，所有的函数值都大于或者等于在该点的函数值。一般的，求局部极小值是容易的，但是要确保其为全域性的最小值，则需要一些附加性的条件，例如，该函数必须是凸函数。
目录 |
[编辑] 一些标识
最优化问题通常有一些较特别的标示方法。例如：
这是要求表达式x2 + 1的最小值，这里x取值为全体实数，
。这个问题的最小值应该是1，当x = 0。
这是要求表达式2x的最大值，同样地，x在全体实数上取值。对于这个问题，由于该表达式不是有界的，因此不存在最大值，因此，答案应该是无限大，或者是不可定义的。
[编辑] 主要分支
- 线性规划 当目标函数f是线性函数而且集合A是由线性等式函数和线性不等式函数来确定的， 我们称这一类问题为线性规划
- 整数规划 当线性规划问题的部分或所有的变量局限于整数值时， 我们称这一类问题位整数规划问题
- 二次规划 目标函数是二次函数，而且集合A必须是由线性等式函数和线性不等式函数来确定的。
- 非线性规划 研究的是目标函数或是限制函数中含有非线性函数的问题。
- 随机规划 研究的是某些变量是随机变量的问题。
- 动态规划 研究的是最优策略基于将问题分解成若干个较小的子问题的优化问题。
- 组合最优化 研究的是可行解是离散或是可转化为离散的问题。
- 无限维最优化 研究的是可行解的集合是无限维空间的子集的问题，一个无限维空间的例子是函数空间。
[编辑] 手法
对于无约束的优化问题， 如果函数是二次可导的话，可以通过找到目标函数梯度为0 （也就是拐点）的那些点来解决此优化问题。我们需要用Hessian矩阵来确定此点的类型。如果Hessian矩阵是正定的话，该点是一个局部最小解， 如果是负定的话，该点是一个局部最大解，如果Hessian矩阵是不定的话，该点是某种鞍点。
要找到那些拐点，我们可以通过猜测一个初始点，然后用比如以下的迭代的方法来找到。
- 剃度下降法
- 牛顿法
- conjugate gradient
- line search
如果目标函数在我们所关心的区域中是凸函数的话，那么任何局部最小解也是全局最优解。现在已经有稳定，快速的数值计算方法来求二次可微地凸函数的最小值。
约束问题常常可以通过拉格朗日乘数转化为非约束问题。
其他一些流行的方法有：
- random-restart hill climbing
- 模拟退火
- stochastic tunneling
- 遗传算法
- evolution strategy
- differential evolution
- 微粒群算法
[编辑] 参见
[编辑] 参考
- Stephen Boyd and Lieven Vandenberghe (2004). Convex Optimization, Cambridge University Press. ISBN 0521833787.
