无约束最优化方法

无约束最优化方法第一页，共一百一十八页，编辑于2023年，星期三主要内容5.1最速下降法

5.2共轭梯度法

5.3牛顿法

5.4变尺度法

5.5步长加速法

5.6旋转方向法5.7方向加速法

5.8信赖域方法

5.9最小二乘法

第二页，共一百一十八页，编辑于2023年，星期三无约束最优化问题的求解方法：解析法和直接法。解析法需要计算函数的梯度，直接法仅通过比较目标函数值的大小来移动迭代点。一般来说，无约束最优化问题的求解是通过一系列一维搜索来实现。如何选择搜索方向是求解无约束最优化问题的核心问题，搜索方向的不同选择，形成不同的求解方法。第三页，共一百一十八页，编辑于2023年，星期三5.1最速下降法

5.1.1最速下降法原理第四页，共一百一十八页，编辑于2023年，星期三第五页，共一百一十八页，编辑于2023年，星期三5.1.2最速下降法的计算步骤第六页，共一百一十八页，编辑于2023年，星期三第七页，共一百一十八页，编辑于2023年，星期三第八页，共一百一十八页，编辑于2023年，星期三clearsymsx1x2;%定义符号变量fx=2*x1^2+x2^2;%定义符号函数X0=[1,1];%初值g=jacobian(fx,[x1,x2]);%求符号函数的梯度H=jacobian(g,[x1,x2]);%求符号函数的海塞矩阵x1=X0(1,1);x2=X0(1,2);%赋初值g0=eval(g);H0=eval(H);%求符号函数在x1=1、x2=1梯度、海塞矩阵k=0;fprintf('\n')whilenorm(g0)>eps

%停机判断条件

lamda=g0*g0‘/(g0*H0*g0’);

%求lamdafprintf('k=%2d,lamda=%19.16f,x1=%19.16f,x2=%19.16f,fx=%19.16f,norm(p)=%19.16f\n',k,lamda,x1,x2,eval(fx),norm(g0))X0=X0-lamda*g0;x1=X0(1,1);x2=X0(1,2);g0=eval(g);H0=eval(H);k=k+1;end第九页，共一百一十八页，编辑于2023年，星期三5.1.3最速下降法的收敛性第十页，共一百一十八页，编辑于2023年，星期三第十一页，共一百一十八页，编辑于2023年，星期三由定理5-1知，在最速下降法中，前后两次的搜索方向垂直（见图5-1）。锯齿形的搜索轨迹使最速下降法效率低下。最速下方向反映了目标函数的一种局部性质。从局部看，最速下降方向的确是函数值下降最快的方向，选择这样的方向进行搜索是有利的，从全局看，由于锯齿现象的出现，当在极小点附近时，即使向着极小点移动不太大的距离，也要经历不少的弯路，从而使收敛速度大为减慢。第十二页，共一百一十八页，编辑于2023年，星期三最速下降法不仅简单，而且具有全局收敛性，并且是线性收敛的。为避免锯齿现象对收敛速度的影响，在计算初期可使用最速下降法，在迭代一段时间以后，改用其它更有效的方法，如牛顿法等。对一般的下降算法，只要搜索方向与迭代点处的负梯度方向的夹角小于90°，使用精确一维搜索和不精确一维搜索在一定的条件下，可以证明下降算法具有全局收敛性。第十三页，共一百一十八页，编辑于2023年，星期三共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出，1964年Fietcher和Reever在此基础上，首先提出了求解无约束最优化问题的共轭梯度法。共轭梯度法的基本思想：把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行一维搜索，求出目标函数的极小点。该方法具有收敛速度快、存储空间小等特点，尤其是对于正定二次函数能在有限步内达到极小点，即具有二次终结性。5.2共轭梯度法

第十四页，共一百一十八页，编辑于2023年，星期三5.2共轭梯度法

5.2.1共轭方向与共轭方向法第十五页，共一百一十八页，编辑于2023年，星期三第十六页，共一百一十八页，编辑于2023年，星期三第十七页，共一百一十八页，编辑于2023年，星期三第十八页，共一百一十八页，编辑于2023年，星期三第十九页，共一百一十八页，编辑于2023年，星期三复习

第二十页，共一百一十八页，编辑于2023年，星期三复习

第二十一页，共一百一十八页，编辑于2023年，星期三复习

