02优化的数学基础

优化的数学基础本章内容•优化问题分单变量和多变量，有约束和无约束，线性和非线性问题。•无约束优化就是数学上的无条件极值，约束优化就是数学上的条件极值。•我们常见的是非线性规划问题。•本章是回顾相关的数学基础，讨论约束最优化的条件等问题第一节多元导数的方向导数与梯度方向导数一个二元函数在处的偏导数0x10101201020011,,limxxfxxxfxxfxx20102021020022,,limxxfxxxfxxfxx图2-1二维空间中的方向一个二元函数在处的沿方向d的导数0x010120210200,,limdxfxxxxfxxfdd010120210200,,limdxfxxxxfxxfdd101201020101,,limdfxxxfxxxxd10120210120202,,limdfxxxxfxxxxxd001212coscosxxffxx同理，三元函数的方向导数多元函数的方向导数0000123123coscoscosxxxxffffdxxx00001212coscoscosnxnxxxffffdxxx0n1cosiiixfx图2-2三维空间中的方向二元函数的梯度二元函数的梯度称函数在处的梯度。000011221212coscoscoscosxxxxfffffdxxxx0010122Txxfxfffxfxxx0x方向导数的几种形式：12coscosd00Txffxdd000cos,Txffxdfxfdd图2-3梯度方向与等值线的关系当在平面内画出的等值线12xx12,fxx2x12,fxxc可以看出，在等值线的切线方向d是函数变化率为零的方向，即有0x00cos,0xffxfddcos,0fd所以作业：求二元函数在处函数变化率最大的方向和数值。22121212,425fxxxxxx000Tx多元函数的梯度012012nTnxnxfxffffxfxxxxfxd方向上的方向导数00001coscos,nTiixixfffxdfxfddx12coscoscosnd012201niixffxx为梯度的模。0fx00fxpfx为梯度方向单位向量，它与函数等值面相垂直。fxc图2-5梯度方向与等值面的关系多元函数的泰勒展开一元函数在点处的泰勒展开式为fx0xx20001'''2fxfxfxxfxx其中2200,xxxxxx二元函数在点处的泰勒展开式为12,fxx01020,xxx000001210201212222221122221122,,122xxxxxfffxxfxxxxxxfffxxxxxxxx其中11102220,xxxxxx0010212222112112222221212xfxxfffxfxxxxffxxxxxxxfxxx00012TTfxfxxxGxx其二阶偏导数矩阵：又称hession矩阵02221120222212xffxxxGxffxxx00221221xxffxxxx作业求二元函数在点处的二阶泰勒展开式。22121212,425fxxxxxx1002021xxx将二元函数的泰勒展开式推广到多元函时，则在点处泰勒展开式的矩阵形式为12,,,nfxxx0x00012TfxfxfxxxGxx其中0012Tnxffffxxxx为函数在点处的梯度fx0x022221121222202122222212nnnnnxfffxxxxxfffGxxxxxxfffxxxxx若将函数的泰勒展开式只取到线性项，即取000Tzxfxfxxx则是过点和函数所代表的超曲面相切的切平面。zx0xfx第二节无约束优化的极值条件对于二元函数，若在点处取得极值，其必要条件是12,fxx01020,xxx00120xxffxx00fx为了判断从上述必要条件求得的是否是0x极值点，需要建立极值的充分条件。根据二元函数在点处的泰勒展开式，考虑上述极值必要条件，有12,fxx0x0002222212102011222211221,,22xxxffffxxfxxxxxxxxxx设000222221122,,xxxfffABCxxxx则22121020112222210201221,,221,2fxxfxxAxBxxCxfxxAxBxACBxA即要求:或表示为22121020112222210201221,,221,2fxxfxxAxBxxCxfxxAxBxACBxA121020,,0fxxfxx222122102AxBxACBxA20,0AACB02210xfx该条件反映了函数在处的各阶主子式大于0022222212120xfffxxxx02221120222212xffxxxGxffxxx02210xfx022211202222120xffxxxGxffxxx0x多元函数的极值充分条件**120Tnxffffxxxx*22221121222*22122222212nnnnnxfffxxxxxfffGxxxxxxfffxxxxx正定•函数的极小点和最小点第三节凸集、凸函数与凸规划图2-7下凸的一元函数凸集一个点集（或区域），如果连结其中任意两点和的线段全部包含在该集合内，就成该点集为凸集，否则称非凸集。凸集的概念可以用数学的语言简练地表示为：如果对一切，及一切满足的实数，点，则称集合为凸集。凸集既可以是有界的，也可以是无界的。n维空间中的维子空间也是凸集（例如三维空间中的平面）。1x2x1xR2xR01121xxyRR图2-8凸集与非凸集凸集具有以下性质：（1）若A是一个凸集，是一个实数，是凸集A中的动点，即，则集合还是凸集aaA:,AxxaaA（2）若A和B是凸集，、分别是凸集A、B中的动点，即，，则集合还是凸集。abaAbB:,,ABxxabaAbB（3）任何一组凸集的交集还是凸集。这三个性质如图所示凸集的性质凸函数函数如果在连接其凸集定义域内任意两点、的线段上，函数值总小于或等于用及作线性内插所得的值，那么称为凸函数。用数学语言表达为fx1x2x1fx2fxfx121211fxxfxfx01凸函数的定义下面给出凸函数的一些简单性质：设为定义在凸集上的一个凸函数，对任意实数，则函数也是定义在上的凸函数。设和为定义在凸集上的两个凸函数，则其和也是上的凸函数。对任意两个整数和，函数也是在上的凸函数。fxR02fx1fxfxRR12fxfxR12fxfxR凸性函数设为定义在凸集上，且具有连续一阶导数的函数，则在上为凸函数的充分必要条件是对凸集内任意不同两点、，不等式fxRfxRR1x2x21211Tfxfxxxfx这是根据函数的一阶导数信息——函数的梯度来判断函数的凸性。也可以用二阶导数信息——函数的海塞矩阵来判断函数的凸性。fxGx设为定义在凸集上且具有连续二阶导数的函数，则在上为凸函数的充分必要条件是海塞矩阵在上处处半正定。（证明从略）恒成立。fxRfxRGxR凸规划对于约束优化问题minfx..01,2,,jstgxjm若1,2,,jfxgxjm、都为凸函数，则称此问题为凸规划。凸规划有如下性质：1）若给定一点，则集合为凸集。此性质表明，当为二元函数时期等值线成大圈套小圈形式。0x0Rxfxfxfx2）可行域为凸集。0,1,2,,jRxgxjm3）凸规划的任何局部最优解就是全局最优解。第四节等式约束优化的极值条件minfx..01,2,,ksthxkm求解等式约束优化问题：需要导出极值存在的条件，这是求解等式约束优化问题的理论基础。对这一问题在数学上有两种处理方法：消元法（降维法）和拉格朗日乘子法（升维法），现分别予以介绍。消元法为了便于理解，先讨论二元函数只有一个等式约束的简单情况，即12min,fxx12..,0sthxx12xx对于n维情况12min,,nfxxx12..,,1,2,,knsthxxxkl由个约束方程将n个变量中的前个变量用其余个变量表示，即有llnl1112221212,,,,,,llnllnllllnxxxxxxxxxxxx拉格朗日乘子法拉格朗日乘子法是求解等式约束优化问题的另一种经典方法，它是通过增加变量将等式约束优化问题变成无约束优化问题。所以又称升维法。对于具有个等式约束的N维优化问题lminfx..01,2,,ksthxkl在极值点处有*x**10nTiiifdfxdxfxdxx**101,2,,nTkkikiihdhxdxhxdxklx把个等式约束给出的个分别乘以l10nkiiihdxx1,2,,kkll10niiifdxx待定系数再和相加，得31212310nlliiiiiiihhhhfdxxxxxx（2-10）可以通过其中的个方程l3121230lliiiiihhhhfxxxxx（2-11）来求解个，使得个变量的微分的系数全部为零。这样式（2-10）的等号左边就只剩下个变量的微分的项，即它变为l12,,ll12,,,ldxdxdxnl12,,,llndxdxdx31212310nlljjljjjjjhhhhfdxxxxxx（2-12）但应是任意的量，则应有12,,,llndxdxdx31212