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

第二章优化方法的数学基础§2-1方向导数与梯度§2-2凸集、凸函数与凸规划§2-3无约束优化问题的极值条件§2-4有约束优化问题的极值条件§2-1方向导数与梯度一、函数的方向导数一个二元函数F(x1,x2)在X0点处的偏导数定义为:分别是函数在点X0处沿坐标轴方向的变化率.函数在点处沿某一方向的变化率如图2-1称它为函数沿此方向的方向导数（2-1）和也可看成是函数分别沿坐标轴方向的方向导数推导方向导数与偏导数之间的数量关系：偏导数是方向导数的特例（2-2）n元函数在点x0处沿s方向的方向导数0000012121coscoscoscosnnniiiFFFFsxxxFxxxxxxOx2x1x10x20x0x1x2sxS12图2-3二、梯度二元函数的梯度:0001212coscosFFFsxxxxx01212coscosFFxxx0010122()TFxFFFFxxxxxx为函数F(x1，x2)在x0点处的梯度。梯度的模：1212coscoscos,TFFFsxxFsFsFs2212FFFxx设12coscoss梯度方向和s方向重合时，方向导数值最大。12coscossOx2x1x0变化率为零的方向最速下降方向下降方向上升方向最速上升方向－f(x0)f(x0)梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值。图2-4梯度方向与等值线的关系000()()cos(,)TFFsFFssxxx设：则有为单位向量。多元函数的梯度0012012()TnnFxFFFFxFxxxFxxxx00001cos()()cos(,)nTiiiFFFFFssxxxxdx012201()()niiFFxxx函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。0()Fx梯度模：梯度两个重要性质：性质一函数在某点的梯度不为零，则必与过该点的等值面垂直；性质二梯度方向是函数具有最大变化率的方向。Ox2x1x0变化率为零的方向最速下降方向下降方向上升方向最速上升方向－f(x0)f(x0)图2-5梯度方向与等值面的关系例2-1求二元函数在点沿和的方向导数。解：因此，同理：例2-2求函数在点x(1)=[3,2]T的梯度。22121()44fxxxx112224()2fxxfxfxx(1)1(1)2242()24xxfxx在点x(1)=[3,2]T处的梯度为：解：12121264,42fXfXxxxxxx121211200121021644422xxxxfXxxxPfXxxfXx例2-3：试求目标函数在点处的最速下降方向。2221212143,xxxxxxf00,1TX00,1TX则函数在处的最速下降方向是解：由于当极值点X*能使f（X*）在整个可行域中为最小值时，即在整个可行域中对任一X都有f（X）≥f（X*）时，则X*就是最优点，且称为全域最优点或整体最优点。若f（X*）为局部可行域中的极小值而不是整个可行域中的最小值时，则称X*为局部最优点或相对最优点。最优化设计的目标是全域最优点。为了判断某一极值点是否为全域最优点，研究一下函数的凸性很有必要。函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。为了研究函数的凸性，现引入凸集的概念：§2-2凸集、凸函数与凸规划一、凸集设D为n维欧氏空间中的一个集合，若其中任意两点X(1)、X(2)之间的联接直线都属于D，则称这种集合D为n维欧氏空间的一个凸集。图2-6（a）是二维空间的一个凸集，而图2-6（b）不是凸集。图2-6二维空间的凸集与非凸集X（1）、X（2）两点之间的联接直线，可用数学式表达为:(1)(2)(1)XXX式中为由0到1（0≤≤1）间的任意实数。凸集的性质：1）若D为凸集，是一个实数，则集合D仍是凸集；2）若D和F均为凸集，则其和（或并）仍是凸集；3）任何一组凸集的积（或交）仍是凸集。二、凸函数具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：设f（X）为定义在n维欧氏空间中的一个凸集D上的函数，如果对任何实数α（0≤α≤1）以及对D中任意两点X(1)、X(2)恒有:(1)(2)(1)(2)((1))()(1)()fXXfXfX则f（X）为D上的凸函数，若不满足上式，则为凹函数。凸函数的几何意义如图2-7所示：图2-7一元凸函数的几何意义在凸函数曲线上取任意两点（对应于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）亦必为该凸集上的一个凸函数。4）若f（X）为定义在凸集D上且具有连续一阶导数的函数，则f（X）为凸函数的充分必要条件为：对任意两点X（1），X（2），不等式(2)(1)(2)(1)(1)()()()()TfXfXXXfX恒成立三、凸规划对于约束优化问题12min()(),..()01,2,,nnjFXFxxxXRstgXjm，，，式中若F（X）、均为凸函数，则称此问题为凸规划。()jgX凸规划的一些性质：2）凸规划问题中的任何局部最优解都是全局最优解；**()()0TFXXX1）可行域为凸集；()01,2,,jDXgXjm3）若F（X）可微，则X*为凸规划问题的最优解的充分必要条件为：对任意，对满足XD不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。注意：一、多元函数的泰勒展开21()()()()2kkTTkFFFFxxxxxxx22211220222212()FFxxxFFFxxxx111222kkxxxxxxx§2-3无约束优化问题的极值条件二元函数：多元函数泰勒展开12()[]kkTnFFFFxxxxx22221121222222122222212()()nkknnnnFFFxxxxxFFFxxxxxFHxFFFxxxxxx海色矩阵（Hessian）21()()()()2kkTTkFFFFxxxxxxx二、无约束优化问题的极值条件12()[]0TnFFFFxxxxx1.F(x)在处取得极值，其必要条件是:*x即在极值点处函数的梯度为n维零向量。例：在处梯度为但只是双曲抛物面的鞍点，而不是极小点。1212,.fxxxx*0,0TX00,00f*Xx函数的梯度为零的条件仅为必要的，而不是充分的。则称为f的驻点。*X*0fX•定义：设是D的内点，若:,nfDR*X根据函数在点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。*x为了判断从上述必要条件求得的是否是极值点，需建立极值的充分条件。*x2.处取得极值充分条件2222112122222*2122222212*()nnnnnFFFxxxxxFFFxxxxxFFFFxxxxx正定或负定xx*x，..，，各阶主子式均大于零:则海色（Hessian）矩阵是正定的,即海色（Hessian）矩阵负定的，则X*为极大点。()Hx()Hx各阶主子式负、正相间:则X*为极小点。2202220222Xf2,2,02,2,20,2,2322232132322222122312212212xfxxfxxfxxfxfxxfxxfxxfxfTxxxxxxxXf233122122,3222,2223322xxxXf21122xxxXf32223122xxxxXf22212312233223xxxxxxxx例2-4：求目标函数f（X）=的梯度和Hessian矩阵。解：因为则故Hessian阵为：例2-5求函数的极值。解：根据极值的必要条件求驻点得驻点再根据极值的充分条件，判断此点是否为极值点。由于其各阶主子式均大于零，H(x*)为正定矩阵，故X*=[2,4]T为极小点，极小值为F(X*)=-13。§2-4有约束优化问题的极值条件不等式约束的多元函数极值的必要条件是著名的库恩--塔克（Kuhn-Tucker）条件，它是非线性优化问题的重要理论1库恩—塔克条件(K-T条件）对于多元函数不等式的约束优化问题：min()Fx..()0(1,2,,)jstgjmxK-T条件可阐述为：若是一个局部极小点，则该点的目标函数梯度可表示成诸起作用约束面梯度的线性组合.即(2-17)——在设计点处的起作用约束不等式约束面数；——非负值的乘子，也称为拉格朗日乘子。式中()()0mjjjJFgxxOx1x2极值点处于等值线的中心极值点处于两个约束曲线的交点上x﹡g1(x)＝0g2(x)＝0g3(x)＝0Ox1x2x﹡g1(x)＝0g2(x)＝02有约束问题最优点的几种情况:2.有作用约束目标函数是凸函数,可行域是凸集，则目标函数等值线与作用约束曲面的切点为最优点，而且是全局最优点。1.无作用约束目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问题的最优点。x(k)为最优点x*的条件：必要条件：充分条件：Hessian矩阵H(x(k))是正定矩阵··X*f(x)·x*)()(2kxg)()(kxF)()(1kxg)()(2kxg)()(kxF)()(1kxg()()0mjjjJFgxx库恩—塔克条件的几何意义是:在约束极小值点x*处，函数F(x)的负梯度一定能表示成所有起作用约束在该点梯度（法向量）的非负线性组合。K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。对于目标函数和约束函数都是凸函数的情况，符合K-T条件的点一定是全局