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

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

《最优化理论与算法完整版课件-PPT.ppt》由会员分享，可在线阅读，更多相关《最优化理论与算法完整版课件-PPT.ppt（902页珍藏版）》请在冰点文库上搜索。

,1,最优化理论与算法,2023/6/13,2,提纲,1.线性规划对偶定理2.非线性规划K-K-T定理3.组合最优化算法设计技巧,使用教材：

最优化理论与算法陈宝林参考书：

数学规划黄红选，韩继业清华大学出版社,2023/6/13,3,其他参考书目,NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979（2ndEdit,1993，3ndEdit，2006）,LinearandNonlinearProgrammingDavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003.,2023/6/13,4,LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.,运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999,组合最优化算法和复杂性CombinatorialOptimization蔡茂诚、刘振宏AlgorithmsandComplexity清华大学出版社，1988Printice-HallInc.,1982/1998,其他参考书目,2023/6/13,5,1,绪论-学科概述,最优化是从所有可能的方案中选择最合理的一种方案,以达到最佳目标的科学.达到最佳目标的方案是最优方案,寻找最优方案的方法-最优化方法（算法）这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.,运筹学的“三个代表”模型理论算法,最优化首先是一种理念,其次才是一种方法.,2023/6/13,6,绪论-运筹学（OperationsResearch-OR）,运筹学方法,2023/6/13,7,优化树,2023/6/13,8,最优化的发展历程,费马:

1638;牛顿,1670,欧拉,1755,Minf（x1x2xn）f（x）=0,2023/6/13,9,欧拉，拉格朗日：

无穷维问题，变分学柯西：

最早应用最速下降法,拉格朗日，1797,Minf（x1x2xn）s.t.gk（x1x2xn）=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等复杂性理论，组合优化迅速发展,电子计算机-最优化,2023/6/13,11,最优化应用举例,具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：

光网络、无线网络，adhoc等.制造业：

钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSIetc.排版（TEX,Latex,etc.）,2023/6/13,12,1.食谱问题,我每天要求一定量的两种维生素，Vc和Vb。

假设这些维生素可以分别从牛奶和鸡蛋中得到。

需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。

2023/6/13,13,1.食谱问题（续）,令x表示要买的奶的量，y为要买的蛋的量。

食谱问题可以写成如下的数学形式：

运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。

求最优安排或计划的问题，称作programming问题。

Min3x+2.5ys.t.2x+4y403x+2y50x,y0.,极小化目标函数可行区域（单纯形）可行解,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,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元的价格出售，则净现金为：

501000-0.3（50-30）1000-0.1501000=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,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。

2023/6/13,24,6.结构设计问题,2023/6/13,25,6.结构设计问题,此应力要求小于材料的屈吸极限，即,解：

桁杆的截面积为：

桁杆的总重量为：

负载2p在每个杆上的分力为：

于是杆截面的应力为：

2023/6/13,圆杆中应力小于等于压杆稳定的临界应力。

由材料力学知：

压杆稳定的临界应力为,由此得稳定约束：

6.结构设计问题,2023/6/13,TPSHUAI,26,另外还要考虑到设计变量d和h有界。

从而得到两杆桁架最优设计问题的数学模型：

6.结构设计问题,2023/6/13,TPSHUAI,27,28,基本概念,在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.,2023/6/13,29,基本概念,最优化问题可写成如下形式:

2023/6/13,30,基本概念,Df1.1设f（x）为目标函数，S为可行域，x0S,若对每一个xS,成立f（x）f（x0）,则称x0为极小化问题minf（x）,xS的最优解（整体最优解）,则称x0为极小化问题minf（x）,xS的局部最优解,Df1.2设f（x）为目标函数，S为可行域，,2023/6/13,31,Thankyouverymuchforyourattendance!

优化软件http:

/www-neos.mcs.anl.gov/http:

/neos.mcs.anl.gov/neos/solvers/index.html,2023/6/13,TPSHUAI,32,最优化理论与算法,帅天平北京邮电大学数学系Email:

