最优化方法教案东北大学.docx

《最优化方法教案东北大学.docx》由会员分享，可在线阅读，更多相关《最优化方法教案东北大学.docx（44页珍藏版）》请在三一办公上搜索。

1、最优化方法教案 东北大学第一章 最优化问题与数学预备知识 最优化分支：线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。 应用最优化方法解决问题时一般有以下几个特点： 1. 实用性强 2. 采用定量分析的科学手段 3. 计算量大，必须借助于计算机 4. 理论涉及面广 应用领域：工业，农业，交通运输，能源开发，经济计划，企业 管理，军事作战。 1 1.1 最优化问题实例 最优化问题：追求最优目标的数学问题。 经典最优化理论： 无约束极值问题：opt f(x1,x2,L,xn) 其中，f(x1,x2,L,xn)是定义在n维空间上的可微函数。 解法：求驻点，即满足 fx1(x1,L,x

2、n)=0fx2(x1,L,xn)=0 LLf(x,L,x)=0nxn1并验证这些驻点是否极值点。 约束极值问题：opt f(x1,x2,L,xn) s.t. hj(x1,x2,L,xn)=0,j=1,2,L,l(ln) 解法：采用Lagrange乘子法，即将问题转化为求Lagrange函数 L(x1,x2,L,xn;l1,L,ll)=f(x1,x2,L,xn)+ljhj(x1,L,xn)j=1l的无约束极值问题。 近代最优化理论的实例： 例1 (生产计划问题) 设某工厂有3种资源B1，B2，B3，数量各为b1，b2，b3，要生产10种产品A1，A10 。每生产一个单位的Aj需要消耗Bi的量为a

3、ij，根据合同规定，产品Aj的量不少于dj，再2 设Aj的单价为cj 。问如何安排生产计划，才能既完成合同，又使总收入最多？ 数学模型：设Aj的计划产量为xj ，z为总收入。 目标函数：maxz=cx jjj=11010aijxjbi,i=1,2,3约束条件： j=1 xd,j=1,2,L,10jj线性规划问题通常采用单纯形法来求解。 例2 (工厂设址问题) 要在m个不同地点计划修建m个规模不完全相同的工厂，他们的生产能力分别是a1,a2L,am，第i个工厂的建设费用fi,i=1,2,L,m。又有n个零售商店销售这种产品，对这种产品的需求量分别为b1,b2L,bn，从第i个工厂运送一个单位产品

4、到第j个零售商店的运费为cij。试决定应修建哪个工厂，使得既满足零售商店的需求，又使建设工厂和运输的总费用最小。 数学模型： 设第i个工厂运往第j个零售商店的产品数量为xij，且 1, 如果修建第i个工厂yi= ,i=1,L,m 0, 否则n目标函数：minz=fiyi+cijxij i=1j=1m 3 nxijaiyi, i=1,L,mj=1mxijbj, j=1,L,n约束条件：i=1 yi=0 或 1, i=1,L,mxij0, i=1,L,m;j=1,L,n整数规划问题通常可用分枝定界法或割平面法来求解。 例3 (投资计划问题) 假设某一个生产部门在一段时间内可用于投资的总金额为a亿元

5、，可供选择的项目总共有n个，分别记为1，2，n。并且已知对第j个项目的投资总数为aj亿元，而收益额总数为cj亿元。问如何使用资金a亿元，才能使单位投资获得的收益最大。 1, 对第j个项目投资 , j=1,L,n 数学模型：设xj=0, 否则cxjnj目标函数：maxz=axjj=1j=1njnajxjaj=1约束条件： x=0 或 1, j=1,L,nj非线性规划问题的求解方法很多，是本课的重点。 动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman最优性原理”，例如：资源分配问题，生产与存储问4 题。 例4 (多参数曲线拟合问题)已知热敏电阻R依赖于温度T的函数关系为

6、 R=x1ex2T+x3其中，x1,x2,x3是待定的参数，通过实验测得T和R的15组数据列表如下，如何确定参数x1,x2,x3？ i 1 50 2 55 3 60 4 65 5 70 6 75 7 80 8 85 Ti/ Ri/kW i 34.78 28.61 23.65 19.63 16.37 13.72 11.54 9.744 9 90 10 95 11 100 12 105 13 110 14 115 15 120 Ti/ Ri/kW 8.261 7.03 6.005 5.147 4.427 3.82 3.307 建立数学模型：测量点(Ti,Ri)与曲线R(T)对应的点产生“偏差”，即

