2022年最优化方法教案 .docx

《2022年最优化方法教案 .docx》由会员分享，可在线阅读，更多相关《2022年最优化方法教案 .docx（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 学习必备 欢迎下载第一章 最优化问题与数学预备学问最优化分支： 线性规划,整数规划,几何规划,非线性规划,动态规划；又称规划论；应用最优化方法解决问题时一般有以下几个特点：1. 有用性强 2. 采纳定量分析的科学手段 3. 运算量大,必需借助于运算机 4. 理论涉及面广 应用领域： 工业,农业,交通运输,能源开发,经济方案,企业治理,军事作战 ；名师归纳总结 - - - - - - -第 1 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载 1.1 最优化问题实例 最优化问题：追求最优目标的数学问题；经典最优

2、化理论：（1）无约束极值问题：opt fx 1,x2,nx,nx）（min fx 1,x2,xn或maxfx 1,x2,其中,fx 1,x2,x n是定义在 n 维空间上的可微函数；解法（求极值点）：求驻点,即满意fx 1x 1,x n0fx2x 1,x n0fxnx 1,x n0并验证这些驻点是否极值点；L（2）约束极值问题：opt fx 1,x2,xn,llns.t. hjx 1,x2,x n0 ,j,12 ,解法：采纳 Lagrange乘子法,即将问题转化为求jLagrange函数lhjx 1,xnx 1,x2,xn;1,lfx 1,x2,x nj1的无约束极值问题；近代最优化理论的实例

3、：例 1 生产方案问题 设某工厂有 3 种资源 B 1,B2,B3,数量各 为 b1,b2,b3,要生产 10 种产品 A 1, , A 10 ；每生产一个单位的A j 需要消耗 B i 的量为 aij,依据合同规定,产品A j 的量不少于 dj,再设 A j 的单价为 cj ；问如何支配生产方案,才能既完成合同,又使总名师归纳总结 - - - - - - -第 2 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载收入最多？（线性规划问题）数学模型：设 A j 的方案产量为,jx,z 为总产值；10,1 23,目标函数：maxzj1cjxj10aijxjb

4、i,i约束条件：j1dj,j,1 2xj, 10线性规划问题通常采纳单纯形法来求解；例 2 工厂设址问题 要在 m 个不同地点方案修建 m 个规模不完全相同的工厂,他们的生产才能分别是a 1,a2,am（为简便起见,假设生产同一种产品） ,第 i 个工厂的建设费用fi,i,1,2,m；又有 n 个零 售商店销售这 种产 品,对 这种 产品 的需求 量分 别为b 1 , b 2 , b n,从第 i 个工厂运输一个单位产品到第 j 个零售商店的运费为 cij ；试打算应修建哪个工厂, 使得既满意零售商店的需求,又使建设工厂和运输的总费用最小； （混合整数规划问题）数学模型：设第 i 个工厂运往第

5、j 个零售商店的产品数量为xij（i=1, , m；j=1, , n）,且名师归纳总结 yi,1 ,0z假如修建第i个工厂,i,1,m第 3 页,共 34 页否就目标函数：minmnfiyicijx iji1j1- - - - - - -精选学习资料 - - - - - - - - - nxij学习必备i欢迎下载ma iy i,1,约束条件：j1xij,bj,j,1,n,nmi10或,1i,1,myi0i,1,m ;j,1x ij整数规划问题通常可用分枝定界法或割平面法来求解；例 3 投资方案问题 假设某一个生产部门在一段时间内可用于投资的总金额为a亿元,可供挑选的项目总共有n 个,分别记为

6、1,2, n；并且已知对第 j 个项目的投资总数为 a 亿元,而收益额总数 为 jc 亿元；问如何使用资金 a 亿元,才能使单位投资获得的收益最大；（非线性规划问题）数学模型：设x j,1对第j个项目投资,j,1,n,0否就ncjxj目标函数：maxzj1najxjj1njxjaa约束条件：j1xj0或,1j,1,n非线性规划问题的求解方法许多,是本课的重点；动态规划是解决“ 多阶段决策过程” 的最优化问题的一种方法,基于“ Bellman 最优性原理” ,例如：资源安排问题, 生产与储备问题；名师归纳总结 - - - - - - -第 4 页,共 34 页精选学习资料 - - - - - -

