2优化方法的数学基础1

第二章优化方法的数学基础§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常数则，即，则，则，对称矩阵。则，当极值点X*能使f（X*）在整个可行域中为最小值时，即在整个可行域中对任一X都有f（X）≥f（X*）时，则X*就是最优点，且称为全域最优点或整体最优点。若f（X*）为局部可行域中的极小值而不是整个可行域中的最小值时，则称X*为局部最优点或相对最优点。最优化设计的目标是全域最优点。为了判断某一极值点是否为全域最优点，研究一下函数的凸性很有必要。函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。为了研究函数的凸性，现引入凸集的概念：§2-2凸集、凸函数与凸规划一、凸集设D为n维欧氏空间中的一个集合，若其中任意两点X(1)、X(2)之间的联接直线都属于D，则称这种集合D为n维欧氏空间的一个凸集。图2-3（a）是二维空间的一个凸集，而图2-3（b）不是凸集。图2-3二维空间的凸集与非凸集X（1）、X（2）两点之间的联接直线，可用数学式表达为:(1)(2)(1)XXX式中为由0到1（0≤≤1）间的任意实数。凸集的性质：1）若D为凸集，是一个实数，则集合D仍是凸集；2）若D和F均为凸集，则其和（或并）仍是凸集；3）任何一组凸集的积（或交）仍是凸集。二、凸函数具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：设f（X）为定义在n维欧氏空间中的一个凸集D上的函数，如果对任何实数a（0a1）以及对D中任意两点X(1)、X(2)恒有:(1)(2)(1)(2)((1))()(1)()fXXfXfX则f（X）为D上的凸函数，若不满足上式，则为凹函数。凸函数的集合意义如图2-4所示：图2-4一元凸函数的几何意义在凸函数曲线上取任意两点（对应于X轴上的坐标X(1)、X（2））联成一直线线段，则该线段上任一点（对应于X轴上的X(k)点）的纵坐标Y值必大于或等于该点（X(k)）处的原函数值f(X(k))。凸函数的一些性质：1）若f（X）为定义在凸集D上的一个凸函数，且a是一个正数（a0），则af（X）也必是定义在凸集D上的凸函数；3）若f1(X），f2(X)为定义在凸集D上的两个凸函数，α和β为两个任意正数，则函数afl（X）＋βf2(X)仍为D上的凸函数。2）定义在凸集D上的两个凸函数f1(X），f2(X)，其和f（X）=f1（X）十f2（X）亦必为该凸集上的一个凸函数；1）若f（X）为定义在凸集D上且具有连续一阶导数的函数，则f（X）为凸函数的充分必要条件为：对任意两点X（1），X（2），不等式三、凸性条件(2)(1)(2)(1)(1)()()()()TfXfXXXfX恒成立2）设f（X）为定义在凸集R上具有连续二阶导数的函数，则f（X）在R上为凸函数的充分必要条件是海赛矩阵G(X)在R上处处半正定。四、凸规划对于约束优化问题12min()(),..()01,2,,nnjFXFxxxXRstgXjm，，，式中若F（X）、均为凸函数，则称此问题为凸规划。()jgX不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。注意：cxaxxxfniiin121nTaaaa21外，最简单最重要的一类就是二次函数。在n元函数中，除了线形函数：或f(X)=aX+c§2-3二次函数及正定矩阵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是正定的。定理：若二次函数中Q正定，则它的等值面是同心椭球面族，且中心为12TfZXQXbXc*1XQb证明：作变换，代入二次函数式中：1XYQbbQYfY1cbQYbbQYQbQYTT11121cbQbQYYTT12121根据解析几何知识，Q为正定矩阵的二次型的等值面是以坐标原点为中心的同心椭球面族。由于上式中的是常数，所以的等值面也是以=0为中心的同心椭球面族，回到原坐标系中去，原二次函数就是以为中心的同心椭球面族。QYYT210Y112TbQbcYY*1XQb前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。特别地若算法对于Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。另外，这族椭球面的中心恰是二次目标函数的唯一极小点。*1XQb例：把二次函数化为矩阵向量形式并检验Q是否正定，如正定，试用公式求这个函数的极小点。222123123121312,,32345fxxxxxxxxxxxx*1XQb12312TTfxxxXQXbX1031031021031023101210210121081Q极小点是==*XbQ1707682解：展开321321321333231232221131211321,,,,21xxxbbbxxxgggggggggxxx=332211322331132112233322222111212121xbxbxbxxgxxgxxgxgxgxg=401023136054与题中函数比较各项系数为：Q=b=由前例知Q正定一、多元函数的泰勒展开000002222212102012112222121122122fffffff22211220222212()FFxxxFFFxxx