最优化理论与算法完整版课件-PPT.ppt

1、,1,最优化理论与算法,2023/6/13,2,提纲,1.线性规划 对偶定理2.非线性规划 K-K-T 定理3.组合最优化 算法设计技巧,使用教材：最优化理论与算法 陈宝林参考书：数学规划 黄红选，韩继业 清华大学出版社,2023/6/13,3,其他参考书目,Nonlinear Programming-Theory and AlgorithmsMokhtar S.Bazaraa,C.M.ShettyJohn Wiley&Sons,Inc.1979(2nd Edit,1993，3nd Edit，2006),Linear and Nonlinear Programming David G.Luen

2、bergerAddison-Wesley Publishing Company,2nd Edition,1984/2003.,2023/6/13,4,Linear Programming and Network Flows M.S.Bazaraa,J.J.Jarvis,John Wiley&Sons,Inc.,1977.,运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999,组合最优化算法和复杂性 Combinatorial Optimization 蔡茂诚、刘振宏 Algorithms and Complexity 清华大学出版社，1988 Printice-Hall Inc.,1982/

3、1998,其他参考书目,2023/6/13,5,1,绪论-学科概述,最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学.达到最佳目标的方案是最优方案,寻找最优 方案的方法-最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.,运筹学的“三个代表”模型理论算法,最优化首先是一种理念,其次才是一种方法.,2023/6/13,6,绪论-运筹学（Operations Research-OR）,运筹学方法,2023/6/13,7,优化树,2023/6/13,8,最优化的发展历程,费马:1638;牛顿,1670,欧拉,1755,Min f(x1

4、 x2 xn)f(x)=0,2023/6/13,9,欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法,拉格朗日，1797,Min f(x1 x2 xn)s.t.gk(x1 x2 xn)=0,k=1,2,m,2023/6/13,10,1930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法，冯 诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划 6-70年代：Cook等复

5、杂性理论，组合优化迅速发展,电子计算机-最优化,2023/6/13,11,最优化应用举例,具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，ad hoc 等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSI etc.排版（TEX,Latex,etc.）,2023/6/13,12,1.食谱问题,我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。,需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。,2023/6/13,13,

