最速下降法

4.1非线性规划数学模型4.2凸函数和凸规划4.3一维搜索4.4无约束优化问题的解法第四章无约束最优化问题第四节无约束优化问题的解法最速下降法Newton法拟Newton法共轭梯度法第四章无约束最优化问题一.最速下降法收敛性问题的基本概念最速下降法的迭代原理最速下降法的迭代步骤最速下降法的举例最速下降法的收敛结论)(minXfnRX)(NP无约束问题4-41.收敛性问题的基本概念定义4-9若序列，对于，存在正整数(){}kX0(),N当时，有，即kN()kXX()0,kkXX().kkXX则称收敛于，记为(){}kXX无约束问题4-4X0X1X2X3X4XkXmin()nXRfX()kfX()kkXX定义4-10,0)(kkXX若.)(XXkk则1.收敛性问题的基本概念若收敛于，且满足(){}kXX(1)()lim,kpkkXXXX则p称为收敛于的阶。(){}kXX当p=1时，称为一阶收敛；当p=2时，称为二阶收敛；当时，称为超线性收敛；12p无约束问题4-4当时，当p=2时，同阶无穷小若收敛于，且满足(){}kXX(1)()lim,kpkkXXXX则p称为收敛于的阶。(){}kXX,0)(kkXX若.)(XXkk则2(1)()kkXXXX与XXk)(XXk)1(1.001.00001.0810XXk)2(XXk)3(XXk)4(16101.收敛性问题的基本概念1,k2(1)()kkXXXX定义4-10无约束问题4-4当时，当p=1时，同阶无穷小若收敛于，且满足(){}kXX(1)()lim,kpkkXXXX则p称为收敛于的阶。(){}kXX,0)(kkXX若.)(XXkk则(1)()kkXXXX与XXk)(XXk)1(1.00.090.050.02XXk)2(XXk)3(XXk)4(0.011.收敛性问题的基本概念1,k(1)()kkXXXX定义4-10无约束问题4-4定义4-10,0)(kkXX若.)(XXkk则1.收敛性问题的基本概念若收敛于，且满足(){}kXX(1)()lim,kpkkXXXX则p称为收敛于的阶。(){}kXX当p=1时，称为一阶收敛；当p=2时，称为二阶收敛；当时，称为超线性收敛；12p无约束问题4-4最速下降法Newton法拟Newton法定义4-12若某算法对于任意正定二次目标函数,从任意初始点出发,都能经过有限次迭代达到其极小点,则该算法称为具有二次终止性的算法或二次收敛算法.1.收敛性问题的基本概念),,,(21nxxxfcXbQXXTT21结论：1()2TTfXXQXbXcbQX1当Q为正定阵时，称f(X)为正定二次函数。正定二次函数有唯一全局极小点：无约束问题4-4一.最速下降法收敛性问题的基本概念最速下降法的迭代原理最速下降法的迭代步骤最速下降法的举例最速下降法的收敛结论)(minXfnRX)(NP无约束问题4-4是X(k)处函数值下降最快的方向。当时，p(k)是f(X)在X(k)处的下降方向。函数f(X)在X(k)处的负梯度方向)()(kXf梯度的性质：2.迭代原理)()()()()()()()()(kTkkkkpXfXfpXf证明：))()(()()(kTkpXf充分小时)()()()()()()(hhxfxfhxfkkk00)()()()()()()()()(kTkkkkpXfXfpXf结论：()()()0kTkfXp)()(kXf)(kP)(kP)(kX)(kPcos)()()()()()(kkkTkpXfpXf)(kP一元函数泰勒公式：1cos()kX()()kkXp()kp无约束问题4-42.迭代原理),(00Xfp000p0X000pX)(min000pXf0001pXX)()(10XfXf)(minXfnRX),(000pXf,0X最优步长无约束问题4-4,0X),(00Xfp00p0X)(min000pXf0001pXX)(minXfnRX),(000pXf最速下降法迭代原理：0(1,1),TX42122xx312()(4,2)TfXxx00()(4,2)TpfX0014141212Xp0042()(14)(12)2()fXpF000min()()fXpF一维搜索找极小点：1)确定[0,1],精度0.102)用0.618法得到00.343751X040.53184()F无约束问题4-4,0X),(00Xfp00p0X)(min000pXf0001pXX)(minXfnRX),(000pXf最速下降法迭代原理：0(1,1),TX42122xx312()(4,2)TfXxx00()(4,2)TpfX0014141212Xp0042()(14)(12)2()fXpF000min()()fXpF00.343751(1,1)0.34375(4,2)(0.375,0.3125)TTTX10()2.11743()4fXfX1X无约束问题4-4,0X),(00Xfp00p0X1X)(min000pXf0001pXX)()(10XfXf)(minXfnRX),(000pXf1p,1X),(11Xfp)(min110pXf),(111pXf1112pXX111pX1)(2Xf12.迭代原理0最优步长最优步长无约束问题4-4,0X),(00Xfp00p0X1X)(min000pXf0001pXX)()(10XfXf)(minXfnRX),(000pXf1p,1X),(11Xfp)(min110pXf),(111pXf1112pXX2X)(2Xf,kX),(kkXfp)(min0kkpXf),(kkkpXfkkkkpXX11()()kkfXfXXXkk)((411)Th线性收敛2.迭代原理110最优步长最优步长,)()(严格kXf(410),Th得到一个点列：01(),,,,,kXXX可以证明：无约束问题4-4,0X),(00Xfp)(min000pXf0001pXX)(minXfnRX),(000pXf,1X),(11Xfp)(min110pXf),(111pXf1112pXX,kX),(kkXfp)(min0kkpXf),(kkkpXfkkkkpXX1,,,,,:)(10kXXX得到一个点列2.迭代原理()()kfX严格证明：)()()()()()()()()(kTkkkkpXfXfpXf))()(()()(kTkpXf充分小时00)()()()()()()()()(kTkkkkpXfXfpXf0,)()(严格kXfXXkk)(0)(2)(kXf)()()()()()()(kTkkTkXfXfpXf()()()()()0kkkkfXpfX1kX无约束问题4-4一.最速下降法收敛性问题的基本概念最速下降法的迭代原理最速下降法的迭代步骤最速下降法的举例最速下降法的收敛结论)(minXfnRX)(NP无约束问题4-4无约束问题4-43.迭代步骤0:,0)(,1)0(0kX令精度容许误差取初始点)(2)()(0kkXfp计算0)()(04,,?3否则转取若是迭代终止检验kkXXp))(()(min:4)()()()(00一维搜索求最优步长kkkkkkpXfpXf0)()()1(02,1:,5转令令kkpXXkkkk0k),(00Xfp)(min000pXf0001pXX),(000pXf),(11Xfp)(min110pXf),(111pXf1112pXX否则若是取,?)0()0(XXp1k否则若是取,?)1()1(XXp2k),(22Xfp否则若是取,?)2()2(XXp)(min220pXf),(222pXf2223pXX3.迭代步骤0:,0)(,1)0(0kX令精度容许误差取初始点)(2)()(0kkXfp计算0)()(04,,?3否则转取若是迭代终止检验kkXXp))(()(min:4)()()()(00一维搜索求最优步长kkkkkkpXfpXf0)()()1(02,1:,5转令令kkpXXkkkk注释：,)(时当XXk)()()(XfXfk00)()()(XfXfk)()(kXf)(kp(一阶必要条件))(minXfnRXTknkkkXxfXxfXxfXf))(,),(),(()()()(2)(1)(TnXxfXxfXxfXf))(,),(),(()(2110停机准则：设连续(即f(X)连续可微)()fX无约束问题4-4()0kXX0)()(04,,?3否则转取若是迭代终止检验kkXXp0:,0)(,1)0(0kX令精度容许误差取初始点)(2)()(0kkXfp计算))(()(min,4)()()()(00一维搜索求最优步长kkkkkkpXfpXf0)()()1(02,1:,5转令令kkpXXkkkk注释：)()(min)()()()(0kkkkkpXfpXf)()(k()()()()()kkTkfXpp)(0k)()1()(kTkpXf(411)k)(kp)1(kX)(kX)()1(kXf3.迭代步骤一维搜索最优解的梯度与搜索方向正交(1)()kfX()kp20结论：证明：()()()()()kkTkkkfXpp无约束问题4-40)()(04,,?3否则转取若是迭代终止检验kkXXp0:,0)(,1)0(0kX令精度容许误差取初始点)(2)()(0kkXfp计算))(()(min,4)()()()(00一维搜索求最优步长kkkkkkpXfpXf0)()()1(02,1:,5转令令kkpXXkkkk注释：最速下降法的任何两个相邻搜索方向正交(垂直))()(min)()()()(0kkkkkpXfpXf)()(k()()()()()kkTkfXpp)(0k)()1()(kTkpXf(411)0)()1(kTkppk)(kp)1(kX)1(kp)(kX)()1(kXf3.迭代步骤30结论：无约束问题4-40:,0)(,