5无约束优化方法.ppt

共轭梯度法共轭方向生成通式 共轭梯度法的特点： 1. 共轭梯度法可看作是对最速下降法的修正，故收敛速度较最速下降法快； 2. 共轭梯度法具有二次收敛性； 3. 共轭梯度法程序简单，存储量小，对初始点要求不严。 4. 共轭梯度法梯度模较小时容易上溢出。 第五节 变尺度法 变尺度法(Variable Metric Method)也称为拟Newton法(Quasi-Newton Method)，是求解无约束最优化问题最有效的算法之一，它不需要求二阶Hesse矩阵，而只利用一阶导数来构造二阶信息的近似矩阵，从而该算法有较好的收敛性质。 一、尺度矩阵的概念 变量的尺度变换就是对其坐标进行放大或缩小处理，达到降低函数偏心率的目的。 对于二次函数 进行尺度变换 则函数的二次项变为 若矩阵H是正定的，则一定存在尺度矩阵Q，使 由此可见，二次函数的Hesse矩阵H的逆阵H-1 ，可以通过尺度矩阵Q求得。 Newton法迭代公式因此而变为： 梯度法迭代公式为： 记 称为尺度矩阵 则Newton法和梯度法的迭代公式可统一写为： 为了避免在牛顿法中直接计算目标函数f(X)的Hesse矩阵的逆阵[H(X(k))] -1 ，故构造一个尺度矩阵序列{Ak}来逼近[H(X(k))] -1 ,则称Ak为变尺度矩阵。从而可得变尺度法的迭代公式为： 二、变尺度矩阵的构造原则： 1. 为了保证迭代公式具有下降性质，要求{Ak}中的每个矩阵都是对称正定的。 2. 为了计算简便，要求Ak具有如下的递推关系： 3. 为了获得牛顿法的收敛速度，要求Ak ? [H(X(k))] -1 。 Ak不可能在数值上近似于[H(X(k))] –1，因为我们的目标是不计算Hesse矩阵[H(X(k))] –1。那么， Ak只能在性质上近似[H(X(k))] –1。因此，先研究一下Hesse矩阵的逆阵[H(X(k))] –1的性质。 考虑 f(X)在X(k)处的Taylor展开式 令X=X(k+1)，得 求梯度得 记 则得拟牛顿条件： 令Ak+1满足拟牛顿条件，得： 即 满足上述拟牛顿条件的?Ak 有无穷多个，因此变尺度法是一族方法。 三、DFP变尺度矩阵 DFP公式是由Daviden在1959年提出来的，后由Fletcher和Powell在1963年于以简化，故此而得名的。 设 代入拟牛顿条件 得： 比较系数得： DFP变尺度矩阵迭代公式为： 四、BFGS变尺度矩阵 由于DFP变尺度法的数值稳定性差，1970年由Brogden、Fletcher、Goldfarb、Shanno提出数值稳定性好的BFGS变尺度法，其尺度矩阵迭代公式如下： 五、变尺度矩阵的统一表达式 1970年Huang对变尺度矩阵迭代公式进行了统一处理，得出如下公式： 其中 当取 为DFP公式 当取 为BFGS公式 当取 当取 为McCormick公式 为Pearson公式 (1)取初始点X(0)，置初始矩阵A0=I，置精度要求ε,置k=0. 六、变尺度法的算法步骤 (2)计算gk=?f(X(k))，如果‖?f(X(k))‖≤ε，则停止计算，将X(k)作为无约束问题的解输出；否则计算有哪些信誉好的足球投注网站方向 (3)沿d(k)方向进行一维有哪些信誉好的足球投注网站,即求解一维问题 (4)计算 gk+1=?f(X(k+1)), ?gk= gk+1- gk， ?Xk= X(k+1)- X(k) 修正矩阵 ?Ak和尺度矩阵 Ak+1 =Ak +?Ak 得： (5)置k=k+1，若kn,转(2)；否则X(0) =X(k+1),A0=I，k=0，转(2). 七、变尺度法的特点 1、算法具有下降性 2、算法具有二次收敛性 定理：设矩阵Ak正定对称矩阵，且?XkT?gk 0，则由DFP公式(或 BFGS公式)构造的Ak+1是正定对称的。 若一维有哪些信誉好的足球投注网站是精确的，假设已进行了m次迭代，则: 定理：若用DFP算法(或BFGS算法)求解正定二次函数 (1)有哪些信誉好的足球投注网站方向d(0),d(1),…,d(m-1)是m个非零的H共轭方向; (2)对于j=0，2，…，m-1，有 Am?Xj=?gj 且当m=n-1时，有An=H-1 证明： 仅对DFP公式进行证明即可. 由于?XkT?gk 0，蕴含着 ?gk ≠0，再由Ak的正定性，得到 ?gkT Ak ?gk 0 ，因此DFP公式有意义。 对任意的x∈Rn，考察 由广义Cauchy-Schwarz不等式 证得Ak＋1是正定的，其对称性是显然的. 证明： 由算法知，有哪些信誉好的足球投注网站方向d(0),d(1),…,d(m-1)是零的。现证明其共轭性。用数学归纳法证明： * 第四章 无约束最优化方法 第一节 概述 第二节 最速下