高等运筹第四讲刘巍大连海事大学

1、高等运筹学,第二篇 运筹学中的数学规划,第四章 线性规划 第五章 非线性规划 第六章 锥规划、矩阵规划及变分不等式 第七章 整数规划 第八章 动态规划 第九章 向量优化（多目标优化）,第五章 非线性规划（续）,本节课讨论n元函数的无约束非线性规划问题：,求解此类模型(UMP)的方法称为无约束最优化方法。,无约束最优化方法通常有两类： 解析法：要使用导数的方法； 直接法：无须考虑函数是否可导，直接使用函数值。,退 出,前一页,后一页,4.4无约束最优化方法,1.无约束问题的最优性条件,定理1,定理2,梯度为0的点称为函数的驻点。 驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时

2、称为函数的鞍点。 定理2说明：UMP问题的局部最优解必是目标函数的驻点。,注：,退 出,前一页,后一页,定理3,定理4,退 出,前一页,后一页,例,解： 1.先求出目标函数的全部驻点； 2.利用充分条件判断驻点是不是最优点。,退 出,前一页,后一页,关于梯度的复习： 梯度是一个向量。n元函数f(x1 ,x2 ,xn)在某点x处的梯度为：,梯度的方向与函数f的等值线的一个法线方向相同，从较低的等值线指向较高的等值线。,梯度的方向就是函数f的值增加最快的方向，其相反方向就是函数值降低最快的方向。,2.最速下降法,退 出,前一页,后一页,最速下降法又称为梯度法，由Cauchy于1847年给出。,最速

3、下降法解决的是具有连续可微的目标函数的UMP问题。,最速下降法的基本思想：从当前点xk出发寻找使得目标函数下降最快的方向，即负梯度方向。,退 出,前一页,后一页,最速下降法计算步骤：,选区初始点x0和精度,计算,停止，输出x0,求p0=,计算t0,使,计算x1= x0+ t0 p0,退 出,前一页,后一页,例,解：,退 出,前一页,后一页,说明： 观察P119的图，可以发现x1 x0垂直于目标函数的等值线（图中的虚线）在x0的切线； 最速下降方法相邻的两个搜索方向是相互垂直的，即x1 x0垂直x1 x2； 最速下降法解决UMP的缺陷：迭代点越靠近最优解则目标函数下降的速度越慢； 优点：迭代点列

4、总是收敛的，而且计算过程简单。,退 出,前一页,后一页,本节课讨论约束非线性规划问题MP,其中,x=(x1 ,x2, xn)T，f(x),gi(x),hj(x)为x的实值函数,求解此类模型(MP)的方法称为约束最优化方法。,退 出,前一页,后一页,4.5约束最优化方法,1.约束最优化问题的最优性条件,对于MP问题：,退 出,前一页,后一页,若x*有变化，则约束条件可能没有破坏,若x*有变化，则约束条件一定被破坏,令J表示MP的全部等式约束的下标集合，即J=1,2q, I表示MP的全部不等式约束的下标集合，即I=1,2p,x*的积极约束的下标集合,退 出,前一页,后一页,定理1,对于,若x*是局

5、部最优解,则,退 出,前一页,后一页,定理1的说明：,2、称下述表达式为MP的Kuhn-Tucker条件，简称K-T条件,满足K-T条件的点称为MP的K-T点，定理1说明MP的局部最优解一定是MP的K-T点。,为了求出MP的最优解，可以先找出MP的K-T点，再做进一步的判断。,退 出,前一页,后一页,3、定理1的实例说明,定理1表明：若(x1,x2)T是局部最优解，g1和g2为积极约束，则：,退 出,前一页,后一页,4.定理1的特例1,退 出,前一页,后一页,5.定理1的特例2,退 出,前一页,后一页,6.定理1的改进：,对于,若x*是局部最优解,则,互补松紧条件,退 出,前一页,后一页,7.

6、实例说明改 进后的定理1：,定理1改进后表明：若(x1,x2)T是局部最优解，则：,退 出,前一页,后一页,互补松紧条件,退 出,前一页,后一页,定理2,对于,注：定理2表明，在凸性条件下，K-T点是整体最优解。,退 出,前一页,后一页,例：写出K-T条件; 求出相应的K-T点; 判断K-T点是不是问题的最优解,解：由于全部函数都是连续可微的，所以应用以下K-T条件,退 出,前一页,后一页,首先写出原MP问题的K-T条件：,根据定理1,K-T点还应该满足原问题的约束条件,互补松紧条件,退 出,前一页,后一页,利用互补松紧条件，可以求出K-T点：,利用定理2，由于全部函数都连续可微，并且f和g都

