《最优化方法》课程复习考试

《最优化方法》复习提要第一章最优化问题与数学预备知识§1.1模型无约束最优化问题12min(),(,,,)TnnfxxxxxR．约束最优化问题（},,2,1,0)(;,,2,1,0)(,|{ljxhmixgRxxSjin）min();...fxstxS即min();..()0,1,2,,,()0,1,2,,.ijfxstgximhxjl其中()fx称为目标函数，12,,,nxxx称为决策变量，S称为可行域，()0(1,2,,),()0(1,2,,)ijgximhxjl称为约束条件．§1.2多元函数的梯度、Hesse矩阵及Taylor公式定义设:,nnfRRxR．如果n维向量p，nxR，有()()()Tfxxfxpxox．则称()fx在点x处可微，并称()Tdfxpx为()fx在点x处的微分．如果()fx在点x处对于12(,,,)Tnxxxx的各分量的偏导数(),1,2,,ifxinx都存在，则称()fx在点x处一阶可导，并称向量12()()()()(,,,)Tnfxfxfxfxxxx为()fx在点x处一阶导数或梯度．定理1设:,nnfRRxR．如果()fx在点x处可微，则()fx在点x处梯度()fx存在，并且有()()Tdfxfxx．定义设:,nnfRRxR．d是给定的n维非零向量，ded．如果0()()lim()fxefxR存在，则称此极限为()fx在点x沿方向d的方向导数，记作()fxd．定理2设:,nnfRRxR．如果()fx在点x处可微，则()fx在点x处沿任何非零方向d的方向导数存在，且()()Tfxfxed，其中ded．定义设()fx是nR上的连续函数，nxR．d是n维非零向量．如果0，使得(0,)，有()fxd（）()fx．则称d为()fx在点x处的下降（上升）方向．定理3设:,nnfRRxR，且()fx在点x处可微，如果非零向量ndR，使得()Tfxd（）0，则d是()fx在点x处的下降（上升）方向．定义设:,nnfRRxR．如果()fx在点x处对于自变量12(,,,)Tnxxxx的各分量的二阶偏导数2()(,1,2,,)ijfxijnxx都存在，则称函数()fx在点x处二阶可导，并称矩阵22221121222222122222212()()()()()()()()()()nnnnnfxfxfxxxxxxfxfxfxfxxxxxxfxfxfxxxxxx为()fx在点x处的二阶导数矩阵或Hesse矩阵．定义设:,nmnhRRxR，记12()((),(),,())Tmhxhxhxhx，如果()(1,2,,)ihxim在点x处对于自变量12(,,,)Tnxxxx的各分量的偏导数()(1,2,,;1,2,,)ijhximjnx都存在，则称向量函数()hx在点x处是一阶可导的，并且称矩阵111122221212()()()()()()()()()()nnmnmmmnhxhxhxxxxhxhxhxxxxhxhxhxhxxxx为()hx在点x处的一阶导数矩阵或Jacobi矩阵，简记为()hx．例2设,,nnaRxRbR，求()Tfxaxb在任意点x处的梯度和Hesse矩阵．解设1212(,,,),(,,,)TTnnaaaaxxxx，则1()nkkkfxaxb，因()(1,2,,)kkfxaknx，故得()fxa．又因2()0(,1,2,,)ijfxijnxx，则2()fxO．例3设nnQR是对称矩阵，,nbRcR，称1()2TTfxxQxbxc为二次函数，求()fx在任意点x处的梯度和Hesse矩阵．解设1212(),(,,,),(,,,)TTijnnnnQqxxxxbbbb，则121111(,,,)2nnnnijijkkijkfxxxqxxbxc，从而111111111()()()nnjjjjjjnnnnjjnnjjjjnfxqxbqxxbfxQxbfxbqxbqxx．再对1()(1,2,,)nijjijifxqxbinx求偏导得到2()(,1,2,,)ijijfxqijnxx，于是1112121222212()nnnnnnqqqqqqfxQqqq．例4设()()tfxtd，其中:nfRR二阶可导，,,nnxRdRtR，试求(),()tt．解由多元复合函数微分法知2()(),()()TTtfxtddtdfxtdd．定理4设:,nnfRRxR，且()fx在点x的某邻域内具有二阶连续偏导数，则()fx在点x处有Taylor展式21()()()(),(01)2TTfxxfxfxxxfxxx．证明设()(),[0,1]tfxtxt，则(0)(),(1)()fxfxx．按一元函数Taylor公式()t在0t处展开，有21()(0)(0)(),(0)2tttt．从例4得知2(0)(),()()()TTfxxxfxxx．令1t，有21()()()(),(01)2TTfxxfxfxxxfxxx．根据定理1和定理4，我们有如下两个公式()()()()()Tfxfxfxxxoxx，221()()()()()()()()2TTfxfxfxxxxxfxxxoxx．§1.3最优化的基本术语定义设:nfRR为目标函数，nSR为可行域，xS．（1）若xS，都有()()fxfx，则称x为()fx在S上的全局（或整体）极小点，或者说，x是约束最优化问题min()xSfx的全局（或整体）最优解，并称()fx为其最优值．（2）若,xSxx，都有()()fxfx，则称x为()fx在S上的严格全局（或整体）极小点．（3）若x的邻域(){}(0)nNxxRxx使得()xNxS，都有()()fxfx，则称x为()fx在S上的局部极小点，或者说，x是约束最优化问题min()xSfx的局部最优解．（4）若x的邻域()(0)Nx使得(),xNxSxx，都有()()fxfx，则称x为()fx在S上的严格局部极小点．第二章最优性条件§2.1无约束最优化问题的最优性条件定理1设:nfRR在点x处可微，若x是问题min()fx的局部极小点，则()0fx．定义设:()nfSRR在intxS处可微，若()0fx，则称x为()fx的平稳点．定理2设:nfRR在点x处具有二阶连续偏导数，若x是问题min()fx的局部极小点，则()0fx，且2()fx半正定．定理3设:nfRR在点x处具有二阶连续偏导数，若()0fx，且2()fx正定，则x是问题min()fx的严格局部极小点．注：定理2不是充分条件，定理3不是必要条件．例1对于无约束最优化问题2312min()fxxx，其中212(,)TxxxR，显然2212()(2,3),TfxxxxR，令()0fx，得()fx的平稳点(0,0)Tx，而且2222020(),()0600fxfxx．易见2()fx为半正定矩阵．但是，在x的任意邻域xx，总可以取到(0,)2Tx，使()()fxfx，即x不是局部极小点．例2对于无约束最优化问题42241122min()2fxxxxx，其中212(,)TxxxR，易知3223112122()(44,44)Tfxxxxxxx，从而得平稳点(0,0)Tx，并且22221212221212001248(),()008412xxxxfxfxxxxx．显然2()fx不是正定矩阵．但是，22212()()fxxx在x处取最小值，即x为严格局部极小点．例3求解下面无约束最优化问题332122111min()33fxxxxx，其中212(,)TxxxR，解因为21212222201(),()0222xxfxfxxxx，所以令()0fx，有2122210,20.xxx解此方程组得到()fx的平稳点(1)(2)(3)(4)1111,,,0202xxxx．从而2(1)2(2)2020(),()0202fxfx，2(3)2(4)2020(),()0202fxfx．由于2(1)()fx和2(4)()fx是不定的，因此(1)x和(4)x不是极值点．2(3)()fx是负定的，故(3)x不是极值点，实际上它是极大点．2(2)()fx是正定的，从而(2)x是严格局部极小点．定理4设:nfRR是凸函数，且()fx在点nxR处可微，若()0fx，则x为min()fx的全局极小点．推论5设:nfRR是凸函数，且()fx在点nxR处可微．则x为min()fx的全局极小点的充分必要条件是()0fx．例4试证正定二次函数1()2TTfxxQxbxc有唯一的严格全局极小点1xQb，其中Q为n阶正定矩阵．证明因为Q为正定矩阵，且(),nfxQxbxR，所以得()fx的唯一平稳点1xQb．又由于()fx是严格凸函数，因此由定理4知，x是()fx的严格全局极小点．§2.2等式约束最优化问题的最优性条件定理1设:nfRR在点x处可微，:(1,2,,)njhRRjl在点x处具有一阶连续偏导数，向量组12(),(),,()lhxhxhx线性无关．若x是问题min();..()0,1,2,,jfxsthxjl的局部极小点，则,1,2,,jvRjl，使得1()()0ljjjfxvhx．称(,)()()TLxvfxvhx为Lagrange函数，其中12()((),(),,())Tlhxhxhxhx．称12(,,,)Tlvvvv为Lagrange乘子向量．易见(,)xvLLxvL，这里1(,)()(),(,)()lxjjvjLxvfxvhxLxvhx．定理2设:nfRR和:(1,2,,)njhRRjl在点nxR处具有二阶连续偏导数，若lvR，使得(,)0xLxv，并且，,0nzRz，只要()0,1,2,,Tjzhxjl，便有2(,)0TxxzLxvz，则x是问题min();..()0,1,2,,jfxsthxjl的严格局部极小点．例1试用最优性条件求解221212min();..()80.fxxxsthxxx解Lagrange函数为221212(,)(8)Lxvxxvxx，则1221122(,)2(8)xvxLxvxvxxx，从而得(,)Lxv的平稳点(8,8,2)T和(8,8,2)T，对应有(8,8),2Txv和(8,8),2Txv．由于2