7、 - - - 学习必备 欢迎下载例 4 多参数曲线拟合问题 数关系为已知热敏电阻 R依靠于温度 T 的函x 2T x 3R x 1 e（* ）其中,x 1 , x 2 , x 3 是待定的参数,通过试验测得 T 和 R的 15 组数据列表如下,如何确定参数 x 1 , x 2 , x 3？i 1 2 3 4 5 6 7 8 iT /50 55 60 65 70 75 80 85 Ri / k 34.78 28.61 23.65 19.63 16.37 13.72 11.54 9.744 i 9 10 11 12 13 14 15 iT /90 95 100 105 110 115 120 Ri

8、 / k 8.261 7.03 6.005 5.147 4.427 3.82 3.307 建立数学模型：测量点 T iR i 与曲线 R T 对应的点产生“ 偏差”,即S15R ix 1 eT ix 22x 3i1得如下无约束最优化问题：minfx15R ix 1eT ix 232xi1通常采纳最小二乘法；名师归纳总结 - - - - - - -第 5 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载 1.2 最优化问题的数学模型一、 最优化问题的数学模型1. 定义 1：设向量 a 1 , a 2 , , a m T , b 1 , b 2 , , b m

9、T. 如 a i b i i ,1 ,2 , m ,就记 或；如 a i b i i ,1 2 , , m ,就记 或；n2一般模型：opt f x 或 min 或 max,x R（1）S i x 0 , i ,1 , m 2 s.t. h j x 0 , j ,1 , l 3 其 中 ,x x 1 , x 2 , , nx T；f x ,Si x ,h j x 是 关 于 变 量x 1 , x 2 , , x n 的实值连续函数, 一般可假定它们具有二阶连续偏导数；3向量模型：opt f x 或 min 或 max,x R n（1）S x 0 , i ,1 , m 2 s.t. h x 0

10、, j ,1 , l 3 其中,f x 称为目标函数；Si x ,hj x 称为约束函数；满意约束条件（ 2）,（3）的点称为容许解或容许点（或可行解） ；可行解的全体称为容许域（或可行域） ,记为 R；为满意（ 1）的容许点称为最优点或最优解（或微小（大）点 ）,记x ；* f x 称为最优值；不带约束的问题称为无约束问题,带约束的问题称为约束问题；如目标函数fx,约束函数Six ,hjx 都是线性函数,就称为线性规划；如其中存在非线性函数,就称为非线性规划；名师归纳总结 - - - - - - -第 6 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载如

11、变量只取整数,称为整数规划；如变量只取 0,1,称为 01 规划；注：因h x0hx0,-hx 0,就最优化问题一般可写成opt fx0s . t.S x二、 最优化问题的分类最优化问题静态规划无约束问题一维问题n 维问题约束问题线性规划非线性规划动态规划 1.3 二维问题的图解法例 1. maxz2x 13x2s .x 12x 28x 14x 116,x 20解：1. 由全部约束条件作图,求出可行域R：凸多边形 OABC 2. 作出一条目标函数的等值线：设2x 13x26,作该直线即为一条目标函数的等值线, 并确定在可行域内, 这条等值线向哪个方向平移可使 z 值增大；名师归纳总结 - -

12、- - - - -第 7 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载3. 平移目标函数等值线,做图求解最优点,再算出最优值；顶点B4 , 2是最优点,即最优解x42 T,最优值z14；分析：线性规划问题解的几种情形（1）有唯独最优解（上例）；（2）有无穷多组最优解：目标函数改为maxz2x 14x2（3）无可行解：增加约束x 25,就 R；x2（4）无有限最优解（无界解） ：例maxzx 1x 12x24s . t.-x 1x22x 1,x20结论：（1）线性规划问题的可行域为凸集,特殊情形下为无界域或空集；（2）线性规划问题如有最优解,肯定可在其可行

13、域的顶点上得到；例 2. minx 12 2x 2-12x2-12T1x 12 x 25x 20s .x 1x250x 1,x 20解：目标函数等值线：x 122C 为最优点x 12 x 25x200,得x41x 1x 25定义 2：在三维及三维以上的空间中,使目标函数取同一常数的名师归纳总结 点集xfx r,r是常数称为等值面；第 8 页,共 34 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载 1.4 预备学问（一）线性代数xx 1,x2,xnT,yy 1,y 2,ynT,就一、 n 维向量空间Rn1. 向量的内积： 设内积为nTx y x