6、1.食谱问题（续）,令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：,运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。,Min 3x+2.5y s.t.2x+4y 40 3x+2y 50 x,y 0.,极小化目标函数可行区域（单纯形）可行解,2023/6/13,14,2 运输问题,设某种物资有m个产地A1,A2,Am,各产地的产量是a1,a2,am;有 n个销地B1,B2,Bn.各销地的销量是b1,b2,bn.假定从产地Ai(i=1,2,m)到销地Bj(j=1

7、,2,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？,如果运输问题的总产量等于总销量，即有,则称该运输问题为产销平衡问题；反之，称产销不平衡问题。,2023/6/13,15,令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：,2 运输问题（续）,2023/6/13,16,以价格qi 购买了si份股票i,i=1,2,n股票i的现价是pi你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50

8、 1000-0.3(50-30)1000-0.150 1000=39000,3 税下投资问题,2023/6/13,17,我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。,3 税下投资问题（续）,2023/6/13,18,4 选址问题（1）,实例:一组潜在位置（地址）,一组顾客集合及相应的 利润和费用数据；解:设施开放(使用)的数目，他们的位置，以及顾客 被哪个设施服务的具体安排方案；目标：总的利润最大化。,数据与约束J=1,2,n:放置设施的可能的潜在位置集合I=1,2,m:顾客集合,其要求的服务需要某设施所提 供.,2023/6/13,19,4 选址问题（2）,2023/6/13,

9、20,4选址问题（3）,2023/6/13,21,5负载平衡(1),实例:网络G(V,E)及一组m 个数的集合s,d0，表示 连接源点 s与汇点d 之间的流量解:s,d0的一组路由,即G(V,E)中m 条s 与 d间的路,表示连接s与d 的负载流量的路径。目标:极小化网络负载,2023/6/13,22,5 负载平衡(2),2023/6/13,23,6.结构设计问题,两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,

10、2023/6/13,24,6.结构设计问题,2023/6/13,25,6.结构设计问题,此应力要求小于材料的屈吸极限，即,解：桁杆的截面积为：,桁杆的总重量为：,负载2p在每个杆上的分力为：,于是杆截面的应力为：,2023/6/13,圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为,由此得稳定约束：,6.结构设计问题,2023/6/13,TP SHUAI,26,另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：,6.结构设计问题,2023/6/13,TP SHUAI,27,28,基本概念,在上述例子中,有的目标函数和约束函数都是线性的,称之为线性

11、规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.,2023/6/13,29,基本概念,最优化问题可写成如下形式:,2023/6/13,30,基本概念,Df 1.1 设f(x)为目标函数，S为可行域，x0S,若对每一个x S,成立f(x)f(x0),则称x0为极小化问题min f(x),x S的最优解（整体最优解）,则称x0为极小化问题min f(x),x S的局部最优解,Df 1.2 设f(x)为目标函数，S为可行域，,2023/6/13,3

12、1,Thank you very much for your attendance!,优化软件 http:/www-neos.mcs.anl.gov/http:/neos.mcs.anl.gov/neos/solvers/index.html,2023/6/13,TP SHUAI,32,最优化理论与算法,帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼814 1 预备知识,2023/6/13,TP SHUAI,32,TP SHUAI,33,1，预备知识,1.线性空间2.范数3.集合与序列4.矩阵的分解与校正,2023/6/13,TP SHUAI,33,TP SHUAI

13、,34,1.线性空间,Df 1.3:给定一非空集合G以及在G上的一种代数运算+:GGG(称为加法),若下述条件成立:,则称为一个群.若还满足对任意的a,bG,有a+b=b+a,则称为一个阿贝尔群(&交换群),2023/6/13,TP SHUAI,34,TP SHUAI,35,1.线性空间,Df 1.4:给定一非空集合V和一个域F,并定义两种运算加法+:VVV以及数乘:FVV.若构成一交换群,且两种运算满足下面性质:,则称V在域F上关于加法和数乘 运算构成一线性空间,简称V为F上的线性空间.记为V(F).若V的非空子集合S关于加法和数乘运算在F上也构成一线性空间,则S称为F上的线性子空间.,20

14、23/6/13,TP SHUAI,35,TP SHUAI,36,1.线性空间,例子,2023/6/13,TP SHUAI,36,TP SHUAI,37,1.线性空间,2023/6/13,TP SHUAI,37,TP SHUAI,38,1.线性空间,Th1.1 线性空间V(F)的非空子集S的线性扩张L(S)是V中包含S的最小子空间.,2023/6/13,TP SHUAI,38,TP SHUAI,39,1.线性空间,2023/6/13,TP SHUAI,39,TP SHUAI,40,1.线性空间,2023/6/13,TP SHUAI,40,TP SHUAI,41,2.范数,2023/6/13,TP

15、 SHUAI,41,TP SHUAI,42,2.范数,2023/6/13,TP SHUAI,42,TP SHUAI,43,2.范数,2023/6/13,TP SHUAI,43,TP SHUAI,44,3.集合与序列,2023/6/13,TP SHUAI,44,TP SHUAI,45,3，集合与序列,2023/6/13,TP SHUAI,45,TP SHUAI,46,3.集合与序列,2023/6/13,TP SHUAI,46,TP SHUAI,47,3.集合与序列,2023/6/13,TP SHUAI,47,TP SHUAI,48,4.矩阵的分解与校正,Th1.5 若n阶矩阵A可逆，则存在一个排

16、列矩阵P,单位下三角矩阵L和上三角矩阵U，使得PA=LU,2023/6/13,TP SHUAI,48,TP SHUAI,49,4.矩阵的分解与校正,Th1.6 设A为对称正定矩阵，则（1）矩阵A可唯一的分解成A=LDLT,其中L为单位下三角矩阵，D为对角矩阵（2）存在可逆的下三角矩阵L，使得A=LLT.当L的对角元素为正时，分解是唯一的。(Cholesky分解),2023/6/13,TP SHUAI,49,TP SHUAI,50,4.矩阵的分解与校正,2023/6/13,TP SHUAI,50,TP SHUAI,51,4.矩阵的分解与校正,2023/6/13,TP SHUAI,51,TP SH

17、UAI,52,5.函数的可微性与展开,2023/6/13,TP SHUAI,52,TP SHUAI,53,5.函数的可微性与展开,当f(x)在x点存在二阶偏导时,函数f在点x的Hesse矩阵定义为,2023/6/13,TP SHUAI,53,TP SHUAI,54,5.函数的可微性与展开,2023/6/13,TP SHUAI,54,TP SHUAI,55,5.函数的可微性与展开,2023/6/13,TP SHUAI,55,TP SHUAI,56,5.函数的可微性与展开,2023/6/13,TP SHUAI,56,TP SHUAI,57,最优化理论与算法,帅天平北京邮电大学数学系Email:,T

18、el:62281308,Rm:主楼8142，凸分析与凸函数,2023/6/13,TP SHUAI,57,TP SHUAI,58,2.凸集与凸函数,2.1 凸集与锥,2023/6/13,TP SHUAI,58,TP SHUAI,59,2.凸集与凸函数,2023/6/13,TP SHUAI,59,TP SHUAI,60,2.凸集与凸函数,2023/6/13,TP SHUAI,60,TP SHUAI,61,2.凸集与凸函数,2023/6/13,TP SHUAI,61,TP SHUAI,62,运用定义不难验证如下命题：,2.凸集与凸函数,2023/6/13,TP SHUAI,62,TP SHUAI,6

19、3,2.凸集与凸函数,多面体(polyhedral set)是有限闭半空间的交.(可表为 Axb).,2023/6/13,TP SHUAI,63,TP SHUAI,64,2.凸集与凸函数,2023/6/13,TP SHUAI,64,TP SHUAI,65,多面集 x|Ax0也是凸锥，称为多面锥。,2.凸集与凸函数,由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合,K(S)=x|0,xS,是包含S的最小凸锥.,锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间.,约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)