第二十二页，共一百一十八页，编辑于2023年，星期三第二十三页，共一百一十八页，编辑于2023年，星期三你能找到A共轭方向吗？第二十四页，共一百一十八页，编辑于2023年，星期三第二十五页，共一百一十八页，编辑于2023年，星期三第二十六页，共一百一十八页，编辑于2023年，星期三第二十七页，共一百一十八页，编辑于2023年，星期三第二十八页，共一百一十八页，编辑于2023年，星期三P(0)和p(1)正交吗？第二十九页，共一百一十八页，编辑于2023年，星期三（5-2）第三十页，共一百一十八页，编辑于2023年，星期三5.2.2正定二次函数的共轭梯度法

第三十一页，共一百一十八页，编辑于2023年，星期三第三十二页，共一百一十八页，编辑于2023年，星期三第三十三页，共一百一十八页，编辑于2023年，星期三第三十四页，共一百一十八页，编辑于2023年，星期三第三十五页，共一百一十八页，编辑于2023年，星期三第三十六页，共一百一十八页，编辑于2023年，星期三5.2.3共轭梯度法的计算步骤

第三十七页，共一百一十八页，编辑于2023年，星期三5.2.4非二次函数的共轭梯度法第三十八页，共一百一十八页，编辑于2023年，星期三复习第三十九页，共一百一十八页，编辑于2023年，星期三第四十页，共一百一十八页，编辑于2023年，星期三5.2.5共轭梯度法的收敛性第四十一页，共一百一十八页，编辑于2023年，星期三第四十二页，共一百一十八页，编辑于2023年，星期三第四十三页，共一百一十八页，编辑于2023年，星期三第四十四页，共一百一十八页，编辑于2023年，星期三第四十五页，共一百一十八页，编辑于2023年，星期三5.3牛顿法

对一维搜索方法中的牛顿法加以推广，就得到了求解无约束优化问题的牛顿法。该方法具有收敛速度快的特点，在牛顿法基础上的改进算法如阻尼牛顿法在实际中被广泛应用。第四十六页，共一百一十八页，编辑于2023年，星期三5.3.1牛顿法原理利用二次函数近似目标函数。

第四十七页，共一百一十八页，编辑于2023年，星期三第四十八页，共一百一十八页，编辑于2023年，星期三第四十九页，共一百一十八页，编辑于2023年，星期三第五十页，共一百一十八页，编辑于2023年，星期三第五十一页，共一百一十八页，编辑于2023年，星期三第五十二页，共一百一十八页，编辑于2023年，星期三第五十三页，共一百一十八页，编辑于2023年，星期三5.3.2牛顿法的特点与收敛性牛顿法优点：牛顿法具有二阶收敛速度。对二次正定函数，仅需一步迭代即可达到最优解，具有二次终结性。牛顿法缺点：（1）牛顿法是局部收敛的，即初始点选择不当，可能会导致不收敛；（2）牛顿法不是下降算法，当二阶Hesse阵非正定时，不能保证是下降方向；（3）二阶Hesse阵必须可逆，否则算法将无法进行下去；（4）对函数分析性质要求苛刻，计算量大，仅适合小规模优化问题。由于牛顿法有良好收敛速度，人们对它的缺点进行了多方面改进和修正。第五十四页，共一百一十八页，编辑于2023年，星期三5.3.3牛顿法的改进1.阻尼（广义）牛顿法第五十五页，共一百一十八页，编辑于2023年，星期三第五十六页，共一百一十八页，编辑于2023年，星期三2.Goldstein-Price方法第五十七页，共一百一十八页，编辑于2023年，星期三第五十八页，共一百一十八页，编辑于2023年，星期三5.4变尺度法

第五十九页，共一百一十八页，编辑于2023年，星期三5.4.1变尺度法原理

第六十页，共一百一十八页，编辑于2023年，星期三第六十一页，共一百一十八页，编辑于2023年，星期三5.4.2DFP变尺度法第六十二页，共一百一十八页，编辑于2023年，星期三第六十三页，共一百一十八页，编辑于2023年，星期三第六十四页，共一百一十八页，编辑于2023年，星期三5.4.3BFGS变尺度法与初始尺度矩阵的修正第六十五页，共一百一十八页，编辑于2023年，星期三第六十六页，共一百一十八页，编辑于2023年，星期三5.4.4变尺度法的计算步骤第六十七页，共一百一十八页，编辑于2023年，星期三第六十八页，共一百一十八页，编辑于2023年，星期三第六十九页，共一百一十八页，编辑于2023年，星期三第七十页，共一百一十八页，编辑于2023年，星期三第七十一页，共一百一十八页，编辑于2023年，星期三第七十二页，共一百一十八页，编辑于2023年，星期三第七十三页，共一百一十八页，编辑于2023年，星期三使用MATLAB软件实现DFP算法第七十四页，共一百一十八页，编辑于2023年，星期三例5-5最优解搜索过程

