10--拟牛顿法

§4.6拟牛顿法•牛顿法收敛很快，但需要计算Hesse矩阵，而此矩阵可能非正定，可能导致搜索方向不是下降方向。)()()(1)(2)(kkkxfxfd基本思想：用不包含二阶导数的矩阵近似Hesse矩阵的逆。拟牛顿条件)()()(1)(2)(kkkxfxfd)()()1(kkkkdxx与一阶导数的关系：首先分析1)(2)(kxf))(()(21))(()()()1()1(2)1()1()1()1()1(kkTkkkkkxxxfxxxxxfxfxfTaylorx展开：处进行二阶在点))(()()()1()1(2)1(kkkxxxfxfxf))(()()()1()()1(2)1()(kkkkkxxxfxfxf)(1)1(2)()()1(2)()()1()()()1()()()()()(::kkkkkkkkkkkkqxfppxfqxfxfqxxp)(1)(kkkqHpkH1.秩1校正2.DFP(Davidon-Fletcher-Powell)算法：秩2校正3.BFGS(Broyden-Fletcher-Goldfarb-Shanno)公式及Broyden族kkkHHHIH11;校正矩阵秩1校正TkkkkzzH)()(秩为1)(1)(kkkqHp)()()()(kTkkkkqzzH)()()()()(kTkkkkkkqzqHpz)()()()()(2)()(kkkTkkTkkqHpqqz)())(()()()()()()()(kkkTkTkkkkkkkqHpqqHpqHpH?0注释•在一定条件下，收敛且具有二次终止性。•无法保证Hk的正定性；即使能，也有可能导致△Hk无界。DFP算法TkkkTkkkkvvuuH)()()()(秩为2)(1)(kkkqHp)()()()()()(kTkkkTkkkkqvvuuH)()()()()()()()(kkkkTkkkkTkkkqHpqvvquu)()()()()()()()(1;1kTkkkkkkTkkkkqvqHvqupu；；令)()()()()()()()(kkTkkTkkkkTkTkkkqHqHqqHqpppH计算步骤：0,)1(x)()(kxf否是)(kxx)()()1()()(0)()()(minarg)(kkkkkkkkkkdxxdxfxfHdnk否是1:)()(1)()1()()()1()(kkHHHHxfxfqxxpkkkkkkkkkk)1()1(nxx1),(,)1()1(1kxfdIHn重置1001,12242min13.41)1(12221HxxxxDFP初始点方法求解：用例DFP法具有二次终止性！1294980118513617130538388630612H.0DFP),,...,1(0)(:)(kkHnkxf方法构造的则若定理)()()(kkkxfHd0)()()(kTkdxf搜索方向为下降方向110021)(min)()()1()(1)()(1)1(iiiii(i)(i)kjTiTTdxxpnkipApHnjiAppHxcxbAxxxfDFP其中则，令任取方法求解正定二次函数设用定理共轭11AHnDFP法具有二次终止性！BFGS公式)(1)(kkkqHp)(1)(kkkpBq)()()()()()()()(kkTkkTkkkkTkTkkkpBpBppBpqqqB)()()()()()()()(kkTkkTkkkkTkTkkkqHqHqqHqpppH互换)()(,kkqpBFGS修正公式DFP公式1111kkkkkBHBBB)()()()()()()()()()()()()()(11)()1(11111kTkTkkkkTkkkTkkTkkTkkkTkkBFGSkuMvMuvMMuvMqppqHHqpqpppqpqHqHHTTTSherman-Morrison公式经验表明，比DFP公式好。Broyden族BFGSkDFPkkHHH111)1(TkkDFPkvvH)()(1)()()()()()(21)()()()(kkTkkkkTkkkkTkkqHqqHqppqHqv其中Broyden族的所有成员均满足拟牛顿条件。0为保持正定性，取特点•不必计算Hesse矩阵。•当Hk0时，算法产生的方向均为下降方向，具有二次终止性。•存储量较大。拟牛顿法是无约束最优化方法中最有效的一类算法。作业P21826§5约束优化数学模型ljxhmixgtsRxxfjin,...,1,0)(,...,1,0)(..)(min}0)(;0)({xhxgxSji•一阶最优性条件(必要;充分)不等式约束问题一般约束问题•二阶最优性条件(必要;充分)RPPPP起作用约束件。解，它满足所有约束条是约束极值问题的可行假定x满足它有两种情况：来说，对某一个约束条件xxgi0)(0)(xgi一为0)(xgi一为.作用一约束起到了某种限制的进一步摄动来说，这对x效约束）；的不起作用约束（或无称这一约束为成的可行域边界上，不在由这个约束条件形xx约束）。的起作用约束（或有效称这一约束为的可行域边界上，在由这个约束条件形成xx}0)({xgiIi下降方向:处的下降方向。在为则称有若上的实函数，是定义在设定义xxfdxfdxftsRdRxRxfnnn)()()(),,0(..,00,)(:1局部概念0)(dxfT定理)()(xfdxf可行方向:表示闭包。其中处的可行方向。在为则称有若，设集合定义cl),,0(..,00,cl:2xSdSdxtsRdSxRSnn局部概念IidxgTi0)(定理0)()(xgdxgiiIixgi0)(0)(dxgi连续可行下降方向的可行下降方向。为则称又是该点的下降方向，既是该点的可行方向，，点的某一方向若xddx可行下降方向进行。继续搜索时应沿该点的小点，不是极小点，为求其极设x它不是极小点。若存在可行下降方向，极小点；方向，它就可能是局部若该点不存在可行下降来说，若对某一点*x00))(())((,)(,:GFxxIixgxIixgxxfSxii是局部最优解，则若处连续；在处可微；在处可微在设定理0)(..)(minxgtsxfi考虑问题}0)({0dxfdFT},0)({0IidxgdGTi反证法不等式约束问题的一阶最优性条件0)()(..)(0,0))(())((,)(,:)(00IiiiiiixgwxfwtsIiwwxxIixgxIixgxxfSxJohnFritz是局部最优解，则若处连续；在处可微；在处可微在设条件定理的解。无有解定理：000yyAAxGordanT条件成立。验证在点例JohnFritzxxxgxxxgtsxxfT,)2,0(0)(0)2(2)(..)(min12321120)2,,0(),,(210kkk)()(..)(0})({))(())((,)(,:)Tucker-Kuhn(IiiiiiiixgwxftsIiwxIixgxIixgxIixgxxfSx是局部最优解，则若线性无关。处连续；在处可微；在处可微在设）条件塔克（库恩定理可微00)(0)()(1iiimiiiwxgwxgwxf互补松弛条件点。是否为和验证下列两点例TKxxxxxgxxxgtsxxxf11000)(0)(..)2()(min)2()1(21222112221是不是；)2()1(xx条件的点。求满足例TKxxgxxxgtsxxxf0)(02)(..)1()(min22211221Tx)0,1(为全局最优解。条件成立，则处若在处连续；在处可微；在处可微在是凸函数设定理xTKxxIixgxIixgxxfSxgfiii))(())((,)(,,:对于凸规划，有下面的一阶充分条件：)()()()(xxxfxfxfT值凸集上求凸函数的极小一般约束问题的一阶最优性条件ljxhmixgtsRxxfjin,...,1,0)(,...,1,0)(..)(min考虑),...,1(),...,1();(ljhljhIigjji起作用约束：0)()()(..),...,1()(0,0),...,1)(())(())((,)(,:)(100xhvxgwxfwtsljvIiwwxxljxhxIixgxIixgxxfSxJohnFritzjljjIiiijijii，是局部最优解，则若处可微；在处连续；在处可微；在处可微在设条件定理0)()()(..),...,1(),(0},...,1,)()({),...,1)(())(())((,)(,:)Tucker-Kuhn(1xhvxgwxftsljvIiwxljIixhxgxljxhxIixgxIixgxxfSxjIiljjiijijijii是局部最优解，则若线性无关。，处可微；在处连续；在处可微；在处可微在设）条件塔克（库恩定理miwmixgwxhvxgwxfiiijljjmiii,...,1,0,...,1,0)(0)()()(11互补松弛条件)()()(),,(11xhvxgwxfvwxLLagrangejljjmiii函数：广义miwmixgwvwxLiiix,...,1,0,...,1,0)(0),,(ljxhmixgji,...,1,0)(,...,1,0)(为全局最优解。条件成立，则处若在处可微在处连续；在处可微；在处可微在是线性函数，是凸函数设定理xTKxxhxIixgxIixgxxfSxhgfjiiji;))(())((,)(,,,:对于凸规划，有下面的一阶充分条件：)()()()(xxxfxfxfT值凸集上求凸函数的极小02)(0)(..)1()2()(min21222112221xxxgxxxgtsxxxf求下面问题的最优解例凹函数线性函数凸函数Tx)1,1(图解：11F(x)(1,1)(2,1)fg1g2的非负线性组合表示和可以由21ggf几点说明(1)、对于凸规划，K－T条件是充分必要条件。(2)、关于“起作用约束在x*点梯度线性无关”说明x20g1x1x*=(1,0)minf(x)=-x1g1(x)=(1-x1)3-x20g2(x)=x10g3(x)=x20起作用约束为g1,g3，而f(x*)=-10g1(x*)=0-1g3(x*)=01g1g3与线性相关fg1g3,显然不能由线性表示∴x*不满足K－T条件(3)、用K－T条件解minf(x)=(x-3)20x5设K－T点为x*，f(x)=2(x-3)g1(x)=1g2(x)=-1解：写出标准形minf(x)=(x-3)2g1(x)=x0g2(x)=5-x0K－T条件2(x*-3)-w1