20、的所有点所构成的集合,记为coneS.若S凸,则,coneS=K(S)0,2023/6/13,TP SHUAI,65,TP SHUAI,66,2.凸集与凸函数,Df 2.5 非空凸集中的点 x 称为极点,若 x=x1+(1-)x2,(0,1),x1,x2 S,则 x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.,由上可知,任何有界凸集中任一点都可表成极点的凸组合.,2023/6/13,TP SHUAI,66,TP SHUAI,67,2.凸集与凸函数,Def 2.6.设非空凸集SRn,Rn中向量d0 称为S的一个回收方向(方向),若对每一 xS,R(x.d)=x+d|0 S.S的所有

21、方向构成的尖锥称为S的回收锥,记为0+S,方向d1和d2 称为S的两个不同的方向,若对任意0,都有 d1d2；方向d称为S的极方向extreme direction,若 d=d1+(1-)d2,(0,1),d1,d2 是S的两个方向,则有 d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合,2023/6/13,TP SHUAI,67,TP SHUAI,68,2.凸集与凸函数,2023/6/13,TP SHUAI,68,TP SHUAI,69,2.凸集与凸函数,表示定理,Th2.4 若多面体P=xRn|Axb,r(A)=n则:,则,(3)指标集J是空集当且仅当P是有界集合,即多胞形.,2