第七十五页，共一百一十八页，编辑于2023年，星期三例5-5三维图

第七十六页，共一百一十八页，编辑于2023年，星期三5.4.5变尺度法的性质与收敛性

第七十七页，共一百一十八页，编辑于2023年，星期三5.5步长加速法解析法：最速下降法、共轭梯度法、牛顿法和变尺度法需要计算目标函数的梯度。直接法：不需要求目标函数的梯度。5.5.1步长加速法的基本思想又称模式搜索法（PatternSearchMethod）。由胡克（Hooke）和基夫斯（Jeeves）于1961年提出的。它不仅易于编制计算机程序，而且具有追循谷线加速移向最优点的性质。基本思想从几何上讲，就是寻找具有较小函数值的“山谷”，力图使迭代产生的序列沿“山谷”逼近极小点。第七十八页，共一百一十八页，编辑于2023年，星期三5.5.2步长加速法的搜索过程步长加速法由“探测移动”和“模式搜索”两个交替的动作构成。探测移动：依次沿n个坐标轴进行，用以确定新的基点和有利于函数值下降的方向。模式搜索：沿相邻两个基点连线方向进行，试图顺着“山谷”使函数值下降的更快（见图5-4）。第七十九页，共一百一十八页，编辑于2023年，星期三第八十页，共一百一十八页，编辑于2023年，星期三第八十一页，共一百一十八页，编辑于2023年，星期三5.5.3步长加速法的计算步骤第八十二页，共一百一十八页，编辑于2023年，星期三第八十三页，共一百一十八页，编辑于2023年，星期三第八十四页，共一百一十八页，编辑于2023年，星期三第八十五页，共一百一十八页，编辑于2023年，星期三5.6旋转方向法5.6.1旋转方向法的基本思想

第八十六页，共一百一十八页，编辑于2023年，星期三5.6.2旋转方向法的搜索过程第八十七页，共一百一十八页，编辑于2023年，星期三第八十八页，共一百一十八页，编辑于2023年，星期三第八十九页，共一百一十八页，编辑于2023年，星期三5.6.3旋转方向法的计算步骤第九十页，共一百一十八页，编辑于2023年，星期三第九十一页，共一百一十八页，编辑于2023年，星期三第九十二页，共一百一十八页，编辑于2023年，星期三第九十三页，共一百一十八页，编辑于2023年，星期三第九十四页，共一百一十八页，编辑于2023年，星期三请读者比较步长加速法和旋转方向法的区别第九十五页，共一百一十八页，编辑于2023年，星期三5.7方向加速(powell)法

5.7.1方向加速法的基本思想方向加速（Powell）法的基本思想：把整个搜索（计算）过程分为若干个阶段（轮），每个轮迭代由n+1次一维搜索组成。即在算法的每一轮中，先依次沿着n个已知的方向搜索，得到一个最好点，然后沿该轮的初始点与该最好点连线方向进行搜索，求得这一轮的最好点。再用最后的搜索方向取代前n个方向之一，进行下一轮的迭代。Powell法的特点：理论体系严密，本质是共轭方向法在一定条件下具有二次终结性第九十六页，共一百一十八页，编辑于2023年，星期三5.7.2基本powell法的计算步骤

第九十七页，共一百一十八页，编辑于2023年，星期三第九十八页，共一百一十八页，编辑于2023年，星期三5.7.3powell法的二次终结性

第九十九页，共一百一十八页，编辑于2023年，星期三第一百页，共一百一十八页，编辑于2023年，星期三5.7.4改进的powell法

第一百零一页，共一百一十八页，编辑于2023年，星期三5.8信赖域法

5.8.1信赖域法的基本思想无约束最优化问题的一般求解策略是，给定点后，定义搜索方向，再从出发沿作一维搜索，得到新的点。信赖域方法另辟蹊径，其基本思想：给定点后，确定一个变化范围，通常取以为中心的球域（称为信赖域），在此域内优化目标函数的二次逼近式，按一定的模式求出后继点。如果不满足精度要求，再定义以为中心的信赖域，并在此域内优化新的二次逼近式，直到满足精度要求为止。信赖域方法是Po