最优化理论与方法ppt课件.ppt

《最优化理论与方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《最优化理论与方法ppt课件.ppt（60页珍藏版）》请在三一办公上搜索。

1、使用导数的无约束最优化方法,策略 表现形式 方法 线性近似 最速下降法二次近似 Newton法 共轭梯度法用布鲁丹（Broyden）族 或黄（Huang）族 拟Newton法 修正公式,最速下降法（Steepest Method）,考虑无约束问题下降算法对于下降方向的要求：最速下降法的 要求：,最速下降法（Steepest Method）,最速下降法的计算步骤：（1）给出初始点 和精度；（2）计算。如果，则令，停止；否则，转（3）；（3）令，求解 得到；（4）令，转（2）。,最速下降法（Steepest Method）,对于最速下降法的几点说明：（1）锯齿现象：目标函数在负梯度方向下降得最快只

2、是局部性质。（2）改进策略：在计算的开始阶段使用最速下降法，在迭代数次后，改用其他算法。,最速下降法（Steepest Method）,二次函数情形下最速下降法的收敛速度定理 考虑无约束最优化问题 其中G是n阶对称正定矩阵。和 分别是G的最大特征值和最小特征值。设 是问题的解点，则最速下降法至少具有线性的收敛速度，并且满足下面的界：,最速下降法（Steepest Method）,对于定理的说明：（1）在上面定理中，如果考虑的是如下一般二次目标函数，其中G是n阶对称正定矩阵，则有类似的证明方法证明定理同样成立。（2）当目标函数是二阶连续可微的一致凸函数时，由上章的推导可知，采用精确线性搜索的最速

3、下降法产生的迭代点列至少是线性收敛的。,最速下降法（Steepest Method）,定理：设最速下降法产生的点列 收敛到，在 附近二阶连续可微，且，正定，则 线性收敛到，即 其中M和m满足，和 分别是 的最小特征值和最大特征值。,Newton法及其改进,Nowton法的主要内容：（1）牛顿法的基本思想（2）阻尼牛顿法（3）带保护措施的阻尼牛顿法（4）吉尔-默里稳定牛顿法（5）信赖域方法（一）,Newton法及其改进,（1）牛顿法的基本思想：在目标函数 的极小点 的近似点 附近将 二阶Tayler展开，用展开的二次函数去逼近，将这个二次函数的极小点作为 的一个新的近似点 依次下去，用一系列二次

4、函数的极小点 去逼近 的极小点。,Newton法及其改进,设 二次连续可微，则 在 处的二次近似为：令即,Newton法及其改进,若 正定（对称），则 存在。Newton迭代公式 Newton方向：,Newton法及其改进,定理（Newton法收敛定理）设 二阶连续可微，是 的局部最优解，正定，Hesse矩阵 满足Lipschitz条件：即存在，使得对所有的i，j，有 其中 是Hesse矩阵 的 元素。则当初始点 充分靠近 时，对于一切的k，牛顿迭代公式有定义，并且所得迭代点列 收敛到，并且具有二阶收敛速度。,Newton法及其改进,牛顿法面临的主要困难：（1）很难检验初始点 是否靠近最优解

5、因而不能保证Hesse矩阵是否正定，得到的方向是下降方向，迭代点列的收敛性及收敛速度。（2）牛顿法对目标函数要求高（二阶连续可微），且需较多的存储单元，每次迭代均要进行矩阵求逆运算。（3）二次终止性：对于二次凸函数，用牛顿法求解，经1次迭代即达极小点。,Newton法及其改进,（2）阻尼牛顿法：在标准牛顿法增加了沿牛顿方向的直线搜索。阻尼牛顿法在适当的条件下具有全局收敛性，且为2级收敛。,Newton法及其改进,阻尼牛顿法的缺点：阻尼牛顿法克服了牛顿法要求初始点充分靠近目标函数的极小点的缺点，但只有当目标函数的Hesse矩阵处处正定时，才具有全局收敛性。如果Hesse矩阵不是处处正定，当初始点

6、远离局部极小点时，Hesse矩阵可能不正定，这时Hesse矩阵可能奇异也可能是非奇异。若Hesse矩阵奇异，求解方向的方程组可能无解，或者虽然有解，但求出的方向不能使迭代过程继续进行下去；若Hesse矩阵非奇异，但不正定，则求得的方向可能不是下降方向。,Newton法及其改进,例：取，则，显然，是可逆矩阵，但不正定。其逆矩阵为 于是，沿此方向进行线性搜索，其极小点为，因此迭代不能继续进行下去。,Newton法及其改进,（3）带保护措施的阻尼牛顿法（Goldstein和Price，1967）假设 可逆，若 正定，否则，,Newton法及其改进,（4）吉尔-默里稳定牛顿法（Gill和Murray，