7、 S=Ri-x1ei=115x2Ti+x32 得如下无约束最优化问题： minf(x)=Ri-x1ei=115x2Ti+x32 通常采用最小二乘法。 5 1.2 最优化问题的数学模型 一、 最优化问题的数学模型 1. 定义1：设向量a=a1,a2,L,am, b=b1,b2,L,bm. 若aibi (i=1,2,L,m)，则记ab或ba； 若aibi (i=1,2,L,m)，则记aa2一般模型： 。 TTopt f(x)=f(x1,x2,L,xn) (minf(x) 或 maxf(x)， (2)Si(x)0, i=1,L,m s.t. h(x)=0, j=1,L,l (3)j其中，x=x1,x

8、2,L,xn； f(x)，Si(x)，hj(x)是关于变量Tx1,x2,L,xn的实值连续函数，一般可假定它们具有二阶连续偏导数。 3向量模型： opt f(x) (minf(x) 或 maxf(x)， (2)S(x)0, i=1,L,m s.t. (3)h(x)=0, j=1,L,l 其中，x=x1,x2,L,xn，f(x)称为目标函数； T Si(x)， hj(x)称为约束函数； 满足约束条件，的点称为容许解或容许点； 可行解的全体称为容许域，记为R； 满足的容许点称为最优点或最优解点），记*f(x)称为最优值； x为； 6 不带约束的问题称为无约束问题，带约束的问题称为约束问题； 若目标

9、函数f(x)，约束函数 Si(x)， hj(x)都是线性函数，则称为线性规划；若其中存在非线性函数，则称为非线性规划； 若变量只取整数，称为整数规划； 若变量只取0，1，称为01规划。 注：因 h(x)=0h(x)0，-h(x)0，则最优化问题一般可 写成 opt f(x) s.t. S(x)0二、 最优化问题的分类 一维问题无约束问题n维问题静态规划线性规划最优化问题约束问题 非线性规划动态规划1.3 二维问题的图解法 例1. maxz=2x1+3x2 x1+2x28s.t. 4x116 x,x0 12解：1. 由全部约束条件作图，求出可行域R：凸多边形OABC 7 2. 作出一条目标函数的

10、等值线：设2x1+3x2=6 ，作该直线即为一条目标函数的等值线，并确定在可行域内，这条等值线向哪个方向平移可使z值增大。 3. 平移目标函数等值线，做图求解最优点，再算出最优值。顶*T*点B(4,2)是最优点，即最优解x=42，最优值z=14。 分析： 线性规划问题解的几种情况 有唯一最优解； 有无穷多组最优解：目标函数改为maxz=2x1+4x2 无可行解：增加约束x25，则R=F。 无有限最优解：例 maxz=x1+x2 x1-2x24s.t. - x1+x22 x,x0 12结论：线性规划问题的可行域为凸集，特殊情况下为无界域或空集。线性规划问题若有最优解，一定可在其可行域的顶点上得到

11、。 22例2. min(x1-2)+(x2-1) 2x1+x2-5x2=0s.t. x1+x2-50 x,x0 1222解：目标函数等值线：(x1-2)+(x2-1)=1 2x1+x2-5x2=0 ，得x*=41T C为最优点x1+x2-5=0 8 定义2：在三维及三维以上的空间中，使目标函数取同一常数的点集xf(x)=r, r是常数称为等值面。 1.4 预备知识 线性代数 一、 n维向量空间R 1. 向量的内积：设x=x1,x2,L,xn, y=y1,y2,L,yn，则 内积为 TTnxTy=x1y1+x2y2+L+xnyn=xiyi i=1n2. 向量的范数：设xR，若实数x具有以下 n性

12、质：x0,当且仅当x=0时x=0； ax=ax,aR； nx+yx+y,x,yR. n则称x为R上的向量的范数，简记为。 nn规定了向量范数的线性空间R称为线性赋范空间,记为R,. 3. 常见的向量范数 向量的Lp范数：xpp=xi，1p0，则称xTAx为正定二次型，A为正定矩阵，记A0；若xTAx0，半正定二次型，A为半正定矩阵，记A0。 类似有负定二次型，负定矩阵的概念。 性质：实对称方阵A为正定矩阵 A的特征值均为正A的各阶顺序主子式均为正实对称方阵A为半正定矩阵A的特征值均非负 A的各阶顺序主子式均为非负 10 数学分析 一、 梯度和海色矩阵 1. 多元函数的可微性 可微定义：设f:D

13、RR，x0D，若存在n维向 量l，对p0R，总有 nn1f(x0+p)-f(x0)-lTplim=0 p0p则称函数f(x)在点x0处可微。 式等价于 f(x0+p)-f(x0)=lTp+0(p) 其中，0p是p的高阶无穷小。 定理1：若函数f(x)在点x0处可微，则f(x)在该点关于各个变量的偏导数存在，且 ()f(x0)f(x0)f(x0)l=,L, xxx12n2. 梯度 概念 梯度：令 Tf(x)f(x)f(x)f(x)=,L, xxx2n1则称f(x)为n元函数f(x)在x处的梯度。又称为f(x)关于x的一阶导数。 11 T注：式等价于 f(x0+p)=f(x0)+f(x0)Tp+0

14、(p) 等值面：在三维和三维以上的空间中，使目标函数取同一 数值的点集xf(x)=r,rR称为等值面。 方向导数：设f:RR在点x0处可微，向量p0R，e是p方向上的单位向量，则极限 n1nf(x0+te)-f(x0)lim t0+tf(x0)称为函数f(x)在点x0处沿p方向的方向导数，记作。 pf(x0)方向导数的几何解释：方向导数表示函数f(x)在点x0p处沿方向的p的变化率。 函数的下降方向：设f:RR是连续函数，点n1x0Rn，p0Rn为一方向，若存在d0，对于t(0,d)，都有 f(x0+tp)f(x0) 则称p方向是函数f(x)在点x0处的下降方向； f(x0)0，则方向p是f(

15、x)在点x0处的上下降方向；若方向导数p升方向； 12 性质 ：梯度f(x0)为等值面f(x)=f(x0)在点x0处的 切平面的法矢量。 ：梯度方向是函数具有最大变化率的方向。 定理2：设f:RR在点x0处可微，则方向导数 n1f(x0)=f(x0)Te=f(x0)cosq p其中，e是p方向上的单位向量，q为梯度与p的夹角。 结论2：1）与梯度f(x0)方向成锐角的方向是上升方向；与梯度f(x0)方向成钝角的方向是下降方向； 2）梯度方向是函数值上升最快的方向，称为最速上升方向；负梯度方向是函数值下降最快的方向，称为最速下降方向。 几种特殊函数的梯度公式 rC=0，C为常数； T(bx)=b

16、，其中b=b1,b2,L,bn； TT(xx)=2x； T若Q是对称方阵，则(xQx)=2Qx. 例 3. 泰勒公式与Hesse矩阵 性质1：设f(x):RR具有一阶连续偏导数，则 nf(x+p)=f(x)+f(x)Tp 其中，x=x+qp (0q1)，即介于x与x+p 之间。 13 性质2：设f(x):RR具有二阶连续偏导数，则 n1T2f(x+p)=f(x)+f(x)p+pf(x)p 2T其中 2f(x)x221f(x)2f(x)=xx212Mf(x)xnx12f(x)x1x22f(x)2x2M2f(x)xnx2LLOL2f(x)x1xn2f(x)x2xnM 2f(x)2xn为函数f(x)

17、关于x的二阶导数，称为f(x)的海色矩阵。 22f(x)f(x)2=, i,j=1,L,n。 注1：1) 设向量函数g(x)=g1(x),g2(x),L,gm(x)时， Tg1(x)x1g1(x)g(x)=x2Mg(x)1xng2(x)x1g2(x)x2Mg2(x)xnLLOLgm(x)x1gm(x)x2M gm(x)xn称为向量函数g(x)在点x处的导数。 2) 向量函数g(x)=g1(x),g2(x),L,gm(x)在点x0处可微是指所有分量都在点x0处可微。 14 T关于向量函数常见的梯度： C=0n，CR； (x)=In，xR； mn(Ax)=A,AR nnTn111设j(t)=f(x

18、0+tp)，其中f:RR，j:RR，则 j(t)=f(x0+tp)Tp，j(t)=pT2f(x0+tp)p 例： 15 极小点的判定条件 一、 基本概念 1. 点x0的邻域：N(x0,d)=x x-x00 *2. 局部极小点：设f:DRR. 若存在点xD和数n1d0，对xN(x*,d)D 都有f(x)f(x*)，则称x*为f(x)*在D上的局部极小点；若f(x)f(x)，则称x*为f(x)在D上的严格局部极小点。 *3. 全局极小点：设f:DRR. 若存在点xD，对于 n1xD 都有f(x)f(x*)，则称x*为f(x)在D上的*全局极小点；若f(x)f(x)，则称x为f(x)在D上的严格全局

