第二章优化方法的数学基础课件.ppt

1、2-1 2-1 方向导数与梯度方向导数与梯度2-2 2-2 凸集、凸函数与凸规划凸集、凸函数与凸规划2-3 2-3 无约束优化问题的极值条件无约束优化问题的极值条件 2-4 2-4 有约束优化问题的极值条件有约束优化问题的极值条件 一、函数的方向导数一、函数的方向导数一个二元函数一个二元函数F(x1,x2)在在X0点处的偏导数定义为点处的偏导数定义为:分别是函数在点分别是函数在点X0处沿坐标轴方向的变化率处沿坐标轴方向的变化率.1020102101010),(),(lim)(1xxxFxxxFxFxX2020120201020),(),(lim)(2xxxFxxxFxFxX),(),(lim)

2、(020120210100 xxfxxxxFFSX2221)()(xx函数 在点 处沿某一方向的变化率如图2-1),(21xxF0X称它为函数沿此方向的方向导数（2-1）和 也可看成是函数分别沿坐标轴方向的方向导数推导方向导数与偏导数之间的数量关系：10)(xFX20)(xFX偏导数是方向导数的特例),(),(lim)(020120210100 xxFxxxxFFSX22021012021010110201021010),(),(lim),(),(limxxxxxFxxxxFxxxxFxxxF220110cos)(cos)(xFxFXX（2-2）n元函数在点元函数在点x0处沿处沿s s方向的方

3、向导数方向的方向导数 0000012121coscoscoscosnnniiiFFFFsxxxFxxxxxxOx2x1x10 x20 x0 x1 x2 sxS 1 2图图2-3二元函数的梯度:0001212coscosFFFsxxxxx01212coscosFFxxx0010122()TFxFFFFxxxxxx为函数F(x1，x2)在x0点处的梯度。梯度的模：1212coscoscos,TFFFsxxFsFsF s 2212FFFxx设12coscoss梯度方向和s方向重合时，方向导数值最大。12coscoss 而梯度而梯度的模就是函数变化率的最大值的模就是函数变化率的最大值。图图2-4 梯度

4、方向与等值线的关系梯度方向与等值线的关系000()()cos(,)TFFsFF ss xxx设：设：则有则有 为单位向量。为单位向量。0012012()TnnFxFFFFxFxxxFxxxx00001cos()()cos(,)nTiiiFFFFF ssx xxxdx012201()()niiFFxxx函数的梯度方向与函数等值面相垂直，也就是和等函数的梯度方向与函数等值面相垂直，也就是和等值面上过值面上过x0的一切曲线相垂直。的一切曲线相垂直。由于梯度的模因点而异，即函数在不同点处的最大由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种变化率是不同的。因此，梯度是

5、函数的一种局部性局部性质质。0()Fxl梯度梯度 模：模：图图2-5 梯度方向与等值面的关系梯度方向与等值面的关系例例2-1 求二元函数 在点 沿 和 的方向导数。4)(221xxFX T1,10X44211S63212S解解：21212142)()()(xxxxFxFFXXX T1,10X42)(0XF 因此，666.14cos44cos2cos)(cos)()(22011010 xFxFFXXSX 同理：465.16cos43cos2)(20SXF求函数求函数 在点在点x(1)=3,2T 的的 梯度。梯度。22121()44fxxxx112224()2fxxfxfxx(1)1(1)2242

6、()24xxfx x在点在点x(1)=3,2T处的梯度为：处的梯度为：l解：解：12121264,42fXfXxxxxxx 121211200121021644422xxxxfXxxxPfXxxfXx：试求目标函数：试求目标函数 在点在点 处的处的最速下降方向。最速下降方向。2221212143,xxxxxxf00,1TX00,1TX则函数在则函数在 处的最速下降方向是处的最速下降方向是解：解：由于由于 当极值点当极值点X X*能使能使f f（X X*）在整个可行域中为最小值时，即在整）在整个可行域中为最小值时，即在整个可行域中对任一个可行域中对任一X X都有都有f f（X X）f f（X X

7、*）时，则）时，则X X*就是最优点，就是最优点，且称为且称为。若。若f f（X X*）为局部可行域中的）为局部可行域中的极小值而不是整个可行域中的最小值时，则称极小值而不是整个可行域中的最小值时，则称X X*为为。最优化设计的目标是全域最优点。为了判断某一极。最优化设计的目标是全域最优点。为了判断某一极值点是否为全域最优点，研究一下函数的凸性很有必要。值点是否为全域最优点，研究一下函数的凸性很有必要。函数的凸性表现为单峰性。对于具有凸性特点的函数来说，函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。其极值点只有一个，因而该点既是局部

8、最优点亦为全域最优点。为了研究函数的凸性，现引入凸集的概念：为了研究函数的凸性，现引入凸集的概念：设设D D为为n n维欧氏空间中的一个集合，若其中任意两点维欧氏空间中的一个集合，若其中任意两点X X(1)(1)、X X(2)(2)之间的联接直线都属于之间的联接直线都属于D D，则称这种集合，则称这种集合D D为为n n维维欧氏空间的一个凸集。图欧氏空间的一个凸集。图2-62-6（a a）是二维空间的一个凸集，）是二维空间的一个凸集，而图而图2-62-6（b b）不是凸集。）不是凸集。图图2-6二维空间的凸集与非凸集二维空间的凸集与非凸集X X（1 1）、X X（2 2）两点之间的联接直线，可

9、用数学式表达为两点之间的联接直线，可用数学式表达为:(1)(2)(1)XXX式中式中 为由为由0 0到到1 1（0 10 1）间的任意实数。）间的任意实数。凸集的性质：凸集的性质：1 1）若）若D D为凸集，为凸集，是一个实数，则集合是一个实数，则集合 D D仍是凸集；仍是凸集；2 2）若）若D D和和F F均为凸集，则其和（或并）仍是凸集；均为凸集，则其和（或并）仍是凸集；3 3）任何一组凸集的积（或交）仍是凸集。）任何一组凸集的积（或交）仍是凸集。具有凸性（表现为单峰性）或只有唯一的局部最优值具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为亦即全域最优值的函数，称为

10、。其数学。其数学定义是定义是：设设 f f（X X）为定义在）为定义在 n n维欧氏空间中的一个凸集维欧氏空间中的一个凸集D D上的函数，上的函数，如果对任何实数如果对任何实数（0 1）以及对）以及对D D中任意两点中任意两点X X(1)(1)、X X(2)2)恒有恒有:(1)(2)(1)(2)(1)()(1)()fXXf Xf X 则则f f（X X）为）为D D上的上的凸函数凸函数，若不满足上式，则为若不满足上式，则为凹函数凹函数。凸函数凸函数的几何意义如图的几何意义如图2-72-7所示：所示：图图2-7 一元凸函数的几何意义一元凸函数的几何意义 在凸函数曲线上取任意两点（对应于在凸函数曲

