2022年最优化问题与数学预备知识 .pdf

第一章最优化问题与数学预备知识本章主要内容：最优化的概念经典最优化中两种类型的问题无约束极值问题、具有等式约束的极值问题的求解方法最优化问题的模型及分类向量函数微分学的有关知识最优化的基本术语教学目的及要求： 理解最优化的概念， 掌握经典最优化中两种类型的问题无约束极值问题、具有等式约束的极值问题的求解方法，了解最优化问题的模型及分类，掌握向量函数微分学的有关知识，了解最优化的基本术语教学重点： 向量函数微分学的有关知识教学难点： 向量函数微分学的有关知识教学方法： 启发式教学手段： 多媒体演示、演讲与板书相结合教学时间： 2 学时教学内容： 1.1 模型与实例无约束最优化问题12min( ),(,)Tnnf xxx xxR约束最优化问题（|,( )0,1,2,;( )0,1,2, nijSx xRg xim hxjl ）min( );.f xxSs.t.即m i n() ;()0 ,1 , 2 ,()0 ,1, 2 , .ijf xgximhxjls.t.其中( )f x称为目标函数，12,nx xx称为决策变量， S称为可行域，( )0(1,2,),( )0(1,2, )ijg ximhxjl称为约束条件例 1（海洋运输问题）某航运公司承接了一项将客户停放在港口等待运输的 N 种货物运往目的地的业务 设航运公司运输单位货物i 的收益为ic（元/吨） ，货船能够装载的货物的重量限制为W （吨） ，相应的容积限制为V （立方米），设ia是单位货物 i 所占的容积（立方米吨），ib是货物 i 可提供的最大数量 （吨） ，iw是货物 i 的日平均装船速度（吨日） ，1q为货船的日泊位费（元日） ，2q为货船在海上航行时的日费用 （元日），d 为航行距离（公里） ，v为航行速度（公里日） 问如何确定货船的装载方案，使航运公司获利最大？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页解设(1,2,)ix iN是货船装载货物的数量（吨） ，则得到该问题的线性分式规划模型1211111max;,0.NNiiiiiiNiiiNiiNiiiiiq xq dc xwvzxdwvxWa xVxbs.t. 1.2 数学预备知识1向量的范数和矩阵的条件数定义如果nR 上的实值函数满足以下三个条件：（1）nxR，有0 x，同时，当且仅当0 x时，0 x；（2）,nxRR，有xx ；（3）,nx yR，有 xyxy 则称 x 为x的范数通常取2221/212()Tnxxxxx xx的 p 范数：1/1(| )(1)nppipixxpx的最大范数：max|1ixxin 性质设A和B是定义于nR 中的两种范数，则总存在正数1c和2c，使nxR，有12ABAcxxcx定义设 A 是n阶方阵，12,n是 A的全部特征值1max|ii n称为 A的谱半径，记作()A设m nAR，称TA A的特征值的正平方根为A的奇异值 A 的最大奇异值与精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7 页最小非零奇异值之商称为A的谱条件数，记为()A，即1()()()tAAA，其中12()( )( )nAAA为 A的所有奇异值，且()tR A性质如果 A为n阶正定矩阵，12()()()0nAAA和12()( )( )nAAA分别为 A的特征值和奇异值，则( )( ),1,2,iiAAin，于是1()()()nAAA如果 A为n阶满秩矩阵，则A的所有奇异值12()( )()0nAAA，从而1()()()nAAA定义一个n阶满秩矩阵 A称为病态的，如果 A的n个列向量之间存在着近似线性关系性质条件数可以用来度量矩阵的病态程度2多元函数的梯度、 Hesse矩阵及 Taylor 公式定义设:,nnfRR xR如果n维向量 p ，使得nxR，有()( )()Tf xxf xpxox则称( )f x在点 x 处可微，并称d ( )Tfxpx为( )f x在点 x 处的微分如 果( )f x在 点 x 处 对 于12(,)Tnxx xx的 各 分 量 的 偏 导 数( ),1,2,if xinx都存在，则称( )f x在点 x 处一阶可导，并称向量12( )( )( )( )(,)Tnf xf xfxf xxxx为( )f x在点 x 处一阶导数或梯度定理 1设:,nnfRR xR如果( )f x在点 x 处可微，则( )f x在点 x 处梯度( )f x存在，并且有d ( )( )Tf xf xx精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 7 页定义设:,nnfRR xR d 是给定的n维非零向量，ded如果0()( )lim()f xef xR存在，则称此极限为( )f x在点 x 沿方向 d 的方向导数，记作( )f xd定理 2设:,nnfRR xR如果( )f x在点 x 处可微，则( )f x在点 x 处沿任何非零方向 d 的方向导数存在，且( )( )Tf xf xed，其中ded定义设( )f x是nR 上的连续函数，nxRd 是n维非零向量如果0，使得(0,)，有()f xd（）( )f x则称 d 为( )f x在点 x 处的下降 （上升）方向定理3设:,nnfRR xR，且( )f x在点 x 处可微，如果非零向量ndR，使得( )Tf xd（）0，则 d 是( )f x在点 x 处的下降 （上升） 方向定 义设:,nnfRR xR 如 果( )f x在 点 x 处 对 于 自 变 量12(,)Tnxx xx的各分量的二阶偏导数2( )( ,1,2, )ijf xi jnxx都存在，则称函数( )f x在点 x 处二阶可导，并称矩阵22221121222222122222212( )( )( )( )( )( )( )( )( )( )nnnnnf xf xf xxxxxxf xf xf xf xxxxxxf xf xf xxxxxx为( )f x在点 x 处的二阶导数矩阵或Hesse矩阵定义设:,nmnh RRxR，记12( )( ),( ),( )Tmh xh xhxhx，如果( ) (1,2,)ih xim在点 x 处对于自变量12(,)Tnxxxx的各分量的偏导数精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 7 页( )(1,2,;1,2, )ijh xim jnx都存在，则称向量函数( )h x在点 x 处是一阶可导的，并且称矩阵111122221212( )( )( )( )( )( )( )( )( )( )nnm nmmmnh xh xh xxxxh xhxhxxxxh xhxhxhxxxx为( )h x在点 x 处的一阶导数矩阵或Jacobi矩阵，简记为( )h x例 2设,nnaRxRbR，求( )Tf xa xb在任意点x处的梯度和 Hesse矩阵解设1212(,) ,(,)TTnnaa aaxx xx，则1( )nkkkf xa xb，因( )(1,2, )kkf xaknx，故得( )f xa又因2( )0( ,1,2, )ijf xi jnxx，则2( )f xO例 3设n nQR是对称矩阵，,nbRcR，称1( )2TTf xx Qxb xc为二次函数，求( )f x在任意点x处的梯度和 Hesse矩阵解设1212(),(,) ,(,)TTijn nnnQqxx xxbb bb，则121111(,)2nnnnijijkkijkf x xxq x xb xc，由于12(,)nf x xx中所有含ix的项为211,11,1112iii iiiiiii iiiininiiq x xqx xq xqx xq x xb x ，所以1( )nijjijif xq xbx，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 7 页从而111111111( )( )( )nnjjjjjjnnnnjjnnjjjjnf xq xbq xxbf xQxbf xbq xbq xx再对1( )(1,2, )nijjijif xq xbinx求偏导得到2( )( ,1,2, )ijijf xqi jnxx，于是1112121222212( )nnnnnnqqqqqqf xQqqq例 4设( )()tf xtd，其中:nfRR二阶可导，,nnxRdRtR，试求( ),( )tt解由多元复合函数微分法知11d()( )()dnnTiiiiiiixtdfftdf xtddutu，221111d()( )()()dnnnnjjTiijjiijjiijxtdfftddddf xtd duutu u定理 4设:,nnfRR xR，且( )f x在点 x 的某邻域内具有二阶连续偏导数，则( )f x在点 x 处有 Taylor 展式21()( )( )(),(01)2TTf xxf xf xxxf xxx证明设( )() ,0,1tf xtxt，则(0)() ,(1)()f xfxx按一元函数 Taylor 公式( ) t在0t处展开，有21( )(0)(0)( ),(0)2tttt 从例 4 得知2(0)( ),( )()()TTf xxxf xxx令1t，有21()( )( )(), (01)2TTf xxf xf xxxf xxx根据定理 1 和定理 4，我们有如下 两个重要公式：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页( )( )( ) ()()Tf xf xf xxxo xx，221( )( )( ) ()()( )()()2TTf xf xf xxxxxf xxxo xx 1.3 最优化的基本术语定义设:nfRR为目标函数，nSR为可行域， xS（1） 若xS，都有( )( )f xf x，则称 x 为( )f x在 S上的全局（或整体）极小点，或者说， x 是约束最优化问题 min( )x Sf x的全局（或整体）最优解，并称()f x为其最优值（2） 若,xS xx，都有( )( )f xfx，则称 x 为( )f x在 S上的严格全局（或整体）极小点（3） 若x 的邻域( )(0)nNxxRxx使得( )xNxS，都有( )( )fxf x，则称 x 为( )f x在 S上的局部极小点，或者说，x 是约束最优化问题 min( )x Sf x 的局部最优解（ 4 ）若x 的邻 域() (0 )Nx使 得(),xNxS xx， 都 有()()fxfx，则称 x 为( )f x在 S上的严格局部极小点精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页