第2章 优化方法的数学基础

第二章优化方法的数学基础§2-1方向导数与梯度§2-2目标函数的泰勒展开§2-3无约束优化问题的极值条件§2-4凸集、凸函数与凸规划§2-5有约束优化问题的极值条件§2-1方向导数与梯度010120210200(,)(,)limSFFxxxxFxxssx一、方向导数二元函数在点x0处沿某一方向s的方向导数Ox2x1x10x20x0x1x2sxS12Ox2x1x10x20x0x1x2sxS12图2-1方向导数与偏导数之间的数量关系是0001212coscosFFFsxxxxx方向导数是偏导数概念的推广。偏导数是方向导数的特例。三元函数在点处沿s方向的方向导数123f01020300000123123coscoscosFFFFsxxxxxxxn元函数在点x0处沿s方向的方向导数0000012121coscoscoscosnnniiiFFFFsxxxFxxxxxx二、梯度二元函数的梯度0001212coscosFFFsxxxxx01212coscosFFxxx0010122()TFxFFFFxxxxxx为函数F(x1，x2)在x0点处的梯度。令梯度的模：1212coscoscos,TFFFsxxFsFsFs2212FFFxx设12coscoss梯度方向和s方向重合时，方向导数值最大。12coscossOx2x1x0变化率为零的方向最速下降方向下降方向上升方向最速上升方向－f(x0)f(x0)梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值。图2-2梯度方向与等值线的关系000()()cos(,)TFFsFFssxxx设：则有为单位向量。多元函数的梯度0012012()TnnFxFFFFxFxxxFxxxx00001cos()()cos(,)nTiiiFFFsFFssxxxxx012201()()niiFFxxx函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。0()Fx梯度模：梯度两个重要性质：性质一函数在某点的梯度不为零，则必与过该点的等值面垂直；性质二梯度方向是函数具有最大变化率的方向。Ox2x1x0变化率为零的方向最速下降方向下降方向上升方向最速上升方向－f(x0)f(x0)图2-2梯度方向与等值面的关系例题2-1求函数在点[3,2]T的梯度。22121()44fxxxx112224()2fxxfxfxx(1)1(1)2242()24xxfxx在点x(1)=[3,2]T处的梯度为：解：12121264,42fXfXxxxxxx121211200121021644422xxxxfXxxxPfXxxfXx例2-2：试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。2221212143,xxxxxxf00,1TX00,1TX则函数在处的最速下降方向是解：由于10225505511151555XXe00224252514255fXefX012211222634|255XfXxxxx•新点是这个方向上的单位向量是：几个常用的梯度公式：1.002..3.2.4.2TTTfXCfXCfXbXfXbfXXXfXXQfXXQXfXQX常数则，即，则，则，对称矩阵。则，cxaxxxfniiin121nTaaaa21外，最简单最重要的一类就是二次函数。在n元函数中，除了线形函数：2-2目标函数的泰勒展开或f(X)=aX+ccxbxxgxxxfniiininjjiijn1112121,,其中均为常数。cbgiij,,jiijgg若，X≠0，均有＞0，则称矩阵Q是正定的。nXRTXQX在代数学中将特殊的二次函数称为二次型。对于二次函数，我们更关心的是Q为正定矩阵的情形。12TfXXQX12TTfXXQXbXc若，且X≠0，均有＜0，则称Q是负定的。nXRTXQX定义：设Q为n×n对称矩阵nnnnnnggggggggg212222111211nbbb21其中Q=b=Q为对称矩阵其向量矩阵表示形式是：二次函数的一般形式为：660633032631320100104解：对称矩阵Q的三个主子式依次为：401023136例：判定矩阵Q=是否正定一个n×n对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶主子式都是正的。一个n×n对称矩阵Q是负定矩阵的充要条件是矩阵Q的各阶主子式的值负、正相间。因此知矩阵Q是正定的。12TfZXQXbXc定理：若二次函数中Q正定，则它的等值面是同心椭球面族，且中心为*1XQb证明：作变换，代入二次函数式中：1XYQbbQYfY1cbQYbbQYQbQYTT11121cbQbQYYTT12121根据解析几何知识，Q为正定矩阵的二次型的等值面是以坐标原点为中心的同心椭球面族。由于上式中的是常数，所以的等值面也是以=0为中心的同心椭球面族，回到原坐标系中去，原二次函数就是以为中心的同心椭球面族。QYYT210Y112TbQbcYY*1XQb前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。特别地若算法对于Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。另外，这族椭球面的中心恰是二次目标函数的唯一极小点。*1XQb一、二元函数的泰勒展开01020(,)xxx000001210201212222221122221122(,)(,)122fffxxfxxfff11012202xxxxxxx二元函数：二元函数在点处的泰勒展开式为12(,)fxx000001210201212222221122221122122fffffff0102122221121122222212000()()121()()()2xTTxfffxfxxxxffxxxxxxxffxxxfxfxxxGxx02221120222212()xffxxxGffxxxx11012202xxxxxxx二元函数：二元函数：在点X0处0()Gx0()Gx00221221xxffxxxx称作海赛矩阵。所以矩阵为对称方阵。由于函数的二次连续性，有对二次函数：12TTfXXQXbXcQ为二次函数的海赛（Hessian）矩阵，常量矩阵。kkfXQXb二次函数的梯度为：二、多元函数泰勒展开0012()[]Tnffffxxxxx02222112122222122222212()nknnnnxfffxxxxxfffxxxxxGfffxxxxxx0001()()()()2TTfffGxxxxxxx()fx为函数在点的海赛矩阵（Hessia）0x2202220222Xf2,2,20,2,2232322222312212212xfxxfxfxxfxxfxfTxxxxxxxXf233122122,3222,2223322xxxXf21122xxxXf32223122xxxxXf22212312233223xxxxxxxx例：求目标函数f（X）=的梯度和Hesse矩阵。解：因为则又因为：故Hesse阵为：(1)12(1)2660120()06600xfxxx例题:(1)()3fx(1)211(1)2220369()336xxfxxxx332212121()339fxxxxxx用泰勒展开将函数(1)[1,1]Tx在点简化成线性函数与二次函数。(1)x解：函数在点的函数值、梯度和二阶导数矩阵：11(1)221111xxxxxx简化的线性函数(1)(1)(1)22()()()[]33(1)36Tfffxxxxxxx简化的二次函数(1)(1)(1)(1)2(1)(1)1()()()[][]()[]2TTfffxfxxxxxxxxx2212112366(1)6123xxxxx§2-3无约束优化问题的极值条件()0()0fxfx()0()0fxfx()0()0fxfx图2-3一元函数的极值点图2-4二元函数的极值点001200()0xxffxxfx即图2-5驻点不是极值点而是鞍点001200()0xxffxxfx无约束优化问题的极值必要条件12()[]0TnFFFFxxxxx即F(x)在处取得极值，其必要条件是:*x即在极值点处函数的梯度为n维零向量。有了必要条件，那么充分条件是什么呢？根据二元函数的泰勒展开式和极值的必要条件000001210201212222221122221122122fffffff000222221122,,fffABC22121020112222210201221221()()2ffABCfABACBA20,0AACB