11、线上取任意两点（对应于X轴上的坐标轴上的坐标X(1)、X（2）联成一直线线段，则该线段上任一点（对应于）联成一直线线段，则该线段上任一点（对应于X轴上轴上的的X(k)点）的纵坐标点）的纵坐标Y值必大于或等于该点（值必大于或等于该点（X(k)）处的原函）处的原函数值数值f(X(k)。凸函数的一些性质：凸函数的一些性质：1 1）若）若 f（X）为定义在凸集）为定义在凸集D D上的一个凸函数，且上的一个凸函数，且 a是一个是一个正数（正数（a 0），则），则 af（X）也必是定义在凸集）也必是定义在凸集D D上的凸函数；上的凸函数；3 3）若若f f1 1(X X），），f f2 2(X X)为定义

12、在凸集为定义在凸集D D上的两个凸函数，上的两个凸函数，和和为两个任意正数，则函数为两个任意正数，则函数 afafl l（X X）ff2 2(X X)仍为仍为D D上的凸函数上的凸函数。2 2）定义在凸集定义在凸集D D上的两个凸函数上的两个凸函数f f1 1(X X），），f f2 2(X X)，其和，其和 f f（X X）=f=f1 1（X X）十）十f f2 2（X X）亦必为该凸集上的一个凸函数。）亦必为该凸集上的一个凸函数。4 4）若若f f（X X）为定义在凸集）为定义在凸集D D上且具有连续一阶导数的函上且具有连续一阶导数的函数，则数，则f f（X X）为凸函数的充分必要条件为：

13、）为凸函数的充分必要条件为：对任意两点对任意两点X X（1 1），X X（2 2），不等式，不等式(2)(1)(2)(1)(1)()()()()Tf Xf XXXf X恒成立恒成立 对于约束优化问题对于约束优化问题12min()(),.()01,2,nnjF XF xxxXRstgXjm，式中若式中若F F（X X）、均均为凸函数，为凸函数，则称此问题为则称此问题为。()jgX凸规划的一些性质：凸规划的一些性质：2 2）凸规划问题中的任何局部最优解都是全局最优解凸规划问题中的任何局部最优解都是全局最优解；*()()0TF XXX 1 1）可行域）可行域 为凸集；为凸集；()01,2,jDX g

14、Xjm 3 3）若若F F（X X）可微可微，则，则X X*为凸为凸规划问题规划问题的的最优解的最优解的充分必充分必要条件为：要条件为：对任意对任意 ，对满足对满足XD 不论是无约束或有约束的优化问题，在实际应用中，要证不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就

15、不必花精力进行求证，而通常是从几个初始点出发，找中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。出几个局部最优解，从中选择目标函数值最好的解。21()()()()2kkTTkFFFF xxxxxxx22211220222212()FFxx xFFFx xx x111222kkxxxxxx x二元函数：二元函数：12()kkTnFFFFxxxxx22221121222222122222212()()nkknnnnFFFxx xx xFFFxxxxxFH xFFFxxxxx x海色矩阵海色矩阵（Hessian）21()()()()2kkTTkFF

16、FF xxxxxxx12()0TnFFFFxxxxx1.F(x)在在 处取得极值，其必要条件是处取得极值，其必要条件是:*x即在极值点处函数的梯度为即在极值点处函数的梯度为n维零向量。维零向量。l例：例：在在 处梯度为处梯度为l但但 只是双曲抛物面的鞍点，而不是极小点。只是双曲抛物面的鞍点，而不是极小点。1212,.f x xx x*0,0TX 00,00f *Xx 则称则称 为为f的的。*X*0fX定义：设定义：设 是是D的内点，若的内点，若:,nfDR*Xl根据函数在根据函数在 点处的泰勒展开式，考虑上述极点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。值必要条件，可得相应的充

17、分条件。*x 为了判断从上述必要条件求得的为了判断从上述必要条件求得的 是否是极值是否是极值点，需建立极值的充分条件。点，需建立极值的充分条件。*x2222112122222*2122222212*()nnnnnFFFxx xx xFFFx xxx xFFFFx xx xx 正定或负定xx*x022211211aaaa011a0333231232221131211aaaaaaaaa0212222111211nnnnnnaaaaaaaaa，.，各阶主子式均大于零各阶主子式均大于零:则海色（则海色（Hessian）矩阵）矩阵 是是正定正定的的,即海色（即海色（Hessian）矩阵）矩阵 ，则，则X

18、*为为。()Hx()Hx 各阶主子式负、正相间各阶主子式负、正相间:则则X*为为。2202220222Xf2,2,02,2,20,2,2322232132322222122312212212xfxxfxxfxxfxfxxfxxfxxfxf TxxxxxxxXf233122122,3222,22 23322xxxXf 21122xxxXf 32223122xxxxXf2221231 22 33223xxxxxx xx例例2-4：求目标函数：求目标函数f（X）=的梯度和的梯度和矩阵。矩阵。解：因为解：因为 则则故故阵为：阵为：例例2-5 求函数 的极值。解解：根据极值的必要条件求驻点得驻点 再根据

19、极值的充分条件，判断此点是否为极值点。由于其各阶主子式均大于零，H(x*)为正定矩阵，故X*=2,4T为极小点，极小值为F(X*)=-13。784),(21222121xxxxxxF082)(042)(2211xxFxxFXXTX4,2*2002)()()()()(22*212*221*221*2*xFxxFxxFxFHXXXXX02 042002l 不等式约束的多元函数极值的必要条件是著名的不等式约束的多元函数极值的必要条件是著名的库恩库恩-塔克（塔克（Kuhn-Tucker）条件，它是非线性优化）条件，它是非线性优化问题的重要理论问题的重要理论1 库恩库恩塔克条件塔克条件(K-T条件）条件

20、）l对于多元函数不等式的约束优化问题：对于多元函数不等式的约束优化问题：l min()F x.()0(1,2,)jst gjmxlK-T条件可阐述为：l若 是一个局部极小点，则该点的目标函数梯度 可表示成诸起作用约束面梯度 的线性组合.l即*X)(*XF)(*Xug (2-17)m在设计点处的起作用约束不等式约束面数；),2,1(mjj非负值的乘子，也称为拉格朗日乘子。式中()()0mjjj JFgxxOx1x2极值点处于等值线的中心极值点处于两个约束曲线的交点上xg1(x)0g2(x)0g3(x)0Ox1x2xg1(x)0g2(x)00)()(kxf2 2 有约束问题最优点的几种情况有约束问

21、题最优点的几种情况:2.2.有有作用约束作用约束 目标函数是凸函数目标函数是凸函数,可行域是凸可行域是凸集，则目标函数等值线与集，则目标函数等值线与作用约作用约束束曲面的切点为最优点，而且是曲面的切点为最优点，而且是全局最优点。全局最优点。1.1.无作用约束无作用约束 目标函数是凸函数，可行域是凸目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约集，则最优点是内点。相当于无约束问题的最优点。束问题的最优点。x x(k)(k)为最优点为最优点x x*的条件：的条件：必要条件：必要条件：充分条件：充分条件：Hessian矩阵矩阵 H(xH(x(k)(k)是正定矩阵是正定矩阵X*0X1X2g

22、3(x)=0g2(x)=0g1(x)=0f(x)x*)()(2kxg)()(kxF)()(1kxg)()(2kxg)()(kxF)()(1kxg()()0mjjj JFgxx 库恩库恩塔克条件的几何意义是塔克条件的几何意义是:在约束极小值点在约束极小值点 x*处，处，函数函数F(x)的负梯度一定能表示成所有起作用约束在该的负梯度一定能表示成所有起作用约束在该点梯度（法向量）的非负线性组合。点梯度（法向量）的非负线性组合。是多元函数取得约束极值的是多元函数取得约束极值的,以用来作为约束极值的判断条件，以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。又可以来直接求解较简单的约束

23、优化问题。这种情况这种情况K-TK-T条件即为多元函数取条件即为多元函数取得约束极值的充分必要条件。得约束极值的充分必要条件。K-T K-T条件是多元函数取得约束极值的必要条件条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。求解较简单的约束优化问题。例例2-6 2-6 库恩库恩塔克（塔克（K-TK-T）条件应用举例）条件应用举例 2212()(2)minfxxx21122231()1 0()0()0gxxgxgx xxxls.tl判断判断1 0T是否为约束最优点。是否为约束最优点。1211202

24、(2)2()02xxxfxx1211022()11ixxxg x20()1gx(1)当前点当前点 为可行点，因满足约束条件为可行点，因满足约束条件(1)10Tx(1)1(1)2(1)3()0()0()10ggg xxx(3)各函数的梯度：各函数的梯度：（2）在）在 起作用约束为起作用约束为g1和和g2,因因 (1)10Tx(1)3()0gx1122()()()fggxxx121010（4）求拉格朗日乘子）求拉格朗日乘子l由于拉格朗日乘子均为非负，说明由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足是一个局部最优点，因为它满足K-T条件。条件。(1)1 0Tx10 120 221221

25、2min()(2)fxxx21122231()1 0()0()0gxxgxgx xxxls.t例例2-7 对于约束极值问题2221)3()(minxxFXs.t.04)(2211xxgX0)(22xgX0)(13xg X试运用K-T条件验证点T0,2*X为约束极值点。解解：图例例2-7给出了由g1(x)=0、g2(x)=0、g3(x)=0、及所确定的可行域，同时给出了的几条等值线。0404)(1Xg0)(2Xg02)(3Xg可见起作用的约束函数是)(1Xg和)(2XgT0,2*X1.计算点 的各个约束函数值例例-7约束极值问题约束极值问题2、求相关函数在 点的梯度3、将梯度代入判别公式，求拉格

26、朗日乘子 TTxxF0,22),3(2)(21*XTTxg1,41,2)(1*1XTg1,0)(*2X)()()(*22*11*XXXggF10140221即 5.05.0004221211T0,2*X 12均为非负，满足K-T条件，因此T0,2*X同时，由于)(XF是凸函数，可行域是凸集，因此点*X也是全域最优点。为约束极值点。和2221)1()(minxxXF0)(0)(01)(.13222211xXgxXgxxXgts)(KX设约束优化问题设约束优化问题 (课堂练习课堂练习)它的当前迭代点为它的当前迭代点为=1,0T，试用，试用KT条件条件。判断它是否为约束最优点判断它是否为约束最优点解

27、：解：)(KX1)(0)(011)(3221XgXgXg)(KX)(KX222211)(1)(xXgxxXg点的诸约束函数值点的诸约束函数值点是可行点。点是可行点。点的起作用约束是：点的起作用约束是：1 计算计算2求求)(KX002)1(2)()0,1(21)(xxXFK1212)()0,1(1)(1xXgK1010)()0,1()(2KXg0)()()()(22)(11)(KKKXgXgXF0101200213求求点的诸梯度点的诸梯度4求拉格朗日乘子求拉格朗日乘子0022110102)(KX写成线性方程组写成线性方程组解得：解得：乘子均为非负，乘子均为非负，=1,0T满足约束最优解的一阶必要条件。满足约束最优解的一阶必要条件。由于由于F(X)是凸函数，可行域为凸集，所以点是凸函数，可行域为凸集，所以点)(KX也是该问题的全局最优解。也是该问题的全局最优解。004.866)(min2121212221xxxxtsxxxxxf点。为检验TKXT2,2