19、极小点。 性质：全局极小点必是局部极小点；但局部极小点不一定是全局极小点。 类似有极大点的概念。因maxf(x)=min-f(x)，本书主要给出极小问题。 *4. 驻点：设f:DRR可微，xD，若f(x)=0， *则称点x为f(x)的驻点或临界点。 n1二、 极值的条件 定理1设f:DRR具有一阶连续偏导*数，x是D的内点，若x是f(x)的局部极小点，则 n1f(x*)=0 n1f:DRR定理2设具有二阶连续偏导 16 2*数，若x是D的内点且为f(x)的局部极小点，则f(x)是半正npR定的，即对恒有 pT2f(x*)p0 例 定理3设f:DRR具有二阶连续偏导数，n1x*为D的内点，且f(

20、x*)=0，若2f(x*)正定，则x*为f(x)的严格局部极小点。 凸函数与凸规划 一、凸集 1. 凸集的定义：一个n维向量空间的点集D中任意两点的连线仍属于这个集合，即对x1,x2D，有 ax1+(1-a)x2D (0a1) 则称该点集D为凸集。 2. 凸集的性质：凸集的交集仍是凸集(D1D2)； 数乘凸集仍是凸集bD=yy=bx, xD； 凸集的和集仍是凸集D1+D2=yy=x+z, xD1,zD2 特别规定，空集是凸集。 n3. 超平面：设aR且a0, bR，则集合 H=xaTx=b, xRn称为Rn中的超平面，a称为该超平面的法向量，即H:a1x1+a2x2+L+anxn=b； Tnn

