最优化

一、最优化问题的分类

1. 根据约束类型分类：

(1)无约束问题
(2)约束问题

2.根据目标函数及约束函数的类型分类：

最优化问题也称为规划问题
如果最优化问题的目标函数为f(x),约束条件为gi(x)>=0,i=1,2,..,m,则：

(1)线性规划：

当f(x)和gi(x)均为线性函数时

(2)非线性规划：

当f(x)和gi(x)不全为线性函数时

(3)二次规划：

当f(x)为二次函数，而gi(x)全为线性函数时

3.根据变量的类型分类

(1)整数规划:

对于最优化问题，如果变量x=(x1，x2，…，xn)T的各分量只能取整数，则相应的最优化问题称为整数规划。

(2)混合整数规划:

如果变量x=(x1，x2，…，xn)T 的部分分量只能取整数，则相应的最优化问题称为混合整数规划。

(3)0-1规划:

如果变量x=(x1，x2，…，xn)T 的各分量只能取0和1，则相应的最优化问题称为0-1规划。

二、最优化问题的基本模型要素

最优化模型一般包括变量、约束条件和目标函数三要素：

1.变量:

指最优化问题中待确定的某些量。变量可用x=(x1，x2,…,xn)T表示。

2.约束条件:

指在求最优解时对变量的某些限制,包括技术上的约束、资源上的约束和时间上的约束等。列出的约束条件越接近实际系统，则所求得的系统最优解也就越接近实际最优解。约束条件可用 gi(x)≤0表示i=1,2，…，m，m 表示约束条件数；或x∈R(R表示可行集合)。

3.目标函数：

最优化有一定的评价标准。目标函数就是这种标准的数学描述，一般可用f(x)来表示，即f(x)=f(x1，x2,…,xn)。要求目标函数为最大时可写成；要求最小时则可写成。目标函数可以是系统功能的函数或费用的函数。它必须在满足规定的约束条件下达到最大或最小。 　问题的分类 　最优化问题根据其中的变量、约束、目标、问题性质、时间因素和函数关系等不同情况，可分成多种类型（见表）。最优化方法

三、常见的最优化方法

1. 梯度下降法（Gradient Descent）

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。

2. 牛顿法（Newton's Method）和拟牛顿法（Quasi-Newton Methods）

• 牛顿法
  牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。
• 拟牛顿法
  拟牛顿法是求解非线性优化问题最有效的方法之一，其本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

3. 共轭梯度法（Conjugate Gradient）

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

4. 启发式优化方法

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验，选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。启发式优化方法种类繁多，包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。

5. 拉格朗日乘数法的基本思想

作为一种优化算法，拉格朗日乘子法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。
将一个含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题，拉格朗日乘数法从数学意义入手，通过引入拉格朗日乘子建立极值条件，对n个变量分别求偏导对应了n个方程，然后加上k个约束条件（对应k个拉格朗日乘子）一起构成包含了（n+k）变量的（n+k）个方程的方程组问题，这样就能根据求方程组的方法对其进行求解。