Tel:

62281308,Rm:

主楼8141预备知识,2023/6/13,TPSHUAI,32,TPSHUAI,33,1，预备知识,1.线性空间2.范数3.集合与序列4.矩阵的分解与校正,2023/6/13,TPSHUAI,33,TPSHUAI,34,1.线性空间,Df1.3:

给定一非空集合G以及在G上的一种代数运算+:

GGG（称为加法）,若下述条件成立:

则称为一个群.若还满足对任意的a,bG,有a+b=b+a,则称为一个阿贝尔群（&交换群）,2023/6/13,TPSHUAI,34,TPSHUAI,35,1.线性空间,Df1.4:

给定一非空集合V和一个域F,并定义两种运算加法+:

VVV以及数乘:

FVV.若构成一交换群,且两种运算满足下面性质:

则称V在域F上关于加法和数乘运算构成一线性空间,简称V为F上的线性空间.记为V（F）.若V的非空子集合S关于加法和数乘运算在F上也构成一线性空间,则S称为F上的线性子空间.,2023/6/13,TPSHUAI,35,TPSHUAI,36,1.线性空间,例子,2023/6/13,TPSHUAI,36,TPSHUAI,37,1.线性空间,2023/6/13,TPSHUAI,37,TPSHUAI,38,1.线性空间,Th1.1线性空间V（F）的非空子集S的线性扩张L（S）是V中包含S的最小子空间.,2023/6/13,TPSHUAI,38,TPSHUAI,39,1.线性空间,2023/6/13,TPSHUAI,39,TPSHUAI,40,1.线性空间,2023/6/13,TPSHUAI,40,TPSHUAI,41,2.范数,2023/6/13,TPSHUAI,41,TPSHUAI,42,2.范数,2023/6/13,TPSHUAI,42,TPSHUAI,43,2.范数,2023/6/13,TPSHUAI,43,TPSHUAI,44,3.集合与序列,2023/6/13,TPSHUAI,44,TPSHUAI,45,3，集合与序列,2023/6/13,TPSHUAI,45,TPSHUAI,46,3.集合与序列,2023/6/13,TPSHUAI,46,TPSHUAI,47,3.集合与序列,2023/6/13,TPSHUAI,47,TPSHUAI,48,4.矩阵的分解与校正,Th1.5若n阶矩阵A可逆，则存在一个排列矩阵P,单位下三角矩阵L和上三角矩阵U，使得PA=LU,2023/6/13,TPSHUAI,48,TPSHUAI,49,4.矩阵的分解与校正,Th1.6设A为对称正定矩阵，则

（1）矩阵A可唯一的分解成A=LDLT,其中L为单位下三角矩阵，D为对角矩阵

（2）存在可逆的下三角矩阵L，使得A=LLT.当L的对角元素为正时，分解是唯一的。

（Cholesky分解）,2023/6/13,TPSHUAI,49,TPSHUAI,50,4.矩阵的分解与校正,2023/6/13,TPSHUAI,50,TPSHUAI,51,4.矩阵的分解与校正,2023/6/13,TPSHUAI,51,TPSHUAI,52,5.函数的可微性与展开,2023/6/13,TPSHUAI,52,TPSHUAI,53,5.函数的可微性与展开,当f（x）在x点存在二阶偏导时,函数f在点x的Hesse矩阵定义为,2023/6/13,TPSHUAI,53,TPSHUAI,54,5.函数的可微性与展开,2023/6/13,TPSHUAI,54,TPSHUAI,55,5.函数的可微性与展开,2023/6/13,TPSHUAI,55,TPSHUAI,56,5.函数的可微性与展开,2023/6/13,TPSHUAI,56,TPSHUAI,57,最优化理论与算法,帅天平北京邮电大学数学系Email:

Tel:

62281308,Rm:

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