21、半空间：集合xaxb, xR称为R中的一个半空间。 17 超球：xr。 4. 凸组合：设x1,x2,L,xl为R中的l个点，若存在a1,a2,L,al且0ai1, nai=1li=1，使得 x=a1x1+a2x2+L+alxl 则称x为x1,x2,L,xl的凸组合。 若a1,a2,L,al均为正，则称为严格凸组合。 5. 顶点：设D是凸集，xD，若x不能用D内不同两点x1和x2的凸组合表示，即xax1+(1-a)x2 (0a1)，则称x为D的顶点。 二、凸函数 1. 凸函数：设f:DRR，D是凸集，若对x1,x2D 及a0, 1，都有 n1f(ax1+(1-a)x2)af(x1)+(1-a)

22、f(x2) 则称f(x)为凸集D上的凸函数；若 f(ax1+(1-a)x2)af(x1)+(1-a) f(x2) (0af(x1)+ f(x1)T(x2-x1) 定理2设f:DRR具有二阶连续偏导数，n1D为开凸集，则 2 f(x)在D内为凸函数对xD，f(x)是半正定的； 2若f(x)正定，则f(x)在D内为严格凸函数。 特殊地，n元二次函数为f(x)=1TxQx+bTx+C；若Q正定，则f(x)称为正定二次函数。 19 性质：正定二次函数是严格凸函数。 5. 凸函数的极值 定理3 设f:DRR为凸集D上的凸函数，则 *f(x)的任一局部极小点x为全局极小点； *若f(x)具有二阶连续偏导数

23、，且存在xD，使2n1f(x*)=0，则x*为f(x)在D上的全局极小点； 若f(x)为严格凸函数，且全局极小点存在，则必唯一。 1TTf(x)=xQx+bx+C，有 特殊：对于正定二次函数2f(x)=Qx+b，得唯一驻点x*=-Q-1b为唯一的全局极小点。 6. 凸规划问题：非空凸集D上的凸函数的极小化问题。 考虑凸规划问题：minf(x)，xR (1) n (2)Si(x)0, i=1,L,m s.t. h(x)=0, j=1,L,l (3)j其中，Si(x)为R上的凹函数，hj(x)为R上的线性函数， nnD=xSi(x)0,hj(x)=0,i=1,L,m;j=1,L,l为凸集， f:D

24、RnR1为D上的凸函数。 注：线性函数既可视为凸函数，又可视为凹函数。 1TTminf(x)=xQx+bx+C 二次规划： 2Axp s.t. Cx=d 其中，xR，Amn，Cln，Q半正定或正定。 20 n 下降迭代算法 1. 下降迭代算法的步骤 选择一个初始点x0，令k：=0 检验xk是否最优？若是，则停止迭代；若不是，则 确定一个下降方向pk：存在d0，对t(0,d)，使得 f(xk+tpk)0，此时-p是点z的下降方向； T2）f(z)p1)和b(b0)，使得当k从某个k0(0)开始，都有 xk+1-xbxk-x*a则称序列xk收敛的阶为a，或xk为a阶收敛。 当a=1，且0b1时，称