14、 1 y 1 x 2 y 2 x n y n x i y ii 12. 向量的范数（或长度或模） ：设 x R ,如实数 x 具有以下性质：（1）x 0 , 当且仅当 x 0 时 x 0；（2）x x , R；n（3）x y x y , x , y R . 就称 x 为 R 上的向量的范数,简记为 n；规定了向量范数的线性空间 R 称为线性赋范空间 ,记为 n R n , . 3. 常见的向量范数1n pp向量的 L 范数：x p x i,1 pi 1三个重要的向量范数：x ,1 x 2, x注：如无特殊说明,本书中的 指的是 x 2；4. x, y 间的距离：x y5. x 与 y 正交：x

15、 T y 0如非零向量组 x 1 , ,x k 的向量两两正交,称它们是正交向量组；名师归纳总结 6. 标准正交基：e1 , , n e是 n 个正交的单位向量,即第 9 页,共 34 页- - - - - - -精选学习资料 - - - - - - - - - ei学习必备欢迎下载jT ej,1i,0ij二、 特点值和特点向量定义： 设 A为 n 阶方阵,存在数和非零向量 x ,使就称Axx,的特为矩阵 A的特点值,非零向量x 为矩阵 A属于特点值征向量；三、 正定矩阵定义： 设 A为 n 阶实对称方阵,如对任意非零向量 x ,均有x TAx 0,就称 x T Ax 为正定二次型, A为正定

16、矩阵,记 A0；如x TAx 0,半正定二次型, A为半正定矩阵；类似有负定（半负定）二次型,负定（半负定）矩阵的概念；性质：实对称方阵 A 为正定矩阵（负）A 的特点值均为正（负）A 的各阶次序主子式均为正（奇数阶 为负,偶数阶为正）实对称方阵 A 为半正定矩阵A的特点值均非负A的各阶次序主子式均为非负名师归纳总结 - - - - - - -第 10 页,共 34 页精选学习资料 - - - - - - - - - （二）数学分析学习必备欢迎下载一、 梯度和海色（ Hesse）矩阵1. 多元函数的可微性可微定义：设f:DRnfR1,x0pD,如存在n维向（1）量 l ,对p0Rn,总有x 0

17、lT0fx 0plim p0p0x 处可微；就称函数fx 在点式（1）等价于fx 0pfx 0lTp0px 处可微,就 0（2）其中,0p是 p 的高阶无穷小；fx在点fx定理 1：（可微的必要条件） 如函数在该点关于各个变量的偏导数存在,且lfx 0,fx0,fx 0Tx2x 1xn2. 梯度（1）概念梯度：令名师归纳总结 就称ffxfx fx,fx,fx Tgrad fx ）；又第 11 页,共 34 页x 1x2xn为 n 元函数fx在 x 处的梯度（或记为称为x关于x的一阶导数；- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载注： 式（2）

18、等价于fx0pfx0fx0Tp0p（3）等值面：在三维和三维以上的空间中,使目标函数取同一数值的点集xfx:r,rR 称为等值面（曲面）；p0Rn,e方向导数： 设fRnR1在点0x 处可微, 向量是p方向上的单位向量,就极限lim t 0fx 0te fx 0fp x 0 ；0x 处t称为函数fx 在点0x 处沿 p 方向的方向导数,记作方向导数的几何说明： 方向导数fx 0表示函数fx 在点p沿方向的 p 的变化率；x 0函数的下降（上升）方向：设f:RnR1是连续函数,点,Rn,p0Rn为一方向,如存在0 ,对于t0 ,都有f x 0 tp f x 0 （f x 0 tp f x 0 ）

19、就称 p 方向是函数 f x 在点 x 处的下降（上升）方向；结论 1：如方向导数 f p x 0 0,就方向p是 f x 在点 x 处的下降方向；如方向导数 f p x 0 0,就方向p是 f x 在点 x 处的上升方向；名师归纳总结 - - - - - - -第 12 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载（2）性质【性质 1】：梯度fx 0为等值面fxfx0在点x 处的切平面的法矢（向）量；【性质 2】：梯度方向是函数具有最大变化率的方向；定理 2：设f:RnR1在点x 处可微,就方向导数 0fx 0fx 0Tefx0cosp其中,e是 p

