北工大第一次最优化方法13

最优化理论与算法（54课时）---绪论李改弟应用数理学院[e-mail]最优化研究什么？•有选择的地方就有优化：田忌赛马•讨论在众多的方案中什么样的方案最优以及怎样找出最优方案城建规划：如何安排工厂、机关、学校、商店、医院、住户和其他单位的布局，方能方便群众，利于城市的房展食谱问题：保证营养要求条件下最经济课本与教辅材料：1.陈宝林，最优化理论与算法(第二版)，清华大学出版社2.刘红英，数学规划基础，北京航空航天大学出版社，2012优化的数学描述与例子•目标：系统性能的一种“量的度量”(利润、时间、势能)－－任何数量或某些量的组合－－数•变量：目标所依赖的系统的“某些可控的特征”•约束条件：经常变量以某种方式受限制(分子中电子密度的量、贷款利率的量，不能是负的)－－---优化问题的一般模型－－数学规划问题优化建模(modeling)：识别出给定问题的目标、变量和约束的过程。•建立恰当模型：第一步、最重要的一步(太简单－不能给实际问题提供有用的信息；太复杂－不易求解)•选择特定算法：很重要--决定求解速度及质量(无通用优化算法，有求解特定类型优化问题的算法)优化实例１：运输问题(transportationproblem)背景：化学制品公司考虑某种产品的产销问题.数据：问题：确定从每个工厂运送到每个销地的产品数量，使其满足需求，同时极小化费用变量：的产品数量目标函数：产量约束：销量约束：非负约束：问题中目标和约束函数都是线性函数,称此类型的问题为线性规划问题.优化实例2：选址问题(facilitylocationproblem)已知：),,2,1(),,(njqbajnjjj对某种货物的需要量是个市场的位置为个市场，第有).,,2,1(micimi个货栈的容量为个货栈，第计划建立目标：确定货栈的位置，使各货栈到各市场的运输量与路程乘积之和最小。变量：),2,1;,2,1().,2,1)(,(njmiWjimiyxiijii个市场的货物量为个货栈到第第个货栈位置为第minjjijiijbyaxW1122)()(minnjmiWij2,1;,2,1,0njiijmicWts1,2,1,..货栈的容量mijijnjqW1,2,1,市场的需要量目标函数和约束函数至少有一个是非线性函数，此为非线性规划！1.2最优化问题的分类与特征•某些或全部变量取整数值才有意义--整数规划(IP).(上述运输问题中，工厂生产拖拉机而非化学产品).•分为整数线性规划和整数非线性规划；整数规划和混合整数规划；一般整数规划和0-1整数规划•简单松弛策略.忽略整数要求，当成实变量来求解问题，然后将所有分量舍入到最近的整数--可给出问题的界.Lagrange松弛策略.•整数规划属NP难问题.常用算法：分支定界法、或其他启发式算法(求解一系列连续优化问题)连续与离散约束与无约束无约束优化肯定是非线性的、约束优化又分线性规划和非线性规划局部与全局单目标与多目标随机与确定有的问题进行优化建模时，模型与一些不能提前确定的参数有关(运输问题中，零售市场的需求在实际中不能够精确确定.许多经济和金融规划模型也具有该特征,哪里经常与未来的利息率和经济的未来趋向有关).多目标规划最重要的是Perato解/有效解的概念；一般可用标量化方法求Perato解优化问题的简单分类与求解难度问题的求解难度依次增加！1.3优化算法和优化软件•迭代法•从最优解的某个初始猜测出发，生成一个提高的估计序列，直到达到一个解.•大部分利用目标函数和约束，可能还有这些函数的一阶和二阶导数.•通常收敛到(无约束问题)驻点或者(约束问题)KKT点(极大点、极小点或鞍点).如果问题是凸规划，则可确保算法收敛到全局极小点.◎优化算法•AMPL:AModelingLanguageforMathema-ticalProgramming•Lindo/Lingo软件(\verb•Matlab优化工具箱(见姜启源等编的《数学实验》,高教出版社)•Cplex•其它(Mathematica,Minos,Excel等的优化功能).◎优化软件课程主题介绍线性与非线性规划的－－基本理论、实用算法和部分应用具体的主题包括：•线性规划基本性质、单纯形法、对偶理论•非线性规划最优性条件、凸性、Lagrange对偶无约束优化的算法：线搜索法和信赖域法、直接法约束优化的算法：可行方向法、罚函数法先修课程：线性代数，高等数学，最好会某种高级语言Chap1预备知识.,...,1,0)(;,...,1,0)(s.t.)(minmmixcmixcxfeieiRxn(p)一、最优化问题的一般形式：决策变量，目标函数，约束函数（等式，不等式）。二、可行点与可行域三、（严格）局部极小点与（严格）全局极小点称满足约束条件的点为可行点称可行点全体组成的集合为可行域,记为D若存在，使得均有Dx*,Dx),()(*xfxf则称是在可行域上的全局极小点。*x)(xf则称是在可行域上的局部极小点。*x)(xf),()(),(},|||||{),(0******xfxfxNDxxxxxNxDx成立使得对的邻域的和若存在四、向量范数、矩阵范数1、向量范数定义三条件：2、常见向量范数：p||||||||||||||||21范数的等价性：||||||||||||,||||||||2121xcxxcRxccRnn成立使得对每个和存在正数上任意两个范数，如果是和设中任何两种范数均等价在nR||||||||||||||||||||||||||||||||||||21xnxxxnxxxnxxpp例如3.诱导矩阵范数是某一向量范数。其中||||,||||||||||||max0xAxAx矩阵范数性质(4)||||||||||||)4(||||||||||||)3(||||||||||)2(||||||||||||)1(DAADBABAAAxAAx常用的矩阵范数njijiAAmiijjaAAaAT1211||max||||,||||,||max||||4、向量序列的极限极限、聚点、Cauchy序列定理：的聚点为极限点。序列，则为设}{}{)()(jnjxCauchyRx.则称序列收敛到,||||时就有使得当,存在正整数0对每个任给的如果,中一个向量序列，是}{极限：设)()(xxxKkKRxRxknnk序列。称为则有时，就使得当总存在正整数任意给定的果对中的一个向量序列，如是设序列：CauchyxxxKlmKRxCauchyklmnk}{,||,,,0}{)()()()(的聚点。是则称使得子序列果存在一个中的一个向量序列，如是聚点：设}{ˆ,ˆlim},{}{)()()()(kkkknkxxxxxRxjjj开集、闭集、紧集为紧集。为有界闭集，则称S如果为开集。则成,}||ˆ|||{),ˆ(邻域的ˆ使得,0，ˆ如果对每一点为闭集。S则称,S的极限均属于中每个收敛序列中的一个集合，如果为S设SSSxxxxNxSxSRn五、线性空间、欧式空间六、梯度、Hesse阵例求下列函数的梯度与Hesse阵.)()2(;)()1(AxxxfxaxfTT在线性空间中，定义内积和2范数为度量，这样的空间为欧式空间。七.凸集与凸函数1.凸集（1）凸组合：已知，nRX任取k个点，Xxi如果存在常数0ia，),,2,1(ki,11kiia使得xxakiii1，则称x为ix),,2,1(ki的凸组合。（2）凸集：设集合nRX，如果X中任意两点的凸组合仍然属于X，则称X为凸集。(3)凸集的顶点：不能表示成另外两个点的严格凸组合。（4）凸集的方向、极方向的方向。是凸集则称有如果对每个是闭凸集，设DdDdxDxRdDn,0,,.0凸锥是凸集。验证超平面}|{.1xpxHT是凸集。验证半空间}|{.2xpxHT的方向和极方向。求集合|}||),{(.31221xxxxS定理(表示定理).,,2,1,0;,2,1,0;1,的充要条件是：)3(.,,则存在有限个极方向无界，若.有界要条件是极方向集合为空集的充)2(.,,限个极点极点集非空，且存在有)1(为非空多面集，则有：}0,|{设111)()()()2()1()()2()1(ljkjdxxSxdddSSxxxxbAxxSjjkjjkjljjjjjlk2.凸集分离定理。和分离集合则称超平面都有对于每个都有如果对每个超平面为中两个非空集合是和设212121,,,,.}|{,SSSHxpSxxpSxxpxHRSTTTn定理1使得则存在唯一的点中闭凸集为设,,,SSxSyRn||||inf||||xyxySx由下确界定义知令,0||||infrxySx证明：.||||,)()(rxySxkk使得｝｛SxCauchyxk故有极限序列为由平行四边形定律得,}{)(唯一性由反正法得到.定理2设是非空闭凸集，若，则存在非零SSy向量使得对每个点,0及数p成立,SxxpypTT证明:)(,xypxypT取定理3成立。有,使得对每一点,则存在非零向量,,中的一个非空凸集是设xpypclSxpSyRSTTn)()(xxxypxypTT)()(xxxyT22||)1((||||||xxyxy222||||)()(2||||xxxxxyxyT证明:.,},{,)()()(yyclSyyclSykkk.,,)()()()(xpypclSxpTkkTkk有使得对单位向量定理4（凸集分离定理）}.|sup{}|inf{使得,量则存在非零向,中两个非空凸集是和设212121SxxpSxxppSSRSSTTn证明：},,,|{令2)2(1)1()1()2(SxSxxxzzS.0是非空凸集，且SS.0有,使得对,非零向量zpSzpT3.凸集分离定理的应用Farkas定理无解。的充要条件是有解且则维向量为矩阵为设0,00,,AycyAxcAxncnmTT必要性反正法，充分性凸集分离定理2.凸函数设RRXfn:，任取Xxx21,，如果1,0,2121iiaaa，有)()())((22112211xfaxfaxaxaf，则称f为X上的（严格）凸函数。例子：2)(xxf凹函数？水平集：fXxxfxD,,)(|{是凸函数}。性质：凸函数的水平集一定是凸集。Rxxxf|,|)(3.凸函数的性质定理5.凸函数的局部极小点就是全局极小点。证明:)()(),(,0)(xfxfxNxxfx，有使得的局部极小点，则是凸函数设的凸性。)(利用,的全局极小点)(也是反证法证xfxfx4.凸函数的判断条件定理6.可微，)(xf则它是凸集X上的凸函数的充要条件是有,,21Xxx)()()()(12112xxxfxfxfT.证明：)()1()())1(()(1212xfxfxxfxf的凸性，有由))()(()())1((12112xfxfxfxxf即得必要性令,0定理7.设)(xf在开凸集X上有二阶连续偏导数，则)(xf是凸函数的充要条件是Xx，有)(2xf半正定。例：正定二次函数cxbAxxxfTT21)(，其中A是正定矩阵。例：3123222121622)(xxxxxxxxf证明：.],[,0,,XxxXXxx时，有使得是开集，必存在由于xxfxf