22、023/6/13,TP SHUAI,69,TP SHUAI,70,2.凸集与凸函数,表示定理直观描述:设 X 为非空多面体.则存在有限个极点 x1,xk,k0.进一步,存在有限个极方向 d1,dl,l0 当且仅当 X 无界.进而,xX 的充要条件是 x 可以表为 x1,xk 的凸组合和d1,dl的非负线性组合(凸锥组合).,推论2.1 若多面体S=x|Ax=b,x0非空,则S必有极点.,2023/6/13,TP SHUAI,70,TP SHUAI,71,2.2 凸集分离定理,2.凸集与凸函数,2023/6/13,TP SHUAI,71,TP SHUAI,72,2.凸集与凸函数,2023/6/1

23、3,TP SHUAI,72,TP SHUAI,73,证明：令,2.凸集与凸函数,2023/6/13,TP SHUAI,73,TP SHUAI,74,所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。,2.凸集与凸函数,下证明唯一性,2023/6/13,TP SHUAI,74,TP SHUAI,75,2.凸集与凸函数,2023/6/13,TP SHUAI,75,TP SHUAI,76,2.凸集与凸函数,2023/6/13,TP SHUAI,76,TP SHUAI,77,2.凸集与凸函数,证明提纲,2023/6/13,TP SHUAI,77,TP SHUAI,78,由此可得,2.凸集与凸函

24、数,2023/6/13,TP SHUAI,78,TP SHUAI,79,2.凸集与凸函数,Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理,2023/6/13,TP SHUAI,79,TP SHUAI,80,证明,2.凸集与凸函数,2023/6/13,TP SHUAI,80,TP SHUAI,81,推论2.2：设S为Rn 中的非空集合，yS,则存在非零向量p，使对xclS,pT(x-y)0,2.凸集与凸函数,2023/6/13,TP SHUAI,81,TP SHUAI,82,2.凸集与凸函数,2023/6/13

25、,TP SHUAI,82,TP SHUAI,83,2.凸集与凸函数,2023/6/13,TP SHUAI,83,TP SHUAI,84,作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很有用的。,2.凸集与凸函数,2.3 择一定理,2023/6/13,TP SHUAI,84,TP SHUAI,85,2.凸集与凸函数,2023/6/13,TP SHUAI,85,TP SHUAI,86,2.凸集与凸函数,2023/6/13,TP SHUAI,86,TP SHUAI,87,2.凸集与凸函数,2023/6/13,TP SHUAI,87,TP SHU

26、AI,88,2.凸集与凸函数,2023/6/13,TP SHUAI,88,TP SHUAI,89,2.凸集与凸函数,2023/6/13,TP SHUAI,89,TP SHUAI,90,2.凸集与凸函数,2023/6/13,TP SHUAI,90,TP SHUAI,91,2.凸集与凸函数,2023/6/13,TP SHUAI,91,TP SHUAI,92,2.凸集与凸函数,2023/6/13,TP SHUAI,92,TP SHUAI,93,2.凸集与凸函数,2.4 凸函数,Df2.10 设SRn是非空凸集,函数f:SR,若对任意x1,x2S,和每一(0,1)都有 f(x1+(1-)x2)f(x1

27、)+(1-)f(x2)则称f是S上的凸函数.若上面的不等式对于xy严格成立,则称f是S上的严格凸函数.若-f是S上的凸函数,则称f是S上的凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数.,2.4.1 基本性质,2023/6/13,TP SHUAI,93,TP SHUAI,94,2.凸集与凸函数,2023/6/13,TP SHUAI,94,TP SHUAI,95,Th2.13 设 f 是一凸函数，则对任意的xRn 和d(0)Rn，f在x处沿方向d的方向导数存在。,2.凸集与凸函数,2023/6/13,TP SHUAI,95,TP SHUAI,96,2.凸集与凸函数,2023/6/13

