工程优化 第4章1无约束最优化方法解析.ppt

《工程优化 第4章1无约束最优化方法解析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优性条件最速下降法牛顿法及其阻尼牛顿法共轭方向法共轭梯度法变尺度法（DFP算法和BFGS算法）第4章无约束最优化方法目的是找中的一点，使对，均有，称为(1)的全局极小点。无约束最优化问题：求解(1)的计算方法称为无约束最优化方法。无约束最优化方法应用广泛，理论也比较成熟；可将约束优化问题转化为无约束优化问题来处理；最优化方法中的基本方法---无约束优化方法：利用函数的一阶或二阶导数的方法收敛速度快，需要计算梯度或者Hesse矩阵：仅利用函数值的信息，寻找最优解不涉及导数，适用性强，但收敛速度慢可求得目标函数的梯度时使用解析法在不可能求得目标函数的梯度或偏导数时使用直接

2、法本章介绍解析法最优性条件(OptimalityConditions)所谓最优性条件，是指最优化问题的最优解所要满足的必要条件或充分条件。这些条件对于最优化算法的建立和最优化理论的推导都是至关重要的。解析法要用到目标函数的梯度或者Hesse矩阵，容易想到利用一阶必要条件将无约束优化问题转化成一个梯度为0确定的方程组。这里用到的一阶必要条件就是最优性条件。定理(一阶必要条件)设，若为的局部极小点，且在内连续可微，则无约束优化的最优性条件----一阶必要条件若为的局部极小点，且在内二次连续可微，则半正定。无约束优化的最优性条件----二阶必要条件定理（二阶必要条件）定理(二

3、阶充分条件)设，若在内二次连续可微，且正定，则为的严格局部极小点。如果负定，则为的严格局部极大点。无约束优化的最优性条件----二阶充分条件定理(一阶充要条件)设是凸函数且在处连续可微，则为的全局极小点的充要条件是无约束优化的最优性条件----凸优化的一阶条件定理(一阶必要条件)设是严格凸函数且在处连续可微，若则为的唯一全局极小点。例：利用最优性条件求解下列问题：解：令即：得到驻点：无约束优化的最优性条件利用二阶条件判断驻点是否是极小点利用一阶条件求驻点函数的Hesse阵：在点处的Hesse阵依次为：无约束优化的最优性条件利用二阶条件判断驻点是否是极小点是不定矩阵；无约

4、束优化的最优性条件是正定矩阵；是负定矩阵；不是极小点；是极小点；是极大点。对某些较简单的函数，这样做有时是可行的；但对一般n元函数f(x)来说，由条件得到的是一个非线性方程组，解它相当困难。为此，常直接使用迭代法。(1)选定某一初始点，并令(2)确定搜索方向(3)从出发，沿方向求步长，以产生下一个迭代点(4)检查得到的新点是否为极小点或近似极小点。，转(2)继续进行迭代。在以上步骤中，选取步长可选用精确一维搜索或者非精确一维搜索，下降方向的选取正是下面我们要介绍的，下降方向选取的不同，得到不同的算法。若是，则停止迭代。线搜索迭代法的步骤否则，令从而得到第k+1次迭代点，

5、即步长由精确一维搜索得到。最速下降法负梯度方向这是函数值减少最快的方向假设f连续可微，最速下降法负梯度方向是函数值减少最快的方向？令是单位长度的向量，P是什么方向时，函数值下降最快？也就是p是什么方向时，取得最小值？当时，最小，最小值为，此时由可得最速下降法是求多元函数极值的最古老的数值算法，早在1847年法国数学家Cauchy提出该算法，后来Curry作了进一步的研究。该方法直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。最速下降法(1)选定某一初始点，并令(2)若，否则转（3）；由精确一维搜索确定步长步长，即由一个极小化问

6、题求得最佳步长最速下降法的迭代格式(3)令转（2）。算法框图x1,ε>0,k=1

7、

8、▽f(xk)

9、

10、<ε?Yesstop.xk–解Nodk=－▽f(xk)解minf(xk+λdk)s.t.λ>0得xk+1=x(k)+λkdkk=k+1最速下降法框图例利用最速下降法求解令解：函数的梯度为第1次迭代：取得令得第2次迭代：令得第3次迭代：继续迭代可得到函数的近似最优解。最速下降法的收敛性分析设目标函数f(x)连续可微，且水平集有界，则最速下降法或者在有限迭代步后终止；或者得到点列，它的任何聚点都是f(x)的驻点。在收敛定理的假设下，若f(x)为凸函数，则最速下降法或在有限迭代

11、步后达到最小点；或得到点列，它的任何聚点都是f(x)的全局最小点。收敛性定理：推论：最速下降法在两个相邻点之间的搜索方向是正交的。最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象。除特殊的目标函数和极特殊的初始点外，这种现象都会发生。令利用精确一维搜索，可得由此得出1.相邻两次迭代的方向互相垂直最速下降法的两个特征注：在最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形，这样从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法