25、线性收敛或一阶收敛； 当a=2时，称二阶收敛； 当1a2时，称超线性收敛。 4. 计算终止准则 计算终止准则根据相继两次迭代的结果 a. 根据相继两次迭代的绝对误差 22 xk+1-xke1，f(xk+1)-f(xk)e2 b. 根据相继两次迭代的相对误差 xk+1-xkf(xk+1)-f(xk)e3，e4 xk+1f(xk)+1c. 根据目标函数梯度的模足够小 f(xk)0，n0，一般地，m0，使前后约束条件不等价，但由于目标函数的修改，同时也使所求的目标函数最小值是一个很大的数，也是对“篡改”约束条件的一种惩罚，因此，M叫做罚29 因子，大M法也叫做罚函数法。 若对极大化问题，目标函数中人

26、工变量系数为。 得到如下标准型： min z=cjxj j=1nx1+a1,m+1xm+1+L+a1nxn=b1 x2+a2,m+1xm+1+L+a2nxn=b2LLLs.t. x+am,m+1xm+1+L+amnxn=bmmxj0 (j=1,2,L,n) 其中，xi ( i=1,2,L,m)表示基变量；xj ( j=m+1,L,n)表示非基变量。 2. 求出一个基本容许解 1用非基变量表示基变量和目标函数。 用非基变量表示基变量，即有 xi=bi-j=m+1ax (i=1,L,m) ijjmnn用非基变量表示目标函数，即 z=ckxk=cixi+k=1i=1nj=m+1cxjiijj=cib

27、i+i=1nmj=m+1(c-caji=1jnm)xjj=z0+j=m+1(c-zj)xj=z0+j=m+1snxj 30 其中，z0=cb，而siii=1mmj=cj-zj称为非基变量xj 的检验数。上式中，规定各基变量的检验数为0。 zj=ciaij=c1a1j+c2a2j+L+cmamji=1a1j=c1,L,cmM=c1,L,cmpjamj若干次迭代=TcB1,L,cBmpj=CBpj其中，CB是基变量的价值系数，随基的改变而改变。 2求出一个基本容许解及相应的目标函数值。 令非基变量=0即得初始基本容许解： xi=bi (i=1,L,m)，xj =0 ( j=m+1,L,n) 初始目

28、标函数值：z=z0 3. 最优性检验 1检验数sj：目标函数式中，各非基变量的系数，即称为各非基变量的检验数。 2最优解判别定理：若在极小化问题中，对于某个基本容许解， 所有检验数sj0，且人工变量为0，则该基本容许解是最优解。 3无穷多最优解判别定理：若在极小化问题中，对于某个基本容许解，所有检验数sj0，又存在某个非基变量的检验数为0，且人工变量为0，则该线性规划问题有无穷多最优解。 4无容许解判别定理：若在极小化问题中，对于某个基本容许31 解，所有检验数sj0，但人工变量不为0，则该线性规划问题无容许解。 4. 基变换 1基本容许解的改进定理：已知一个非退化的基本容许解具有目标函数值z

29、0，设某一个非基变量xj，其sj0，则存在一个可行解具有目标函数值zz0；如果用pj代替原基中的某一列向量而产生一个新的基本容许解，则该新的解将有zz0。 2换入变量的确定 xk为换入变量，使sk=minsjsj0 arkaik4无有限最优解判别定理：若在极小化问题中，对于某个基本容许解，有一个非基变量的检验数sk0，但pk列中没有正元素，且人工变量为0，则该线性规划问题无有限最优解。 三、单纯形法的表格形式 1构造初始可行基，并计算检验数sj 2从表中找出基本可行解和相应的目标函数值 3最优性检验 4基变换 1换入变量的确定 32 2换出变量的确定 3主元素的确定 单纯形表中，换入变量所在的

30、列和换出变量所在的行交叉处的元素为主元素，标“*”号。 4取主变换 即单纯形法的一次迭代。在表中以ark主元素进行旋转变换，把xk所对应的列向量 a1k0MM行初等变换pk=ark=1 MM0amk于是得到新一轮的单纯形表。 四、单纯形法解极大化和极小化问题的区别 原模型目标函数 标准型 最优性检验 换入变量的确定 nmin z=cjxj j=1目标函数中人工所有sj变量系数为大M 0，且sk=minsjsj0 人工变量为0 max z=cjxj j=1n目标函数中人工所有sj变量系数为“-M” 人工变量为0 五、两阶段法 1. 第一阶段：判断原线性规划问题是否有容许解。 先求解以下线性规划 33 min w=xn+1+L+xn+m naijxj +xn+i=bi ,i=1,L,ms.t. j=1