最优化绪论

最优化理论与工程应用厦门大学信息科学与技术学院蔡聪波2016.09Email:[e-mail]最优化理论与工程应用(OptimizationTheoryandItsApplicationsinEngineeringProblems)1.概述2.经典最优化方法3.线性规划4.非光滑最优化方法5.光滑最优化方法6.最优化方法的工程应用7.相关讨论课及最新研究进展与应用选讲第一章概述§1.1各工程领域中的最优化问题概述§1.2最优化问题的一般形式§1.3优化问题的最优性条件第一章概述1.1各工程领域中的最优化问题概述最优化问题总论无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题．最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科．例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标．这是最简单的最优化问题，实际优化问题一般都比较复杂．概括地说，凡是追求最优目标的数学问题都属于最优化问题．作为最优化问题，一般要有三个要素：第一是目标；第二是方案；第三是限制条件．而且目标应是方案的“函数”．如果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题．第一章概述1.1各工程领域中的最优化问题概述1）最优化方法概念最优化方法（Optimization）,它是研究在给定约束之下（如果有）如何寻求某些因素的值，以使某一或某些指标达到最优的问题的一些学科的总称。由于运筹学（OperationsResearch）中出现的问题大多即是最优化所研究的问题，因此运筹学的许多分支，如数学规划、组合最优化、排队论，以及决策论等也是最优化的组成部分。此外，最优化还包括如工程最优设计、最优控制(控制论与运筹学的交叉分支)等。狭义地说，最优化即指数学规划(MathematicalProgramming)。许多生产计划与管理问题都可以归纳为最优化问题,最优化模型是数学建模中应用最广泛的模型之一,其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等。第一章概述1.1各工程领域中的最优化问题概述2）最优化方法意义可以说，有需要决策（选择）的地方，就有最优化存在！应用方面信息科学：（数据挖掘,最大熵，图像处理，通信网设计，通信元件可靠性设计）交通：（最大效益，时刻表，司机排班表，交通灯优化设计）经济金融：（最小风险，最小成本，最大利润）生命科学：（DNA测序与比对,蛋白质折叠）力学：（最小重量，最大载重，结构最优，功率最低）材料科学：（最小能量，最小成本）军事：（核武器最佳拥有量，兵棋推演）地学：（遥感测距，地质勘探）等等。第一章概述1.1各工程领域中的最优化问题概述2）最优化方法意义由于宇宙组成是最完美也是最聪明造物主之产物，宇宙间万物都遵循某种最大或最小准则———欧拉Für,dadasGewebedesUniversumsamvollkommenstenunddieArbeiteinesklügstenistSchöpfers,nichtsanfindetimUniversumstatt,indemirgendeineRichtliniedesMaximumsoderdesMinimumsnichterscheintLeonhardEuler(1707-1783)第一章概述1.1各工程领域中的最优化问题概述2）最优化方法应用的具体例子例1.车站选址问题一直线铁路经过钢厂A，矿区B位于距铁路最近处C为20km，AC相距150km。计划在铁路上设一站D，在BD之间筑一条直线公路，若矿石运费铁路为3元/km·t，公路为5元/km·t。问题：D站选在何处最好。yB（150，20）ox150xADC●●●第一章概述1.1各工程领域中的最优化问题概述2）最优化方法应用的具体例子例2.罐头盒问题设计圆柱形罐头盒，使用料最省。假设：1.不考虑折边及铁皮厚度；2.底半径r，高h；3.容积为常数V。rh（ConstrainedProgramming）第一章概述1.1各工程领域中的最优化问题概述2）最优化方法应用的具体例子例3..生产计划问题某工厂有m种资源某一时段的数量分别为：可用来生产n种产品每生产一单位消耗为利润为。如何安排生产可获最大利润？（LinearProgramming）,B,B,B21m,,,21mbbb,A,A,A21njAiB,ijajc第一章概述1.1各工程领域中的最优化问题概述2）最优化方法应用的具体例子例4.数据拟合问题设某系统中变量x,y满足：y=f(x)已获得系统数据：(xi,yi),i=1,2,···,m确定f(x)的参数，例如：（LSM）32103102101sin)()()(2432axaaaxfexaaxfxaxaaxfxaxaannmixxxx21yx0············iiyx,第一章概述1.1各工程领域中的最优化问题概述2）最优化方法应用的具体例子例5.旅行商问题（TSP）一商人欲到n个城市推销，城市i到城市j相距dij,求走遍所有城市的最短路径。（CombinatorialOptimization）○○○FEDCBA○○○第一章概述1.1各工程领域中的最优化问题概述3）最优化方法学科基础最优化问题的发展规律：优化问题越来越多，非线性程度越来越高，越来越难。此外还有计算规模的问题，如NP-hard问题，特别是组合优化问题，由于计算复杂度的原因，往往只能退而寻次优。准备知识：微积分，线性代数，概率统计，图论，几何，集合论，随机过程等。参考书：1.袁亚湘、孙文瑜著，《最优化理论与方法》，科学出版社，20052.《现代优化计算方法》，邢文训、谢金星编著，清华大学出版社，20033.《ConvexOptimization》，StephenBoydandLievenVandenberghe，CambridgeUniversityPress4.《NumericalOptimization》JorgeNocedalandStephenWright,2ndEdition,Springer5.《NonlinearProgramming》byDimitriP.Bertsekas，AthenaScientific6.《MinimizationMethodsforNondifferentiableFunctions》，N.Z.Shor,K.C.Kiwiel,andA.Ruszcy`nski,Springer，Verlag,Berlin,1985.第一章概述1.2最优化问题的一般形式1）无约束优化（UnconstrainedOptimization）Solveminf(x),(1.2.1)wherexinXandXisametricspace.2）带约束优化（ConstrainedOptimization）Solve:minf(x),(1.2.2)subjecttohi(x)=0,i=1,…,l;(1.2.3)gj(x)≥0,j=1,…,m(1.2.4)wherexinXandXisametricspace.Note:f(x)--objectivefunction,lossfunction（损失函数）,costfunction,indirectutilityfunction（间接效用函数）,utilityfunction,fitnessfunction,energyfunction,orenergyfunctional.Particularly,letX=Rninthiscourseunlesswepointitoutelsewhere..第一章概述1.3优化问题的最优性条件1）无约束优化的最优性条件定义1（全局极小值点）对于任意的,都有f(x*)≤f(x),则称x*为f的全局极小值点。若该不等式严格成立，且x≠x*,则称x*为为f的严格全局极小值点。定义2（局部极小值点）对于任意的,都有f(x*)≤f(x),其中为一常数，则称x为f的局部极小值点。若该不等式严格成立，且x≠x*,则称x*为f的严格局部极小值点。由以上两定义可知，全局极小值点就是局部极小值点。反之不然。一般来说，求全局极小值点都不容易。在实际应用中，一般只求局部极小值点就满足要求了。nRx}|||||{),(*n*xxRxxNx0第一章概述1.3优化问题的最优性条件1）无约束优化的最优性条件第一章概述1.3优化问题的最优性条件1）无约束优化的最优性条件定理一（一阶必要条件）设f(x)在开集D上一阶连续可微，若是（1.2.1）的一个局部极小点，则必有。定理二（二阶必要条件）设f(x)在开集D上二阶连续可微，若是（1.2.1）的一个局部极小点，则必有且是半正定矩阵。其中称为Hessian矩阵。证明：0≤f(x)-f(x*)=(x-x*)T▽f(x*)+(x-x*)T▽2f(x*)(x-x*)+o(||x-x*||2).D*x0)(*xfD*x0)(*xf)(*2xf22122212121212nnnnnxxxxxxxxxxxxxxxffffffffff第一章概述1.3优化问题的最优性条件1）无约束优化的最优性条件定理三（二阶充分条件）设f(x)在开集D上二阶连续可微，若是满足条件和是正定矩阵。那么x*是（1.2.1）的一个局部极小点。定理四（凸充要条件）设凸函数f(x)在Rn一阶连续可微，则x*是（1.2.1）的一个全局极小点的充要条件是。D*x0)(*xf)(*2xf0)(*xf第一章概述1.3优化问题的最优性条件1）无约束优化的最优性条件例子：（验证无约束问题的最优性条件）解：显然为局部极小点，且为全局极小点。1）一阶必要条件2）二阶必要条件易知f(x)二阶连续可微，▽2f(x*)=(20;02),设任意d=(d1,d2)∈R2,则dT(20;02)d=2(d1d1+d2d2)≥0,故半正定！3）二阶充分条件因为▽2f(x*)是半正定的，故不能用二阶充分性条件。4）凸充要条件显然“充分”和“必要”两个方向都满足！221222121),()2()3(),(minRxxxxxxf，)2,3(),(*2*1*xxx▽f(x*)=2(x1*-3,x2*-2)=0第一章概述1.3优化问题的最优性条件2）带约束优化的最优性条件a)等式约束情况考虑minf(x)s.t.h(x)=0回顾高等数学中的条件极值,如求以下问题z=f(x,y)等式约束条件极值：minz=f(x,y)s.t.h(x,y)=0解：引入Lagrange乘子λ，构建Lagrange函数L(x,y;λ)=f(x,y)+λh(x,y)。若(x*,y*)是条件极值，则存在λ*，使fx(x*,y*)+λ*hx(x*,y*)=0fy(x*,y*)+λ*hy(x*,y*)=0h(x*,y*)=0若只有等式约束的问题(1.2.2-1.2.3)推广到n维情况，则可有第一章概述1.3优化问题的最优性条件2）带约束优化的最优性条件a)等式约束情况若只有等式约束的问题(1.2.2-1.2.3)推广到n维情况，则可有ljxhxhxfjljjj,...,10)(0)()(*1***其中第一章概述1.3优化问题的最优性条件2）带约束优化的最优性条件b)不等式约束情况定义3（有效约束集）对于只有不等式约束的优化问题(1.2.2)、(1.2.4)，若x*为其局部极小点定义，则I(x*)={i|gi(x*)=0,i∈I}，称该下标集合为有效约束集。几何解释：x*g1(x)=0g2(x)=0其中g2(x*)=0,那么g2为x*上发挥作用的约束，g1为x*点的无效约束。第一章概述1.3优化问题的最优性条件2）带约束优化的最优性条件b)不等式约束情况例子0),(0),(042),(05),(..)2()3(),(m