7、1974）定义：设 在开集D上二次连续可微，（i）如果Hesse矩阵 至少有一个负特征值，则 叫做不定点。（ii）如果X是一个不定点，若方向d满足 则称d为在X处的负曲率方向。,Newton法及其改进,负曲率方向的性质：（1）若方向d为负曲率方向，则 也是负曲率方向。（2）在鞍点处，负曲率方向必是下降方向；（3）在一般点处，若负曲率方向d满足：，则d与 均是下降方向；，则d是下降方向；，则 是下降方向。,Newton法及其改进,Gill-Murray稳定牛顿法的基本思想：当Hesse矩阵 在迭代点 处为不定矩阵时，对其进行强迫正定的 分解；当 趋于零时，采用负曲率方向使函数值下降。构造一个对称

8、正定矩阵在 处做下降方向,Newton法及其改进,算法：（Gill-Murray稳定牛顿法）（1）给定初始点，精度，常数令；（2）计算梯度 和Hesse矩阵，令；（3）若，则停止计算，输出（4）判断 是否正定。若 正定，转（6）；否则转（5）；（5）计算，转（4）；,Newton法及其改进,算法：（Gill-Murray稳定牛顿法）（6）求解 求出搜索方向；（7）直线搜索，且令；（8）令，转（2）。,Newton法及其改进,定理：设 二阶连续可微，且存在，使得 为有界闭凸集。假定在吉尔-默里稳定牛顿法中取，且初始点，则吉尔-默里稳定牛顿法产生的迭代序列 满足：（i）当 为有穷点列时，其最后一个

9、元素必为 的稳定点；（ii）当 为无穷点列时，它必有聚点，且它的所有聚点都是 的平稳点。,共轭方向法（概述）,共轭方向法是介于最速下降法与牛顿法之间的一类方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存储和计算牛顿法所需要的二阶导数信息。因而简便、易实现、且十分适合大规模（稀疏）优化问题的计算，通常只经过较少的迭代次数就能获得满足所要求精度的近似解。共轭方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题。最典型的共轭方向法就是本节研究的共轭梯度法。下一节介绍的拟牛顿法也是共轭方向法。,共轭方向法（概述）,例：设，其中A为正定矩阵。能否从任意

10、初始点出发，经过至多两步迭代达到其极限点（最优解）？定义：（共轭方向）设A为n阶对称正定矩阵，是n维非零向量，如果，则称向量 和 是关于A共轭的。类似地，设 是m个n维向量，如果，则称 是关于A共轭的向量组。,共轭方向法（概述）,定理：设A为n阶对称正定矩阵，则关于A共轭的非零向量 是线性无关的。定理：（共轭方向法基本定理）设二次函数的极小化问题为，其中A是n阶对称正定矩阵，是任意一组关于A共轭的非零向量，若从任意初始点 出发，依次沿方向 进行精确线性搜索，则至多经过n次迭代就可达到问题的最优解。,共轭梯度法,定理：设向量 线性无关，则由这组向量可以构造m个关于A共轭的向量。共轭梯度法的基本思

11、想是把共轭性与最速下降方法相结合，利用已知点处的梯度构成一组共轭方向，并沿这组方向进行搜索，求出目标函数的最小点。根据共轭方向的基本性质，这种方法具有二次终止性。,共轭梯度法（二次函数）,考虑其中A为对称正定矩阵。给定初始点，计算若，则，停止计算；否则，令。若已知点 和搜索方向，则其中 使用精确线性搜索得到：,共轭梯度法（二次函数）,此时，令则有对于二次函数，有即解得,共轭梯度法（二次函数）,计算 在 处的梯度若，则停止计算；否则，用 和 构造。设要求 与 关于A共轭。解得再从 出发，沿方向 搜索。,共轭梯度法（二次函数）,共轭梯度法的迭代公式为：对于二次函数有：,共轭梯度法（二次函数）,FR

12、，1964：,共轭梯度法（二次函数）,定理：设目标函数为正定二次函数 则采用精确线性搜索的共轭梯度法经 步终止，且对所有 成立下列关系式：,共轭梯度法（二次函数）,FR，1964：PRP，1969：CW，1972：Dixon，1972：,共轭梯度法（二次函数）,例3.30用共轭梯度法求解取初始点为,共轭梯度法（二次函数）,共轭梯度法的计算步骤：（1）给定初始值，令。（2）计算。若，则，停止计算；否则，转（3）。（3）计算共轭系数,共轭梯度法（二次函数）,共轭梯度法的计算步骤：（4）构造搜索方向（5）计算 令（6）令，转（2）。,共轭梯度法（非二次函数）,（1）步长 不能用显式格式计算，必须用其