7、是凸函数，h是线性函数，所以K-T点就是整体最优解。,退 出,前一页,后一页,2.惩罚函数法,惩罚函数法的基本思想：利用原问题的中的约束函数构造适当的惩罚函数，并和原问题的目标函数相加，得到带参数的增广目标函数，从而将原问题题转换为一系列无约束非线性规划问题。 惩罚函数法的分类：罚函数法（外部惩罚法），障碍函数法（内部惩罚法）,退 出,前一页,后一页,(1) 罚函数法,罚函数法基本原理：,考虑：,构造惩罚函数：,很大的正数,无约束最优化问题min F(x)=f(x)+p(x)的最优解必定是原问题的最优解。,退 出,前一页,后一页,可选的惩罚函数：,惩罚函数法的经济解释： f(x)为产品成本，约

8、束条件为产品质量约束； 如果违反质量约束，就给予一定的惩罚p(x)； 追求的目标就是成本f(x)和惩罚量p(x)的总和最小（即构造的无约束最优化问题）； 如果惩罚条件很苛刻，最好的结果就是不违反质量约束（无约束最优化问题的最优解为MP的最优解）,退 出,前一页,后一页,(2) 障碍函数法,障碍函数法基本原理： 构造一个新的目标函数，它在可行区域的边界筑起一道墙； 当迭代点靠近边界时，新的目标函数迅速增加；迭代点被档在可行区域的内部； 迭代得到的点列就只可能在可行区域的内部。,退 出,前一页,后一页,可选的惩罚函数：,考虑：,构造最优化问题：,或：,当x靠近边界时，至少有一个gi(x)趋近于零，

9、则F(x)将无限增大，从而使得迭代点保持在可行区域的内部。,退 出,前一页,后一页,应用实例： 供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米 ）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。 （1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 （2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,（一）、建立模型,记工地的位置为(ai，bi)，水

10、泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。,当用临时料场时决策变量为：Xij， 当不用临时料场时决策变量为：Xij，xj，yj。,（二）使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题. 线性规划模型为：,设X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X