20、方向上的单位向量,为梯度与 p 的夹角；结论 2：1）与梯度 f x 0 方向成锐角的方向是上升方向；与梯度 f x 0 方向成钝角的方向是下降方向；2）梯度方向是函数值上升最快的方向,称为最速上升方向；负梯度方向是函数值下降最快的方向,称为最速下降方向；（3）几种特殊函数的梯度公式（1）C0, C 为常数；b 1,b 2,nbT；（2）bTx b,其中b（3）xTx2x；xTQx2Qx. （4）如 Q是对称方阵,就例3. 泰勒（ Taylor）公式与 Hesse矩阵名师归纳总结 性质 1：设fx :RnR具有一阶连续偏导数,就（* ）第 13 页,共 34 页其中,xp0fxpfxfTp1,

21、即介于x与xp之间；- - - - - - -精选学习资料 - - - - - - - - - 性质 2：设fx :Rn学习必备欢迎下载R具有二阶连续偏导数,就fxpfxfxTp1pT2fp（* ）2其中2fx2fx2fx 2fx22 x 1x 12fx 2x 12fx nfxxx x 2x 1x2 2x2xn2fx2fx2fx x nx 1xnx 22 x n为函数fx关于x的二阶导数,称为fx的海色（ Hesse）矩阵；结论 1：当fx C2时,2fx2fx,i,j,1,n（即x ixjxjx i海色矩阵对称）；名师归纳总结 注 1：1 设向量函数gxg1x ,g2x,g,gmxT时,第

22、14 页,共 34 页g 1xg2xmxgxx 1g 1 xgx 12 xx 1m xgx 2x 2gx2x 处可微是g 1xg2xmxx nx nxn称为向量函数gx在点x处的导数（梯度）；T在点2 向量函数gxg 1x,g2x,gmx指全部重量都在点x 处可微；- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载关于向量函数常见的梯度：（1）C0 ,CAn R ；f:RnR1,:R1R1,（2）xIn,xn R ；（3）AxAT,Rmn（4）设tfx 0tp,其中就tfx 0tpTp,tpT2fx 0tpp例：名师归纳总结 - - - - - -

23、-第 15 页,共 34 页精选学习资料 - - - - - - - - - （三）学习必备欢迎下载fx ）微小点的判定条件（求min 一、 基本概念1. 点 x 的邻域：0 N x 0 , x x x 0 , 02. 局部微小点：设 f : D R n R 1. 如存在点 x *D 和数0 ,对 x N x * , D 都有 f x f *x ,就称 *x 为 f x 在 D 上的（非严格）局部微小点；如 f x f *x （x *x）,就称*x 为 f x 在 D 上的严格局部微小点；3. 全局微小点：设 f : D R n R 1. 如存在点 x *D,对于x D 都有 f x f *x

24、 ,就称 *x 为 f x 在 D 上的（非严格）全局微小点；如 f x f x * （x *x）,就称 *x 为 f x 在 D 上的严格全局微小点；性质：全局微小点必是局部微小点； 但局部微小点不肯定是全局微小点；类似有极大点的概念；因maxfxminfx,本书主要给出微小问题；4. 驻点：设f:DRnR1可微,x *D,如f*x0,就称点*x 为fx的驻点或临界点；二、 极值的条件名师归纳总结 数,定理 1（一阶必要条件）设f:DRnR1具有一阶连续偏导第 16 页,共 34 页*x 是 D 的内点,如*x 是fx的局部微小点,就x*0f定理 2（二阶必要条件）设f:DRnR1具有二阶连

25、续偏导- - - - - - -精选学习资料 - - - - - - - - - 数,如*x 是 D 的内点且为学习必备欢迎下载2fx*是半正定fx 的局部微小点, 就的,即对pn R 恒有pT2fx*p0例定理 3（二 阶充分条件）设f:DRnfxR1具有二阶连续偏导数,0,如2*正定,就*x 为fx的*x 为 D 的内点,且f*x严格局部微小点；（四）凸函数与凸规划一、凸集1. 凸集的定义：一个n 维向量空间的点集 D 中任意两点的连线仍属于这个集合,即对x 1,x 2D,有01 x 1 1x 2D就称该点集 D 为凸集；2. 凸集的性质：（1）凸集的交集仍是凸集D1D2；zD 2（2）数

