最优化理论与算法完整版.ppt
《最优化理论与算法完整版.ppt》由会员分享,可在线阅读,更多相关《最优化理论与算法完整版.ppt(902页珍藏版)》请在三一办公上搜索。
1、TP SHUAI,1,最优化理论与算法,TP SHUAI,2,提纲,1.线性规划 对偶定理2.非线性规划 K-K-T 定理3.组合最优化 算法设计技巧,使用教材:最优化理论与算法 陈宝林参考书:数学规划 黄红选,韩继业 清华大学出版社,TP SHUAI,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
2、G.LuenbergerAddison-Wesley Publishing Company,2nd Edition,1984/2003.,TP SHUAI,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.,
3、1982/1998,其他参考书目,TP SHUAI,5,1,绪论-学科概述,最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学.达到最佳目标的方案是最优方案,寻找最优 方案的方法-最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.,运筹学的“三个代表”模型理论算法,最优化首先是一种理念,其次才是一种方法.,TP SHUAI,6,绪论-运筹学(Operations Research-OR),TP SHUAI,7,优化树,TP SHUAI,8,最优化的发展历程,费马:1638;牛顿,1670,欧拉,1755,Min f(x1 x2 x
4、n)f(x)=0,TP SHUAI,9,欧拉,拉格朗日:无穷维问题,变分学柯西:最早应用最速下降法,拉格朗日,1797,Min f(x1 x2 xn)s.t.gk(x1 x2 xn)=0,k=1,2,m,TP SHUAI,10,1930年代,康托诺维奇:线性规划1940年代,Dantzig:单纯形方法,冯 诺依曼:对策论1950年代,Bellman:动态规划,最优性原理;KKT条件;1960年代:Zoutendijk,Rosen,Carroll,etc.非线性规划算法,Duffin,Zener等几何规划,Gomory,整数规划,Dantzig等随机规划 6-70年代:Cook等复杂性理论,组合
5、优化迅速发展,电子计算机-最优化,TP SHUAI,11,最优化应用举例,具有广泛的实用性运输问题,车辆调度,员工安排,空运控制等工程设计,结构设计等资源分配,生产计划等通信:光网络、无线网络,ad hoc 等.制造业:钢铁生产,车间调度等医药生产,化工处理等电子工程,集成电路VLSI etc.排版(TEX,Latex,etc.),TP SHUAI,12,1.食谱问题,我每天要求一定量的两种维生素,Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。,需要确定每天喝奶和吃蛋的量,目标以便以最低可能的花费购买这些食物,而满足最低限度的维生素需求量。,TP SHUAI,13,1.食谱问题(续),
6、令x表示要买的奶的量,y为要买的蛋的量。食谱问题可以写成如下的数学形式:,运筹学工作者参与建立关于何时出现最小费用(或者最大利润)的排序,或者计划,早期被标示为programs。求最优安排或计划的问题,称作programming问题。,Min 3x+2.5y s.t.2x+4y 40 3x+2y 50 x,y 0.,极小化目标函数可行区域(单纯形)可行解,TP SHUAI,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)运输单位物品
7、的运价是cij问怎样调运这些物品才能使总运费最小?,如果运输问题的总产量等于总销量,即有,则称该运输问题为产销平衡问题;反之,称产销不平衡问题。,TP SHUAI,15,令xij表示由产地Ai运往销地Bj的物品数量,则产销平衡问题的数学模型为:,2 运输问题(续),TP SHUAI,16,以价格qi 购买了si份股票i,i=1,2,n股票i的现价是pi你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30%扣除税金后,你的现金仍然比购买股票前增多支付1%的交易费用例如:将原先以每股30元的价格买入1000股股票,以每股50元的价格出售,则净现金为:50 1000-0.3(50-
8、30)1000-0.150 1000=39000,3 税下投资问题,TP SHUAI,17,我们的目标是要使预期收益最大。Xi:当前抛出股票i的数量。,3 税下投资问题(续),TP SHUAI,18,4 选址问题(1),实例:一组潜在位置(地址),一组顾客集合及相应的 利润和费用数据;解:设施开放(使用)的数目,他们的位置,以及顾客 被哪个设施服务的具体安排方案;目标:总的利润最大化。,数据与约束J=1,2,n:放置设施的可能的潜在位置集合I=1,2,m:顾客集合,其要求的服务需要某设施所提 供.,TP SHUAI,19,4 选址问题(2),TP SHUAI,20,4选址问题(3),TP SH
9、UAI,21,5负载平衡(1),实例:网络G(V,E)及一组m 个数的集合s,d0,表示 连接源点 s与汇点d 之间的流量解:s,d0的一组路由,即G(V,E)中m 条s 与 d间的路,表示连接s与d 的负载流量的路径。目标:极小化网络负载,TP SHUAI,22,5 负载平衡(2),TP SHUAI,23,6.结构设计问题,两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架,其顶点承受负载为2p,两支座之间的水平距离为2L,圆杆的壁厚为B,杆的比重为,弹性模量为E,屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,TP SHUAI,24,6.结构设计问题
10、,TP SHUAI,25,6.结构设计问题,此应力要求小于材料的屈吸极限,即,解:桁杆的截面积为:,桁杆的总重量为:,负载2p在每个杆上的分力为:,于是杆截面的应力为:,圆杆中应力小于等于压杆稳定的临界应力。由材料力学知:压杆稳定的临界应力为,由此得稳定约束:,6.结构设计问题,另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型:,6.结构设计问题,TP SHUAI,28,基本概念,在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行
11、集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.,TP SHUAI,29,基本概念,最优化问题可写成如下形式:,TP SHUAI,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为可行域,,TP SHUAI,31,Thank you very much for your attendance!,优化软件,TP SHUAI,32,最优化理论与算法,帅
12、天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼814 1 预备知识,TP SHUAI,33,1,预备知识,1.线性空间2.范数3.集合与序列4.矩阵的分解与校正,TP SHUAI,34,1.线性空间,Df 1.3:给定一非空集合G以及在G上的一种代数运算+:GGG(称为加法),若下述条件成立:,则称为一个群.若还满足对任意的a,bG,有a+b=b+a,则称为一个阿贝尔群(&交换群),TP SHUAI,35,1.线性空间,Df 1.4:给定一非空集合V和一个域F,并定义两种运算加法+:VVV以及数乘:FVV.若构成一交换群,且两种运算满足下面性质:,则称V在域F上关于加
13、法和数乘 运算构成一线性空间,简称V为F上的线性空间.记为V(F).若V的非空子集合S关于加法和数乘运算在F上也构成一线性空间,则S称为F上的线性子空间.,TP SHUAI,36,1.线性空间,例子,TP SHUAI,37,1.线性空间,TP SHUAI,38,1.线性空间,Th1.1 线性空间V(F)的非空子集S的线性扩张L(S)是V中包含S的最小子空间.,TP SHUAI,39,1.线性空间,TP SHUAI,40,1.线性空间,TP SHUAI,41,2.范数,TP SHUAI,42,2.范数,TP SHUAI,43,2.范数,TP SHUAI,44,3.集合与序列,TP SHUAI,4
14、5,3,集合与序列,TP SHUAI,46,3.集合与序列,TP SHUAI,47,3.集合与序列,TP SHUAI,48,4.矩阵的分解与校正,Th1.5 若n阶矩阵A可逆,则存在一个排列矩阵P,单位下三角矩阵L和上三角矩阵U,使得PA=LU,TP SHUAI,49,4.矩阵的分解与校正,Th1.6 设A为对称正定矩阵,则(1)矩阵A可唯一的分解成A=LDLT,其中L为单位下三角矩阵,D为对角矩阵(2)存在可逆的下三角矩阵L,使得A=LLT.当L的对角元素为正时,分解是唯一的。(Cholesky分解),TP SHUAI,50,4.矩阵的分解与校正,TP SHUAI,51,4.矩阵的分解与校正
15、,TP SHUAI,52,5.函数的可微性与展开,TP SHUAI,53,5.函数的可微性与展开,当f(x)在x点存在二阶偏导时,函数f在点x的Hesse矩阵定义为,TP SHUAI,54,5.函数的可微性与展开,TP SHUAI,55,5.函数的可微性与展开,TP SHUAI,56,5.函数的可微性与展开,TP SHUAI,57,最优化理论与算法,帅天平北京邮电大学数学系Email:,Tel:62281308,Rm:主楼8142,凸分析与凸函数,TP SHUAI,58,2.凸集与凸函数,2.1 凸集与锥,TP SHUAI,59,2.凸集与凸函数,TP SHUAI,60,2.凸集与凸函数,TP
16、 SHUAI,61,2.凸集与凸函数,TP SHUAI,62,运用定义不难验证如下命题:,2.凸集与凸函数,TP SHUAI,63,2.凸集与凸函数,多面体(polyhedral set)是有限闭半空间的交.(可表为 Axb).,TP SHUAI,64,2.凸集与凸函数,TP SHUAI,65,多面集 x|Ax0也是凸锥,称为多面锥。,2.凸集与凸函数,由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合,K(S)=x|0,xS,是包含S的最小凸锥.,锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间.,约定:非空集合S生成的凸锥,是指可以表示成S中
17、有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则,coneS=K(S)0,TP SHUAI,66,2.凸集与凸函数,Df 2.5 非空凸集中的点 x 称为极点,若 x=x1+(1-)x2,(0,1),x1,x2 S,则 x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.,由上可知,任何有界凸集中任一点都可表成极点的凸组合.,TP SHUAI,67,2.凸集与凸函数,Def 2.6.设非空凸集SRn,Rn中向量d0 称为S的一个回收方向(方向),若对每一 xS,R(x.d)=x+d|0 S.S的所有方向构成的尖锥称为S的回收锥,记为0+S,方向d
18、1和d2 称为S的两个不同的方向,若对任意0,都有 d1d2;方向d称为S的极方向extreme direction,若 d=d1+(1-)d2,(0,1),d1,d2 是S的两个方向,则有 d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合,TP SHUAI,68,2.凸集与凸函数,TP SHUAI,69,2.凸集与凸函数,表示定理,Th2.4 若多面体P=xRn|Axb,r(A)=n则:,则,(3)指标集J是空集当且仅当P是有界集合,即多胞形.,TP SHUAI,70,2.凸集与凸函数,表示定理直观描述:设 X 为非空多面体.则存在有限个极点 x1,xk,k0.进一步,存在有限个极
19、方向 d1,dl,l0 当且仅当 X 无界.进而,xX 的充要条件是 x 可以表为 x1,xk 的凸组合和d1,dl的非负线性组合(凸锥组合).,推论2.1 若多面体S=x|Ax=b,x0非空,则S必有极点.,TP SHUAI,71,2.2 凸集分离定理,2.凸集与凸函数,TP SHUAI,72,2.凸集与凸函数,TP SHUAI,73,证明:令,2.凸集与凸函数,TP SHUAI,74,所以为柯西列,必有极限,且由S为闭集知。此极限点必在S中。,2.凸集与凸函数,下证明唯一性,TP SHUAI,75,2.凸集与凸函数,TP SHUAI,76,2.凸集与凸函数,TP SHUAI,77,2.凸集
20、与凸函数,证明提纲,TP SHUAI,78,由此可得,2.凸集与凸函数,TP SHUAI,79,2.凸集与凸函数,Th2.7表明,S为闭凸集,yS,则y与S可分离。若令clS表示非空集合S的闭包,则当yclS时,定理结论也真。实际上我们有下述定理,TP SHUAI,80,证明,2.凸集与凸函数,TP SHUAI,81,推论2.2:设S为Rn 中的非空集合,yS,则存在非零向量p,使对xclS,pT(x-y)0,2.凸集与凸函数,TP SHUAI,82,2.凸集与凸函数,TP SHUAI,83,2.凸集与凸函数,TP SHUAI,84,作为凸集分离定理的应用,下面介绍两个择一定理:Farkas定
21、理和Gordan定理,它们在最优化理论中是很有用的。,2.凸集与凸函数,2.3 择一定理,TP SHUAI,85,2.凸集与凸函数,TP SHUAI,86,2.凸集与凸函数,TP SHUAI,87,2.凸集与凸函数,TP SHUAI,88,2.凸集与凸函数,TP SHUAI,89,2.凸集与凸函数,TP SHUAI,90,2.凸集与凸函数,TP SHUAI,91,2.凸集与凸函数,TP SHUAI,92,2.凸集与凸函数,TP SHUAI,93,2.凸集与凸函数,2.4 凸函数,Df2.10 设SRn是非空凸集,函数f:SR,若对任意x1,x2S,和每一(0,1)都有 f(x1+(1-)x2)
22、f(x1)+(1-)f(x2)则称f是S上的凸函数.若上面的不等式对于xy严格成立,则称f是S上的严格凸函数.若-f是S上的凸函数,则称f是S上的凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数.,2.4.1 基本性质,TP SHUAI,94,2.凸集与凸函数,TP SHUAI,95,Th2.13 设 f 是一凸函数,则对任意的xRn 和d(0)Rn,f在x处沿方向d的方向导数存在。,2.凸集与凸函数,TP SHUAI,96,2.凸集与凸函数,TP SHUAI,97,2.凸集与凸函数,TP SHUAI,98,命题2.3 设f是定义在凸集S上的凸函数,则(1)所有凸函数f的集合关于凸锥
23、组合运算是封闭的,即(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)都是凸集,TP SHUAI,99,2.凸集与凸函数,设S 为Rn中的非空凸集,则 f(x)是凸的当且仅当上镜图 epif=(x,y)|xS,yR,yf(x)是凸集,对上镜图事实上我们有如下定理,TP SHUAI,100,2.凸集与凸函数,TP SHUAI,101,定理2.14 设SRn为一非
24、空凸集,f是定义在S上的凸函数,则f在S上的局部极小点是整体极小点,且极小点的集合为凸集。,2.凸集与凸函数,TP SHUAI,102,2.凸集与凸函数,TP SHUAI,103,2.凸集与凸函数,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 凸函数的判别,TP SHUAI,1
25、05,2.凸集与凸函数,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.,TP SHUAI,107,2.凸集与凸函数,TP SHUAI,108,2.凸集与凸函数,Th 2.17 设S 是 Rn a上的非空开凸集,f(x)为 S 到 R上的二次可微函数.则(1)f(x)是凸函数当且仅当S上每一点的Hessian矩阵是半正定的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 理论 算法 完整版
链接地址:https://www.31ppt.com/p-5749158.html