2.凸集与凸函数,2023/6/13,TPSHUAI,62,TPSHUAI,63,2.凸集与凸函数,多面体（polyhedralset）是有限闭半空间的交.（可表为Axb）.,2023/6/13,TPSHUAI,63,TPSHUAI,64,2.凸集与凸函数,2023/6/13,TPSHUAI,64,TPSHUAI,65,多面集x|Ax0也是凸锥，称为多面锥。

2.凸集与凸函数,由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合,K（S）=x|0,xS,是包含S的最小凸锥.,锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间.,约定:

非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合（称为凸锥组合）的所有点所构成的集合,记为coneS.若S凸,则,coneS=K（S）0,2023/6/13,TPSHUAI,65,TPSHUAI,66,2.凸集与凸函数,Df2.5非空凸集中的点x称为极点,若x=x1+（1-）x2,（0,1）,x1,x2S,则x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.,由上可知,任何有界凸集中任一点都可表成极点的凸组合.,2023/6/13,TPSHUAI,66,TPSHUAI,67,2.凸集与凸函数,Def2.6.设非空凸集SRn,Rn中向量d0称为S的一个回收方向（方向）,若对每一xS,R（x.d）=x+d|0S.S的所有方向构成的尖锥称为S的回收锥,记为0+S,方向d1和d2称为S的两个不同的方向,若对任意0,都有d1d2；方向d称为S的极方向extremedirection,若d=d1+（1-）d2,（0,1）,d1,d2是S的两个方向,则有d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合,2023/6/13,TPSHUAI,67,TPSHUAI,68,2.凸集与凸函数,2023/6/13,TPSHUAI,68,TPSHUAI,69,2.凸集与凸函数,表示定理,Th2.4若多面体P=xRn|Axb,r（A）=n则:

则,（3）指标集J是空集当且仅当P是有界集合,即多胞形.,2023/6/13,TPSHUAI,69,TPSHUAI,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,TPSHUAI,70,TPSHUAI,71,2.2凸集分离定理,2.凸集与凸函数,2023/6/13,TPSHUAI,71,TPSHUAI,72,2.凸集与凸函数,2023/6/13,TPSHUAI,72,TPSHUAI,73,证明：

令,2.凸集与凸函数,2023/6/13,TPSHUAI,73,TPSHUAI,74,所以为柯西列，必有极限,且由S为闭集知。

此极限点必在S中。

2.凸集与凸函数,下证明唯一性,2023/6/13,TPSHUAI,74,TPSHUAI,75,2.凸集与凸函数,2023/6/13,TPSHUAI,75,TPSHUAI,76,2.凸集与凸函数,2023/6/13,TPSHUAI,76,TPSHUAI,77,2.凸集与凸函数,证明提纲,2023/6/13,TPSHUAI,77,TPSHUAI,78,由此可得,2.凸集与凸函数,2023/6/13,TPSHUAI,78,TPSHUAI,79,2.凸集与凸函数,Th2.7表明，S为闭凸集，yS，则y与S可分离。

若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。

实际上我们有下述定理,2023/6/13,TPSHUAI,79,TPSHUAI,80,证明,2.凸集与凸函数,2023/6/13,TPSHUAI,80,TPSHUAI,81,推论2.2：

设S为Rn中的非空集合，yS,则存在非零向量p，使对xclS,pT（x-y）0,2.凸集与凸函数,2023/6/13,TPSHUAI,81,TPSHUAI,82,2.凸集与凸函数,2023/6/13,TPSHUAI,82,TPSHUAI,83,2.凸集与凸函数,2023/6/13,TPSHUAI,83,TPSHUAI,84,作为凸集分离定理的应用，下面介绍两个择一定理：

Farkas定理和Gordan定理，它们在最优化理论中是很有用的。