26、乘凸集仍是凸集Dyyx ,xxD；D 1,（3）凸集的和集仍是凸集D 1D2yyz ,x特殊规定,空集是凸集；名师归纳总结 3. 超平面：设n R 且称为,0 bR,就集合第 17 页,共 34 页Rnn R 中的超平面,称为该超平面HxTxb,x的法向量,即H:a 1x 1a2x2,xanxnb；（是凸集）TxbRn称为n R 中的一个半空间；半空间：集合x- - - - - - -精选学习资料 - - - - - - - - - 超球：xr；学习必备欢迎下载4. 凸组合：设 x 1 , x 2 , , lx 为 R 中的 l 个点,如存在 n a 1 , a 2 , , lal且 0 a

27、i ,1 a i 1,使得i 1x a 1 x 1 a 2 x 2 a lx l就称x为 x 1 , x 2 , , lx 的凸组合；如 a 1 , a 2 , , la 均为正,就称为严格凸组合；5. 顶点（或极点）：设 D 是凸集,x D,如 x 不能用 D 内不同两点 1x 和 2x 的凸组合表示,即 x x 1 1 x 2 0 1,就称x 为 D 的顶点；二、凸函数及1. 凸函数 ：设f:DRnR1, D 是凸集,如对x 1,x2D,01,都有就称fx 11x 2fx 11fx 21fx为凸集 D 上的凸函数；如fx 1 1x 2fx 11fx 20就称fx为凸集 D 上的严格凸函数；

28、类似有凹函数的定义；2.几何意义 ：函数图形上连接任意两点的线段到处都在函数图形的上方；3. 性质名师归纳总结 性质 1：fx为凸集 D 上的凸函数,k0,就kfx 也为 D 上第 18 页,共 34 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载的凸函数；性质 2：两个凸函数的和仍是凸函数； f 1 x f 2 x 推论 1：凸集 D 上有限个凸函数 fi x 的非负线性组合k 1 f 1 x k m f m x , k i 0仍为 D 上的凸函数；性质 3：如fx 为凸集 D 上的凸函数,就对xR ,fx的为凸集 D 上的凸水平集Dxfx

29、,xD 是凸集；性质 4：fx 为凸集 D 上的凹函数f函数；4. 凸函数的充分必要条件定理 1（一阶条件）设f:DRnR1可微, D 是凸集,就（1）fx为凸函数对x 1,x2D,恒有fx 2fx 1fx 1Tx 2-x 1（2）fx为严格凸函数对x 1,x 2D,x 1x 2恒有ffx 2fx 1x 1Tx2-x 1定理 2（二阶条件）设f:DRnR1具有二阶连续偏导数,D 为开凸集,就名师归纳总结 （1）fx在 D 内为凸函数对xD,2fx是半正定的；第 19 页,共 34 页（2）如2fx 正定,就fx 在 D 内为严格凸函数；特殊地, n 元二次函数为fx 1xTQxbTxC（ Q

30、为对称2矩阵）；如 Q 正定,就fx 称为正定二次函数；- - - - - - -精选学习资料 - - - - - - - - - 学习必备欢迎下载2fx Q）性质： 正定二次函数是严格凸函数； （由于5. 凸函数的极值f定理 3 设f:DRnR1为凸集 D 上的凸函数,就（1）fx的任一局部微小点*x 为全局微小点；（ 2 ） 如fx具 有 二 阶 连 续 偏 导 数 , 且 存 在x*D, 使x*0,就*x 为fx在 D 上的全局微小点；f（3）如fx为严格凸函数,且全局微小点存在,就必唯独；特殊：对于正定二次函数fx1xTQxbTxC,有2xQxb,得唯独驻点x *Q1 b为唯独的全局微小点；6. 凸规划问题： 非空凸集 D 上的凸函数的微小化问题；考虑凸规划问题：min f x ,x R n1 S i x ,0 i ,1 , m 2 s.t. h j x ,0 j ,1 , l 3 其中,Si x 为 R 上的凹函数,n hj