最优化方法教案(2)

21第3章无约束最优化方法●无约束最优化问题：)(minxf，nxR●方法：迭代法拟牛顿法牛顿法，共轭梯度法，解析法：最速下降法，换法方向加速法，单纯形替直接法：步长加速法，●直线搜索：)()(minkktpxft直线搜索方法：黄金分割法，抛物线插值法，平分法§3.1直线搜索一、黄金分割法二、平分法问题：设Cxf)(，ba，0)(af，0)(bf，并给出精度.求近似极小点和极小值。基本原理：在],[ba内)(xf有极小点*x,且0)(*xf.令)(21bac,若0)(cf,则在],[ca内)(xf有极小点*x,将],[ba的右边一半去掉,得新的搜索区间],[ca;若0)(cf,则在],[bc内)(xf有极小点*x,将],[ba的左边一半去掉,得新的搜索区间],[bc。计算步骤1．令)(21bac；2．若2ab，则转4，否则；223．计算)(cf，若0)(cf，则转4；若0)(cf，则ca:，转1；若0)(cf，则cb:，转1；4．令cx*，停止。注：若满足条件的],[ba尚未得到，则可按以下步骤确定：首先任取一点0x，指定步长0x。1．计算)(0xf，若0)(0xf，则0*xx，停止；若0)(0xf，则转4；若0)(0xf，则；2．令xxx01；3．若0)(1xf，则1*xx，停止；若0)(1xf，则令0:xa，1:xb，停止；若0)(1xf，则令10:xx，转2；4．令xxx01；5．若0)(1xf，则1*xx，停止；若0)(1xf，则令1:xa，0:xb，停止；若0)(1xf，则令10:xx，转4。例：三、抛物线插值法23§3.2最速下降法最速下降法，又称梯度法。是最古老的一种算法。在每次迭代中，沿最速下降方向进行搜索。迭代公式为：kkkkkktkkkkkkptxxtpxfptxftxfp1min:)(§3.3牛顿法设二次函数xbQxxxfTT21)(的最优解*x存在，用梯度法迭代一次即得最优解：*0001xptxx。由极值的必要条件，有0)(**bQxxf则)()()(0100100101*xfQxbQxQxxbQxbQx若取)(010xfQp，则*001xpxx。推广到一般函数)(xf，取)()(1kkkxfxGp其中，)(kxG为)(xf在kx处的海色矩阵。一、牛顿法的基本思想：在迭代过程中将)(xf在点kx附近按泰勒公式展开，取到二次项))(()()()()()()(T21TkkkkkkxxxGxxxxxfxfxxf以二次函数)(x的极小点作为)(xf的极小点的第1k次近似：240))(()()(kkkxxxGxfx得牛顿法的迭代公式：)()(11kkkkxfxGxx………………（*）特殊地，若Rx（一维），（*）式为)()(1kkkkxfxfxx即为一维情形（一维搜索）的牛顿法的迭代公式。二、牛顿法的步骤已知)(xf及梯度)(xg，海色矩阵)(xG，给出精度。1．选定初始点0x，计算)(0xf，)(00xgg，令0:k；2．计算)(kkxgg；若kg，则令kxx*，停止，否则；3．计算)(kkxGG；4．计算1kG，kkkgGp1；5．计算kkkpxx1；6．令1:kk，转2。三、主要结论定理：已知目标函数)(xf及梯度0kg，kG正定，则由式（*）确定的kp为下降方向。证明：由kG正定，则1kG也正定。又0kg，则有01TTkkkkkgGgpg则kp为下降方向。例1：例2：25§3.4共轭方向法与共轭梯度法（一）共轭方向法一、共轭方向定义1：设Q为n阶对称正定方阵，若对于n维空间中的两个非零向量x和y有，x和Qy正交，即0TQyx，则称向量x和y关于Q共轭，或称x和y是Q共轭的。推广：设Q为n阶对称正定方阵，n维非零向量kppp,,,21满足0TjiQpp，jikji,,,2,1,即其中任何两个向量都是Q共轭的，则称向量组kppp,,,21是Q共轭（向量）。特殊：当IQ，Q共轭即为正交。例：定理1：设Q为n阶对称正定方阵，非零向量组kppp,,,21为Q共轭，则此向量组线性无关。二、共轭方向法1.特点：第k次迭代时所取的方向kp和以前各次迭代所取的方向110,,,kppp都是Q共轭的。2.性质设二次函数cxbQxxxfTT21)(，其中Q为n阶正定矩阵，26nbxR,，c为常数，0x为初始点。定理2：设*x是n元二次函数)(xf的极小点，方向110,,,nppp为Q共轭，kx是由共轭方向法产生的点列，则至多迭代n次就能够达到极小点*x。（对于二次函数，该性质称为二次终止性）共轭方向的形成可以概括为以下定理：定理3：设1º二次函数cxbQxxxfTT21)(，Q为n阶正定矩阵，0x为初始点；2º,0)(00xfg00gp；3º),(1kkkpxlsx；4º若0)(11kkxfg，则确定方向1kp：kkkkkkkkkQppQpgpgpTT111,则i)kppp,,,10)1,,2,1(nk都是下降方向;ii)kppp,,,10)1,,2,1(nk是Q共轭的;iii)0T1ikpg,ki,,1,0;iv)0T1ikgg,ki,,1,0.(二)共轭梯度法一、系数k的其它形式1.对于上述二次函数,由bQxxg)(,得kkkkkkQptxxQgg][1127（由3º：kkkkptxx1)则有][][kkkkkkkggpggg1T1T1————SW共轭梯度法2.由0T1kkgg，0T1kkpg，得kkkkkkkkgggpggpTT11T][（由4º：kkkkpgp11）则有221T1T1kkkkkkkgggggg————FR共轭梯度法3.kkkkkkgggggT1T1][————PRP共轭梯度法二、最佳步长kt的计算公式由kkkkkkkkQptgbptxQbQxg)(11有01kTkkkTkkTkQpptpgpg得最佳步长kt：kkkkkQpppgtTT28三、FR共轭梯度法的步骤（适用于一般非线性函数，包括二次函数）已知初始点0x及收敛精度。1．计算)(00xgg；若00g，令0*xx，停；否则2．令0:k，00gp，转63．按FR公式计算：221kkkgg，kkkkpgp114．令1:kk，若1nk，转8；否则5．若0kTkpg，转8；否则6．作线搜索：),(1kkkpxlsx7．计算)(11kkxgg；若1kg，则令1*kxx，停；否则转38．令kxx0，kgg0，00gp，0:k，转6；例：试用FR共轭梯度法求下列函数121222121232)(xxxxxxf的极小点*x，取初始点Tx]00[)0(。解：29§3.5步长加速法§3.6方向加速法（Powell法）方向加速法，又称Powell法，是无约束最优化的直接方法之一。一、基本思想：在迭代过程中的每个阶段都作n+1次线搜索。首先，依次沿给定的n个线性无关的方向nppp,,,21作线搜索，再沿由这一阶段的起点到第n次搜索所得点的方向p作一次线搜索，把这次所得的点作为下一阶段的起点。下一阶段的n个搜索方向pppn,,,2。二、步骤设)(xf的极小点*x的初始近似为)0(x，控制误差为。取n个线性无关的方向neee,,,21，je是第j个分量为1的单位向量。1．0:k，njepjj,,2,1,；2．0j，)()0,(kkxx；3．作线搜索：1),(11),(minjjkjjjkpxfpxf令11),()1,(jjjkjkpxx4．令1:jj；5．若nj，则转3，否则；6．)0,(),(knkxxp；7．作线搜索：pxfpxfnknnk),(1),(min30令pxxnnkk1),()1(8．若)()1(kkxx或)()1(kxf。则转10，否则；9．令1,,2,1,1njppjj，pppn（可略），1kk，转2；10．令)1(*kxx，停.例：设1212221422)(xxxxxxf，初始点为Tx]11[)0(.试用Powell法求)(xf的极小点*x。解：1.第一次迭代,0:k.(1))0()0,0(xx；取TTpp]10[,]01[21.34)1(4)1(22)1()1,1(221)0,0(1fpxf(或124c)(1c为常数)令0421得21.于是得TTTpxx]13[]01[2]11[11)0,0()1,0((2)2222)1,0(22234)1(32)1(29)1,3(cfpxf(2c为常数)令0241得212.于是得TTTpxx]5.13[]10[]13[2122)1,0()2,0((3)Txxp]5.02[)0,0()2,0(；cfpxf25.2)25.1,23(2)2,0(3令0253得52*.于是得31Tpxx]7.18.3[*)2,0()1(2.第二次迭代,1:k.(1)起点)1()0,1(xx；取TTpp]5.02[,]10[21.121)0,1(18.02)7.1,8.3(cfpxf令08.041得2.01.于是得Tpxx]9.18.3[11)0,1()1,1((2)222)1,1(24.05.2)5.09.1,28.3(cfpxf令04.051得08.02.于是得Tpxx]94.196.3[22)1,1()2,1((3)Txxp]24.016.0[)0,1()2,1(；令03得41*.于是得Tpxx]24[*)2,1()2(.0)()2(xf,则Tx]24[*32§3.7最小二乘问题的解法一、最小二乘问题多参数曲线拟合问题：确定函数),,;,,,(121nlxxtttFy，其中，参数nxx,,1待定。问题：已知)(nm个实验点：miytttiilii,,1],;,,,[)()()(2)(1，试确定n个参数nxx,,1，从而建立回归方程。解：首先得到“偏差”（或距离）：211211()()()()(,,)[(,,,;,,)]miiiinlniSxxFtttxxy原问题转化为：1min(,,)nSxx，求出1**,,nxx回归方程：121**(,,,;,,)lnyFtttxx上述方法称为最小二乘法。简记：1211()()()()()(,,,;,,),,,iiiiilnfxFtttxxyimT1)](,),([)(nxfxfxf则上述问题转化为miixfxfxf12T)()()(min或2min()fx（*）式（*）称为最小二乘问题的一般形式；当)(xf是线性向量函数时，称为线性最小二乘问题；否则称为非线性最小二乘问题。33二、最小二乘法1.线性最小二乘问题（1）线性最小二乘问题如下：2minbAx（**）其中，A是nm矩阵，b是m