13、他直线搜索方法来确定。（2）矩阵A不再是常数矩阵，需要用现行点处的Hesse矩阵。改进思路：将共轭梯度法应用于非二次函数的极小化时，每迭代n次就周期地选取负梯度方向作为搜索方向，所以这种算法称作重新开始的共轭梯度法，即令,共轭梯度法（非二次函数）,鲍威尔：对非二次函数，在计算中可能出现 与 几乎正交的情况，此时FR：PRP：,共轭梯度法（二次函数）,共轭梯度法的计算步骤：（1）给定初始值，令。（2）计算。若，则，停止计算；否则，转（3）。（3）计算共轭系数,共轭梯度法（二次函数）,共轭梯度法的计算步骤：（4）构造搜索方向（5）做直线搜索计算 令（6）若，则，停止计算；否则，令，转（2）。,共轭

14、梯度法（非二次函数）,重新开始的共轭梯度法允许采用近似线性搜索过程，只是在采用近似线性搜索时，要采取一定的检查措施，以保证所得到的搜索方向是下降方向。但是，如果频繁地利用负梯度方向作为搜索方向，将大大降低共轭梯度法的效率，而使算法的性态变得更象最速下降法。采取检查措施可以克服这个困难。,拟牛顿法,最速下降法具有结构简单、计算量小的优点，但其收敛速度较慢；共轭梯度类算法具有计算存储量小的优点，一般使用于大规模优化问题。而牛顿法及各种改进的牛顿法具有收敛速度快的优点，但要求在迭代过程中每次构造搜索方向时，首先要计算目标函数的Hesse矩阵，然后需要求解一个线性方程组，从而计算量大，存储量也大，而且

15、有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就抵消了牛顿法收敛速度快的优点，这类算法只适用于中小规模的优化问题。,拟牛顿法,拟牛顿算法只需利用目标函数及其一阶导数的信息，构造对称正定的矩阵来近似牛顿法中的Hesse矩阵或者其逆矩阵，产生较好的近似牛顿方向，避免了Hesse矩阵的计算，减少了计算量，并且具有超线性收敛的优点。该法被认为是无约束优化（中小规模）问题中最有效的算法。,拟牛顿法,设 二次连续可微，则 在 处的二次近似为：则即拟牛顿法的基本迭代格式,拟牛顿法,记则若Hesse矩阵 可逆，则拟牛顿条件或拟牛顿方程,拟牛顿法,二次近似满足性质：,拟牛顿法,拟牛顿算法的一般框架与牛顿

16、法相比，拟牛顿法还要求以下几点：（1）（或）是对称正定矩阵，从而是下降方向，使得方法具有下降性质。（2）或称（或）为校正矩阵，上两个方程为校正条件。,拟牛顿法,（拟牛顿算法框架）（1）给出 初始值，令。（2）计算。如果，则令，停止迭代；否则，计算（3）沿方向d 作线性搜索求，令（4）计算校正 产生使得拟牛顿条件成立的，令，返回（2）。,拟牛顿法,秩1校正解得：设则有即从而,拟牛顿法,这时，称为秩1校正公式。为了保证矩阵的对称性，若取称为对称秩1校正公式。,拟牛顿法,若取称为布鲁丹（Broyden）秩1校正公式。,拟牛顿法,对称秩2校正公式,第3-2-5节 信赖域方法,信赖域方法的基本思想：首先

17、选取一个信赖域半径，并由此定义的一个邻域 使得n维二次模型 是目标函数 的一个合适的模拟。然后求解具有信赖域约束的子问题（*）,第3-2-5节 信赖域方法,实际下降量：预测下降量：衡量二次模型近似目标函数的指标：,第3-2-5节 信赖域方法,（1）给定初始点，初始步长，精度，阈值，满足 放大系数 令。（2）计算，如果，则，停止；否则，形成矩阵；（3）求解子问题（*），求出；,第3-2-5节 信赖域方法,（4）计算 和 的值。如果，那么；如果 和，那么；否则，令；（5）如果，那么；否则。，转（2）。,第3-2-5节 信赖域方法,例3.20用信赖域方法求解其中。,第3-2-5节 信赖域方法,引理3.21 是问题（*）的解，当且仅当 为满足 的二阶必要条件的极小点。定理3.22（信赖域方法总体收敛性定理）设 二阶连续可微，给定初始点，使得水平集 有界，且存在常数，使得 则信赖域方法产生的迭代序列至少有一个聚点满足 的一阶和二阶必要条件。,第3-2-5节 信赖域方法,定理3.23如果定理3.22中的聚点 还满足的Hesse矩阵 正定的条件，那么，对于主序列，有，以及对于充分大的k，约束。此外，收敛速度是二阶的。,