2.凸集与凸函数,2.3择一定理,2023/6/13,TPSHUAI,84,TPSHUAI,85,2.凸集与凸函数,2023/6/13,TPSHUAI,85,TPSHUAI,86,2.凸集与凸函数,2023/6/13,TPSHUAI,86,TPSHUAI,87,2.凸集与凸函数,2023/6/13,TPSHUAI,87,TPSHUAI,88,2.凸集与凸函数,2023/6/13,TPSHUAI,88,TPSHUAI,89,2.凸集与凸函数,2023/6/13,TPSHUAI,89,TPSHUAI,90,2.凸集与凸函数,2023/6/13,TPSHUAI,90,TPSHUAI,91,2.凸集与凸函数,2023/6/13,TPSHUAI,91,TPSHUAI,92,2.凸集与凸函数,2023/6/13,TPSHUAI,92,TPSHUAI,93,2.凸集与凸函数,2.4凸函数,Df2.10设SRn是非空凸集,函数f:

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

2.凸集与凸函数,2023/6/13,TPSHUAI,95,TPSHUAI,96,2.凸集与凸函数,2023/6/13,TPSHUAI,96,TPSHUAI,97,2.凸集与凸函数,2023/6/13,TPSHUAI,97,TPSHUAI,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,TPSHUAI,98,TPSHUAI,99,2.凸集与凸函数,设S为Rn中的非空凸集,则f（x）是凸的当且仅当上镜图epif=（x,y）|xS,yR,yf（x）是凸集,对上镜图事实上我们有如下定理,2023/6/13,TPSHUAI,99,TPSHUAI,100,2.凸集与凸函数,2023/6/13,TPSHUAI,100,TPSHUAI,101,定理2.14设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。

2.凸集与凸函数,2023/6/13,TPSHUAI,101,TPSHUAI,102,2.凸集与凸函数,2023/6/13,TPSHUAI,102,TPSHUAI,103,2.凸集与凸函数,2023/6/13,TPSHUAI,103,TPSHUAI,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,TPSHUAI,104,TPSHUAI,105,2.凸集与凸函数,2023/6/13,TPSHUAI,105,TPSHUAI,106,2.凸集与凸函数,Th2.16*.设S是Rn上的非空开凸集,f（x）为S到R上的可微函数.则f（x）是凸函数当且仅当任意的x1,x2S,有（f（x2）-f（x1）（x2-x1）0.类似的,f严格凸当且仅当对任意相异的x1,x2S,（f（x2）-f（x1）（x2-x1）0.,2023/6/13,TPSHUAI,106,TPSHUAI,107,2.凸集与凸函数,2023/6/13,TPSHUAI,107,TPSHUAI,108,2.凸集与凸函数,Th2.17设S是Rna上的非空开凸集,f（x）为S到R上的二次可微函数.则

（1）f（x）是凸函数当且仅当S上每一点的Hessian矩阵是半正定的.

（2）f（x）是严格凸函数当且仅当S上每一点的Hessian矩阵是正定的.,2023/6/13,TPSHUAI,108,TPSHUAI,109,凸规划,2.凸集与凸函数,2023/6/13,TPSHUAI,109,TPSHUAI,110,最优化理论与算法,帅天平北京邮电大学数学系Email:

Tel:

62281308,Rm:

主楼8143，线性规划的基本性质,2023/6/13,TPSHUAI,110,TPSHUAI,111,第二章线性规划的基本性质,标准形式与图解法基本性质,2023/6/13,TPSHUAI,111,TPSHUAI,112,我每天要求一定量的两种维生素，Vc和Vb。

假设这些维生素可以分别从牛奶和鸡蛋中得到。

需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。

2.线性规划-例子-食谱问题,2023/6/13,TPSHUAI,112,TPSHUAI,113,令x表示要买的奶的量，y为要买的蛋的量。

食谱问题可以写成如下的数学形式：

Min3x+2.5ys.t.2x+4y403x+2y50x,y0.,极小化目标函数可行区域（单纯形）可行解,2.线性规划-例子-食谱问题,2023/6/13,TPSHUAI,113,TPSHUAI,114,1标准形式,矩阵表示,其中A是mn矩阵，c是n维行向量，b是m维列向量。

注：

为计算需要，一般假设b0.否则，可在方程两端乘以（-1）即可化为非负。

2.线性规划-形式,2023/