28、,TP SHUAI,96,TP SHUAI,97,2.凸集与凸函数,2023/6/13,TP SHUAI,97,TP SHUAI,98,命题2.3 设f是定义在凸集S上的凸函数，则(1)所有凸函数f的集合关于凸锥组合运算是封闭的,即(a)实数0，则f也是定义在S上的凸函数(b)设f1和f2是定义在凸集S上的凸函数，则f1+f2也是定义在S上的凸函数,2.凸集与凸函数,(2)函数f在开集intS内是连续的.(3)函数f的水平集L(f,)=x|xS,f(x),R 和上镜图epi(f)=(x,y)|xS,yR,yf(x)都是凸集,2023/6/13,TP SHUAI,98,TP SHUAI,99,2

29、.凸集与凸函数,设S 为Rn中的非空凸集,则 f(x)是凸的当且仅当上镜图 epif=(x,y)|xS,yR,yf(x)是凸集,对上镜图事实上我们有如下定理,2023/6/13,TP SHUAI,99,TP SHUAI,100,2.凸集与凸函数,2023/6/13,TP SHUAI,100,TP SHUAI,101,定理2.14 设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。,2.凸集与凸函数,2023/6/13,TP SHUAI,101,TP SHUAI,102,2.凸集与凸函数,2023/6/13,TP SHUAI,102,TP S

30、HUAI,103,2.凸集与凸函数,2023/6/13,TP SHUAI,103,TP SHUAI,104,2.凸集与凸函数,2.5.2 凸函数的判别,Th2.16.设S 是Rn 中的非空开凸集,f(x):SR 是可微的函数 则 f(x)是凸函数当且仅当对任意的 x*S,我们有f(x)f(x*)+f(x*)(x-x*),任意 xS.类似的,f(x)严格凸当且仅当对每一 x*S,f(x)f(x*)+f(x*)(x-x*),任意 xS.,2.4.2 凸函数的判别,2023/6/13,TP SHUAI,104,TP SHUAI,105,2.凸集与凸函数,2023/6/13,TP SHUAI,105,

31、TP SHUAI,106,2.凸集与凸函数,Th 2.16*.设S 是 Rn 上的非空开凸集,f(x)为 S 到 R上的可微函数.则 f(x)是凸函数当且仅当任意的 x1,x2 S,有(f(x2)-f(x1)(x2-x1)0.类似的,f 严格凸当且仅当对任意相异的 x1,x2 S,(f(x2)-f(x1)(x2-x1)0.,2023/6/13,TP SHUAI,106,TP SHUAI,107,2.凸集与凸函数,2023/6/13,TP SHUAI,107,TP SHUAI,108,2.凸集与凸函数,Th 2.17 设S 是 Rn a上的非空开凸集,f(x)为 S 到 R上的二次可微函数.则(

32、1)f(x)是凸函数当且仅当S上每一点的Hessian矩阵是半正定的.(2)f(x)是严格凸函数当且仅当S上每一点的Hessian矩阵是正定的.,2023/6/13,TP SHUAI,108,TP SHUAI,109,凸规划,2.凸集与凸函数,2023/6/13,TP SHUAI,109,TP SHUAI,110,最优化理论与算法,帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼8143，线性规划的基本性质,2023/6/13,TP SHUAI,110,TP SHUAI,111,第二章 线性规划的基本性质,标准形式与图解法基本性质,2023/6/13,TP SHUAI

33、,111,TP SHUAI,112,我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。,需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。,2.线性规划-例子-食谱问题,2023/6/13,TP SHUAI,112,TP SHUAI,113,令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：,Min 3x+2.5y s.t.2x+4y 40 3x+2y 50 x,y 0.,极小化目标函数可行区域（单纯形）可行解,2.线性规划-例子-食谱问题,2023/6/13,TP SHUAI,113,TP SHUAI,114,1标准形式,矩阵表示,其中A是mn矩阵，c是n维行向量，b是m维列向量。,注：为计算需要，一般假设b0.否则，可在方程两端乘以(-1)即可化为非负。,2.线性规划-形式,2023/