第四章 无约束优化方法

一维搜索方法一维搜索方法黄金分割法（0.618法）：程序框图：一维搜索方法牛顿法（切线法）：用切线代替弧逐渐逼近函数极值的一种方法。1'()(0,1,2,)''()kkkkfkf牛顿法的迭代公式:一维搜索方法二次插值法（抛物线法）：，缩小搜索区间：用插值函数p(α)的极小点αp作为原目标函数的极小点α*的近似解，通常不能满足给定的迭代精度要求，所以需要多次缩短搜索区间，使αp的点列中的各点依次逐步逼近α*。第四章无约束优化方法第一节概述为什么要研究无约束优化问题？(1)有些实际问题的数学模型是无约束优化问题(2)通过熟悉它的解法可以为研究约束优化问题打下良好的基础(3)约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础第四章无约束优化方法第一节概述1、解析法2、数值计算法（搜索方法）解法分类（1）利用目标函数的一阶或二阶导数：如最速下降法、共轭梯度法、牛顿法及变尺度法（2）只利用目标函数值：如坐标轮换法、单形替换法及鲍威尔法第四章无约束优化方法第一节概述，数值解法：是利用已有的信息，通过计算点一步一步地直接移动，逐步逼近最后达到最优点。1(0,1,)kkkkxxdk1）选择迭代方向即探索方向；2）在确定的方向上选择适当步长迈步进行探索第四章无约束优化方法第一节概述，•从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向d(k),取适当的步长a(k),逐次搜寻函数值下降的新迭代点x(k+1),使之逐步通近最优点x*第四章无约束优化方法第一节概述，可以把初始点x(k)、搜索方向d(k)、迭代步长a(k)称为优化方法算法的三要素。其中以搜索方向d(k)更为突出和重要，它从根本上决定若一个算法的成败、收敛速率的快慢等。kkkkdxx)()1(的确定方法不同的kd解法不同的无约束优化问题第四章无约束优化方法第二节最速下降法，定义：最速下降法就是采用使目标函数值下降得最快的负梯度方向作为探索方向，来求目标函数的极小值的方法，又称为梯度法。1()(0,1,)kkkkxxfxk最速下降法的迭代公式梯度方向)(minxf梯度方向是目标函数上升最快的方向，负梯度方向则是最速下降方向；)(xfd为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有()kfxk1()[()]min[()]min()kkkkkkaaffaffafxxxxx'()[()]()0Tkkkkfffxxx1[()]()0kTkffxx1()0kTkdd第四章无约束优化方法第二节最速下降法第四章无约束优化方法第二节最速下降法，最速下降法的迭代步骤：011*10();3minmin4||;1,kkkkkkkkkkkkkxkdfxfxadaxxadxxxxkk1）给定初始点和收敛精度，置；2）计算梯度，并构造搜索方向）用一维搜索的方法求解得最佳步长，代入得到新的迭代点；）若，则停止迭代，得最优解否则，转到第二步。第四章无约束优化方法第二节最速下降法，最速下降法的迭代步骤：011*10();3minmin4||;1,kkkkkkkkkkkkkxkdfxfxadaxxadxxxxkk1）给定初始点和收敛精度，置；2）计算梯度，并构造搜索方向）用一维搜索的方法求解得最佳步长，代入得到新的迭代点；）若，则停止迭代，得最优解否则，转到第二步。第四章无约束优化方法第二节最速下降法，最速下降法的特点：•（1）理论明确，程序简单，对初始点要求不严格•（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质•（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢第四章无约束优化方法第二节最速下降法，最速下降法的特点：•（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点第四章无约束优化方法第二节最速下降法2212()25fxxx例：用最速下降法求目标函数的极小点。，1()(0,1,)kkkkxxfxk00102()10424()50100xfxfxxx沿负梯度方向进行一维搜索，有01000024()2100fxxx0为一维搜索最佳步长，应满足极值必要条件122()min(24)25(2100)min()fx例4－1求目标函数的极小点。解取初始点则初始点处函数值及梯度分别为0[2,2]Tx2212()25fxxx00'()8(24)5000(2100)0算出一维搜索最佳步长06260.0200307231252第一次迭代设计点位置和函数值0120241.91987721000.307178510x1()3.686164fx继续作下去，经10次迭代后，得到最优解00Tx()0fx将上例中目标函数引入变换2212()25fxxx221212(,)yyyy其等值线由椭圆变成一簇同心圆。仍从即出发进行最速下降法寻优。此时：0[2,2]Tx0[2,10]Ty00102()10424()220yyyyy沿负梯度方向进行一维搜索：则函数f(X)变为：y1=x1,y2=5x21000000()242410201020yyyβ为一维搜索最佳步长，可由极值条件：10022()min[()]min()()(24)(1020)yyy0()0由0260.552从而算得一步计算后设计点的位置及其目标函数：010124010200()0yy经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：11225yxyx等值线由椭圆变成圆。试用梯度法求目标函数f(X)=1.5x12+0.5x22-x1x2-2x1的最优解，设初始点x(0)=[-2，4]T,迭代精度ε=0.02（迭代一步）。第四章无约束优化方法第三节牛顿型法，基本思想：在领域内用一个二次函数来近似代替原目标函数，并将的极小值作为目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。kx)(x)(x)(xf)(xf1kx),2,1,0()()('''1kxfxfxxkkkk2000001()()()'()()()()2fxxfxfxxxfxxx1'()0x对于多元函数fX，设kX为fX极小点X的第一个近似点，fX泰勒展开，保留到二次项，得:设1kX为X的极小点，它作为fX极小点X的下一个近似点，根据极值必要条件：10kX即210kkkkfXfXXX112(0,1,2)kkkkXXfXfXk2kfX——海赛矩阵---多元函数求极值的牛顿法迭代公式。fxx212TTkkkkkkfxfxxxxxfxxx第四章无约束优化方法第四章无约束优化方法第三节牛顿型法，牛顿型法的基本思想：利用二次曲线来逐点近似原目标函数，以二次曲线的极小点来近似原目标函数的极小点并逐渐逼近该点。基本牛顿法的迭代公式：11(0,1,2)()kkkkkkxxdkdGxfx第四章无约束优化方法第三节牛顿型法，基本牛顿法的迭代公式：11(0,1,2)()kkkkkkxxdkdGxfx02212121[1,1],0.1min()224Txfxxxxxx例：用基本牛顿法求解下列无约束优化问题，已知。阻尼牛顿法1.问题提出：1;12121kkkkkkkkkkkxfxfddxxfxfxx步长：则搜索方向：沿牛顿方向进行一维搜索的最佳步长称为阻尼因子，由下式求得：kkkkkkkkxfxfxdxx121)(min)()(1kkkkkkkdxfdxfxf2.改进方法：搜索方向不变，改用最佳步长k第四章无约束优化方法第三节牛顿型法，基本牛顿法的迭代公式：11(0,1,2)()kkkkkkxxdkdGxfx阻尼牛顿法的迭代公式：11(0,1,2,)()kkkkkkkxxdkdGxfx第四章无约束优化方法第三节牛顿型法，阻尼牛顿法的迭代步骤：01111*1,0;()()()()34||;1,kkkkkkkkkkkkkkkxkfxGxGxdGxfxxxddxxxxkk1）给定初始点收敛精度，置2）计算、和，得到；）求，其中，是沿着进行一维搜索的最佳步长；）检查收敛精度。若，则停止迭代，得最优解否则，转到第二步继续进行搜索。第四章无约束优化方法第三节牛顿型法，02212121[1,1],0.1min()224Txfxxxxxx例：用阻尼牛顿法求解下列无约束优化问题，已知。阻尼牛顿法的迭代公式：11(0,1,2,)()kkkkkkkxxdkdGxfx方法特点（1）初始点应选在X*附近，有一定难度；（2）尽管每次迭代都不会是函数值上升，但不能保证每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；（4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。1(0,1,2,)kkkkskxx1()(0,1,2,)kkkkafkxxx121[()]()(0,1,2,)kkkkffkxxxx121[()]()(0,1,2,)kkkkkffkxxxx一般迭代式：梯度法：牛顿法：阻尼牛顿法：梯度法与牛顿法：1()kkkkkGfxxx第四章无约束优化方法第四节共轭方向及共轭方向法，10[()]0Tfxd在下一次迭代时，选择搜索方d1指向极小点x*，*111xxad•共轭方向以二元函数为例：我们任意选择一个初始点x0点，沿着某个下降方向d0作一维搜索1000xxad12TTfxxGxbxc010TdGd第四章无约束优化方法第四节共轭方向及共轭方向法，•共轭方向01m101m1Gnmddd()0(,0,1,,1)()dddGGiTjdGdijmij设是nn对称正定矩阵，若维空间中有个非零向量、、、满足则称、、、对共轭，或称它们是的共轭方向。•正交01m1GI()0()dddiTjddij当=（单位矩阵）时，有，即向量、、、互相正交。第四章无约束优化方法第四节共轭方向及共轭方向法，•共轭方向的性质01m1001n1*dddG()m2nn3xnGdddn1x2TTfxxGxbxc性质1：若非零向量系、、、是对实对称正定矩阵共轭的，则这个向量是线性无关的。性质：在维空间中互相共轭的非零向量个数不超过。性质：从任意初始点点出发，顺次沿个的共轭方向、、、进行一维搜索，最多经过次迭代就可以找到二次函数的极小点。第四章无约束优化方法第四节共轭方向及共轭方向法，•共轭方向法的步骤00k1