11、42= X 10, X52= X 11, X62= X 12 编写程序gying1.m,MATLAB（gying1）,clear a=1.25 8.75 0.5 5.75 3 7.25; b=1.25 0.75 4.75 5 6.5 7.75; d=3 5 4 7 6 11; x=5 2; y=1 7; e=20 20; for i=1:6 for j=1:2 aa(i,j)=sqrt(x(j)-a(i)2+(y(j)-b(i)2); end end,CC=aa(:,1); aa(:,2); A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1;

12、B=20;20; Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 ; beq=d(1);d(2);d(3);d(4);d(5);d(6); VLB=0 0 0 0 0 0 0 0 0 0 0 0;VUB=; x0=1 2 3 0 1 0 0 1 0 1 0 1; xx,fval=linprog(CC,A,B,Aeq,beq,VLB,VUB,x0),计

13、算结果为：,x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000 fval = 136.2275,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：,设 X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X

14、11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16,（1）先编写M文件liaoch.m定义目标函数。,MATLAB（liaoch）,function f=liaoch(x) a=1.25 8.75 0.5 5.75 3 7.25; b=1.25 0.75 4.75 5 6.5 7.75; d=3 5 4 7 6 11; e=20 20; f1=0; for i=1:6 s(i)=sqrt(x(13)-a(i)2+(x(14)-b(i)2); f1=s(i)*x(i)+f1; end f2=0; for i=7:12 s(i)=sqrt(x(15)-a(i-

15、6)2+(x(16)-b(i-6)2); f2=s(i)*x(i)+f2; end f=f1+f2;,(2) 取初值为线性规划的计算结果及临时料场的坐标: x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7; 编写主程序gying2.m.,MATLAB（gying2）,x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7; A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0; B=20;20; Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0

16、0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0; beq=3 5 4 7 6 11; vlb=zeros(12,1);-inf;-inf;-inf;-inf; vub=; x,fval,exitflag=fmincon(liaoch,x0,A,B,Aeq,beq,vlb,vub),(3) 计算结果为：,x =3,4.9994,4,7,1.

17、0006,0,0,0.0006,0,0,4.9994,11,5.6774,4.9055 7.2499,7.7500 fval = 89.8851 exitflag = 1,(4) 若修改主程序gying2.m, 取初值为上面的计算结果: x0=3,4.9994,4,7,1.0006,0,0,0.0006,0,0,4.9994,11,5.6774, 4.9055,7.2499,7.7500,得结果为: x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6958 4.9283 7.2500 7.7500 fval =89

18、.8835 exitflag = 1,总的吨千米数比上面结果略优.,MATLAB（gying2）,(5) 若取初值为上面的计算结果: x0=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6958 4.9283 7.2500 7.7500 则计算结果为: x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6958 4.9283 7.2500 7.7500 fval =89.8835 exitflag = 0 总的吨千米数89.8835与上面结

19、果一样.,第六章 锥规划,锥规划是线性空间中凸锥上的数学规划，它是线性规划与非线性规划的推广。自20世纪90年代中期开始，它一直是国际优化领域的研究热点。相关的研究带动了数学规划学科的深入发展，促进代数、群论、拓扑学、几何学、非线性分析等分支在数学规划中的融合，及优化理论与技术在工程、交通、经济与金融、管理等领域的广泛应用。,研究成果主要包括以下四个方面,(1)二阶锥优化和半定优化。 (2)对称锥优化。 (3)齐次锥优化 (4)双曲锥优化。,一、二阶锥优化和半定优化,二阶锥规划： 约束条件是二阶锥的凸优化 半定规划： 半定规划是指线性函数在对称矩阵的仿射组合半正定的约束下的极小问题,它实际上是

20、凸优化问题,线性二阶锥优化和半定优化已经得到了很好的发展，并且广泛地应用于各种实际问题。近些年，人们开始致力于非线性二阶锥优化和非线性半定优化的理论与算法的研究.,1.二阶锥规划,二阶锥规划是在有限个二阶锥的笛卡儿乘积与仿射子空间的交集上求一个线性目标函数的最小值问题。二阶锥规划是锥规划的一个分支，它既是线性规划的推广，又是半定规划的特例，是一种具有优美结构的对称锥规划。这类规划应用广泛，比如在设施选址、图论控制优化、天线阵列设计、投资组合问题等方面以及金融、工程设计、数字信号处理、声学、力学、民航、电气等领域都有所应用。因此，研究二阶锥规划问题的理论和算法具有重要的理论意义和应用价值。,二阶

21、锥规划问题的研究起源于17世纪，但直至最近十几年才进入活跃阶段，2003年有了对其理论和算法研究的阶段性综述文章，对二阶锥规划的算法研究主要分为内点法和非内点法两大类。原始-对偶内点法是一类重要的内点法，包含“可行内点法”和“不可行内点法”两种，前者的初始点和迭代点均要求可行，后者的初始点和迭代点只需满足二阶锥约束，可行内点法主要有原始-对偶路径跟踪算法，基于核函数的原始-对偶内点算法等。不可行内点法常见的有不可行内点预估-校正算法，非精确不可行内点算法等。非内点法主要有光滑牛顿法，非内点（内部）连续化方法，序列二次规划法等。,二阶锥规划（SOCP）问题是在有限个二阶锥的笛卡儿乘积与仿射子空间

22、的交集上求一个线性目标函数的最小值，其标准形式为（文1）:,二阶锥规划因其优美的几何结构和广泛的应用性引起了人们浓厚的研究兴趣，对二阶锥规划问题的讨论由来已久，最早可追溯到17世纪。1634年，法国数学家费马（Fermat P.D.）提出问题（文2）：对平面上任意给定的三个点，如何求出一个点，使得该点到这三点的距离之和为最小。这个问题后来被瑞士数学家斯坦纳（Steiner J.）推广到给定n个点的情形。之后，德国经济学家韦伯（Weber A.）在1909年发表的工业区位理论（Theory of the Location of Industries）中提出工厂选址问题，可表达成：求一点B，使得

23、最小，其中， 表示固定地点， 这几个问题都属于求模总和最小的类型，可转化为二阶锥规划问题求解。近十几年来的应用主要有：,设施选址（facility location） 斯坦纳树（Steiner tree）问题 图论控制优化（grasping force optimization） 鲁棒阵列插值（robust array interpolation）,鲁棒多级有价证券（robust multistage portfolio）优化 无风险约束的投资组合优化（portfolio optimization with loss risk constraints）,构架（truss）设计 天线阵列（ant

24、enna array）设计 脉冲响应滤子（impulse response filter）设计等工程设计问题,2. 半定规划（半定优化）,半定规划是指线性函数在对称矩阵的仿射组合半正定的约束下的极小问题,可视为线性规划(简称LP)的推广.半定规划与线性规划有着紧密的联系,但又有重大区别.对于半定规划的研究,要追溯到20世纪40年代.从60年代开始,涌现了许多关于半定规划的理论和最优性条件的文章.1984年,Kar-markar把内点法引入到线性规划,虽然其基本原理不是新的,但是其算法和随后发展起来的内点法在实践中具有良好的表现,且具有多项式时间复杂性,所以Karmarkar的文章在当时具有巨大

25、的冲击力.,1988年,Nesterov和Nemirovsky获得了一个重大突破,他们证明了解线性规划的内点法原则上可以推广到一切凸优化问题,其关键在于对具有自协调性质的函数的认识.而半定规划是一类重要的凸优化问题,它具有易于计算的自协调障碍函数,因而内点法适用.1992年,Nesterov和Nemirovsky把内点法推广到半定规划.自20世纪90年代初开始,人们对半定规划的兴趣逐渐增加.目前半定规划已成为优化方面最热门的领域.这一研究活动之所以被激发起来,是由于半定规划在一些领域的新应用的发现以及新的有效算法的产生,2.1 半定规划(SDP),具有实对称矩阵,的二次型,如果对任何非零向量,

26、都有,成立 ，且具有非零向量,使得,则称,为半正定二次型，矩阵,称 为半正定矩阵，简称半定矩阵，记为 。,给定,对于任何一组实数,表达式,称为,的一个线性组合，,设,为实对称矩阵，,是,的一个线性组合。,则称不等式,为线性对称矩阵不等式。,求一组变量,简称半定规划，记为SDP。,有可能受限于线性不等式，线性对称矩阵不等式，,的最小（最大）的一类问题称为半定规划问题，,其一般标准形式为：,半定约束的线性函数,其中,是,阶全体实对称矩阵的线性空间，,是,阶实对称矩阵，,是实数,，,是,阶对称矩阵变元，,称为目标函数，,称为第,个约束条件。,设,是一个集合，若,则,为半定规划的可行域，也称曲面体。,

27、若,，则称,为可行解。,设,若,则称,为最优解，,为最优值。,例3,或简记为：,例3是把例1中的非负约束变成半定约束，这是半定规划与线性规划的不同之处。,例4,为凸多面体如下图所示：,例 5,可行域为,上述问题在可行域上取不到最小值，因为0是 目标函数的下界，且可行域不是凸多面体，而 为曲面体。即该问题不可行。,上述例题讨论的是半定规划的可行性问题。,2,2 线性规划(LP)与半定规划(SDP)的对比,LP:,SDP:,线性目标，线性约束，向量变元且为非负实向量,线性目标，线性约束，对称矩阵变元且为半定实矩阵,SDP可视为LP的推广，LP的向量分量不等式被矩阵不等式代替。根据半定矩阵的 定义知

28、，SDP也可视为一个线性约束的关于变量的无限集的LP，解LP的原始- 对偶内点法可以推广到SDP。,根据前面两个的图形，LP的可行域为有有限个顶点的凸多面体，故LP有简单易行 且高效的单纯形法；而SDP的可行域为一个曲面体，故SDP尚无直接的，适用的 单纯形法。,例 6,线性规划：,转化为半定规划：,线性规划,半定规划,凸规划,非线性规划,2.3 连续性最优化问题的分类,非线性规划是具有非线性约束条件或目标函数的数学规划。,凸规划是指约束集为凸的和目标函数为约束集上凸函数的数学规划。,2.4 为什么凸在最优化中重要的,一个凸函数没有不为全局极小的局部极小值,一个非凸函数可以被“凸化的”同时保持

29、全局极小值的最优性,一个凸集有非空的相对内部,一个凸集在任何点具有可行方向,凸函数的极小值的存在可以非常方便地用收缩方向进行刻画,一个多面体凸集可用它的极值点和极值方向来刻画,二、对称锥优化,20世纪末国际优化专家开始致力于这一领域的研究工作，主要集中在求解对称锥上线性优化问题的内点算法方面。近几年，人们开始探讨对称锥上的非线性优化问题和非凸优化问题的理论与各种算法。,三、 齐次锥优化,齐次锥的理论早在1963年就有相关研究，但齐次锥优化间题的研究最近才开始。,四、 双曲锥优化,这方面目前只有很少的理论研究，需要寻求合适的工具开展其理论与算法的研究。,相关博士硕士论文,内容相关 题目相关 锥规划 371篇 14 锥优化 160篇 4 半定规划 389篇 63 对称锥优化 58篇 14 齐次锥优化 18篇 1 双曲锥优化 6篇 0,第七章 矩阵规划,在众多的科学领域与社会经济中，很多优化问题的决策变量是一个具有特殊结构的矩阵，这样的优化间题被称为矩阵优化或者矩阵规划。矩阵规划的早期研究可以追溯到1981年，然而真正的研究是在20世纪90年代，它以被誉为2