清华大学最优化方法

•考试时间：2014年1月14日下午2：30-4:30•考场安排：•三教2101：学号在2010210814~2013210673三教2102：学号在2013210677~2013310384•三教2301：其余同学•答疑安排：•2014年1月11、12日•上午：8:30~11:30•下午：2:30~5:30•地点：一教103•2014年1月13日•上午：8:30~11:30•下午：2:30~5:30•地点：一教102•1.携带研究生证，以备查对。•2．提前十分钟进入考场。考试开始十五分钟后，不准再进入考场，逾时以旷考论。题卷发出十五分钟后，方可交卷离场。•3．除答卷必需用的文具及教师指定的考试用具外，书包、书籍、笔记、纸张等一律按监考教师要求集中放置。•4．不允许携带具有信息传递或存储功能的工具（如BP机、手机等）进入考场。•5．答卷一般用钢笔或圆珠笔（蓝色或黑色，不得用红色），不得用铅笔（画图或外语考试选择题等指定用铅笔除外）。•6．答卷时不准互借文具（包括计算器、计算尺等）。•7．严禁以任何理由左顾右盼、交头接耳、抄袭或看别人答卷等各种形式的作弊行为。•8．答卷时，不得中途离场后再行返回。如有特殊原因需离场者，必须经监考教师准许。答卷一经考生带出考场，即行作废。•9．在规定的时间内答卷，不得拖延。交卷时间到，考生须在原座位安静地等候监考教师收卷后，方可离场。总复习•一.凸集与凸函数•1．凸集的定义、性质;)4(;},|{)3(;},|{)2(;}|{)1(212)2(1)1()2()1(212)2(1)1()2()1(211121是凸集是凸集是凸集是凸集实数，则是两个凸集，和设SSSxSxxxSSSxSxxxSSSxxSSS2.极点和极方向的定义的极点。是凸集，则称推出，必假设不同点的凸组合，即若中两个不能表示成，若是非空集合，设SxxxxxxxSxSxS)2()1()2()1()1(要求：会证明或判断一个点是否是极点.(1)(2)(1)(2)(1)(2){|0}SdSxxdSdSddSddddSddS设是闭凸集，为非零向量，如果对中的每一个，有，则称是的方向；又设和是的两个方向，若对任何正数，有，则称和是两个不同的方向，若的方向不能表示成该集合的两个不同方向的正的线性组合，则称为的极方向。要求：会证明或判断一个非零向量是否是方向或极方向.。且的方向的充要条件是是非零向量，则是为非空集合，设00}0,|{AddSddxbAxxS结论：了解表示定理2．凸集分离定理（1）会应用凸集分离定理（2）掌握Farkas定理和Gordan定理和证明方法，会应用这两个定理证明相应的题目。3．凸函数(凹函数)要求：掌握凸(凹)函数的定义、性质及判断方法，会证明或判断一个函数是否是凸(凹)函数。凸规划•凸规划：求凸函数在凸集上的极小点。min()..()0,1,,()0,1,,ijfxstgximhxjl()()(1,,)()(1,,)ijfxgximhxjl若是凸函数，是凹函数，是线性函数，则原问题为凸规划。性质：凸规划的局部极小点就是整体极小点，且极小点的集合为凸集。要求：会判断一个模型是否为凸规划LP的标准形式1、极小化型2、约束方程为等式3、所有的决策变量为非负值4、约束方程的右端项系数为非负值11min.1,,01,,njjjnijjijjzcxstaxbimxjn111min00nmnmnzcxcs.t.AxbAbxx线性规划部分•1．基本概念:•可行域(线性规划的可行域是凸集).•解的情形:无解(无可行解)、无界解(不存在有限的最优解)、最优解(最优解与最优值的区别)、局部最优解与全局最优解.•可行解、基本解、基、基变量、非基变量、基本可行解、非退化（退化）的基本可行解。•2．基本性质：•线性规划存在有限最优解的充要条件是所有cd(j)为非负数，其中d(j)为可行域的极方向。•若线性规划问题存在有限最优解，则目标函数的最优值可在某个极点达到。•基本可行解与可行域极点之间的关系---等价。•基本可行解的存在问题：有可行解，一定有基本可行解。单纯形法min..0fxcxstAxbx11.0.BBb存在初始基，使得如何判断该问题是否有最优解？如何判断一个基是否为最优基？如何判断该问题是否有无穷多最优解？用单纯形表求解问题：xBxN右端xBImB-1NB-1b0cBB-1N-cNcBB-1b110BNcBNc若极小化问题，则现行基本可行解为最优解。110,0BNbBbxBbxx假设有一基本可行解主元消去法120.BjjcBPc若存在，用求改进的基本可行解2．寻找初始基本可行解min..0fxcxstAxbx两阶段法大M法min..111,0TaTaaexstAxxbexx1min..11100TaTamcxMexstAxxbeMx•minmax•变≥0≤约•量≤0≥束•无限制=方•程•约≥≥0•束≤≤0变•方=无限制量•程对偶原理•会写各种形式（对称、非对称、一般形式）的对偶问题；•掌握弱对偶定理和强对偶定理及其相关推论；•会用互补松弛定理求原问题或对偶问题的解；小结原问题(min)对应关系对偶问题(max)有最优解有最优解无界解不可行不可行无界解对偶单纯形法•掌握对偶单纯形方法（对偶可行的基本解，如何求初始对偶可行的基本解）。•与原单纯形法的区别：•原单纯形法保持原问题的可行性，对偶单纯形法保持所有检验数wPj-cj≤0，即保持对偶问题的可行性。•特点：先选择出基变量，再选择进基变量。•5．灵敏度分析•改变非基变量和基变量价格系数后，原问题最优解和最优值的改变，会求最优解不变时价格系数的变化范围；•右端向量改变对最优解及最优值的影响，会求最优基不变时，右端向量的变化范围；•会判断增加新的约束后，原问题最优解是否发生变化•6.目标规划•会建立目标规划模型最优性条件•无约束问题的极值条件：.0)()()(1xfxxxf是局部极小点，则若处可微，在点设函数一阶必要条件：定理是半正定的。矩阵，且极小点，则是局部处二阶可微，若在设二阶必要条件：定理)(0)()(22xfHessianxfxxxf是严格局部极小点。正定，则矩阵且处二次可微，若梯度在点：设函数定理xxfHessianxfxxf)(,0)()(32223'()()0,()()fxxfxHessianfxxxxfxx定理：设函数在点的邻域内二次可微，若梯度且矩阵在该邻域内半正定，则是局部极小点。特别地，对于邻域内的任意点，若是正定矩阵，则是一个严格的局部极小点..*)(21)(1bAxAcxbAxxxfTT，有唯一极小点对称正定数推论：对于正定二次函.0)(,)(4xfxExExfnn件是为整体极小点的充要条则上的可微凸函数，是定义在：设定理约束极值问题的最优性条件min()00(0,),()()()nnxEfxxEdfxdfxdfxx对，设是任给一点，，若存在，使得对任意的有，则称为在点处的下降方向(descentdirection)。0)(0dxfdFT处的下降方向集。称为点x定义:,,0,(0,)nSExclSdxdSdSx设集合为非零向量，若存在数使得对任意，都有则称为集合在的可行方向(feasibledirection)。SdxclSxddD有),,0(,0,,0处的可行方向锥。xmin()2(..()0,1,,()0,1,,,{|()0}.,()()(1,,){()()|,1,,},(1,,)(ijiiijijijfxKKTstgximhxjlxIigxfgiIxgiIxhjlxgxhxiIjlxwiIvjlf定理必要条件）考虑问题设为可行点在处可微，在连续，在连续可微，向量集，线性无关，若是局部最优解，则存在数和，使得1)()()0.0().liijjiIjixwgxvhxwiI1min()2'(..()0,1,,()0,1,,,{|()0}.,(1,,){()()|,1,,},(1,,)()()ijiijijijmiiifxKKTstgximhxjlxIigxfgxhjlxgxhxiIjlxwiIvjlfxwgx定理必要条件）考虑问题设为可行点在处可微，在连续可微，向量集，线性无关，若是局部最优解，则存在数和，使得1()0()0,1,2,,01,2,,.ljjjiiivhxwgximwim定义广义的Lagrange函数:.))(,),(()())(,),(()(),,,(),,,()()()()()()(),,(11212111TlTmTlTmTTljjjmiiixhxhxhxgxgxgvvvv其中乘子向量min()2'(..()0,1,,()0,1,,,{|()0}.,(1,,){()()|,1,,}0,,(,,)0ijiijijxfxKKTstgximhxjlxIigxfgxhjlxgxhxiIjlxwvLxwv定理必要条件）考虑问题设为可行点在处可微，在连续可微，向量集，线性无关，若是局部最优解，则存在乘子向量使得为整体极小点。条件成立，则处且在连续，在点连续，在点可微，在点和。，为可行域，是线性函数，是凹函数，是凸函数，中，设问题一阶充分条件．定理xKKTxxIigxljhxIigfxgiISxSljhmigfljxhmixgtsxfijiijiji)(),,2,1()(}0)(|{),,2,1(),,2,1(,,2,10)(,,2,10)(..)(min)(3点。是是整体最优解是凸规划，则：设推论KKTxSxNP)(12()(1,,)(1,,){(),,(),1,,},(,,)()(,,)()0,0()0,0()0,ijijxTiiTiiTjxNPfgimhjlxgxiIhxjlwvxwvLMLxwvGgxdiIwGdgxdiIwhxdj定理（二阶必要条件）：设是的局部最优解，，和二次连续可微，且在处，为线性无关组，则存在，使为的解且矩阵在子空间上是半正定的，其中且且.1,2,,l2(1,,)(1,,),(,,)()(,,)()0,00()0,0.()0,1,2,,ijxTiiTiiTjfgimhjlxwvxwvLMLxwvGxgxdiIwGdgxdiIwhxdjl定理（二阶充分条件）：设，和是二次连续可微函数，为可行解，若存在，使为的解且矩阵在子空间上是正定的，则是严格局部极小点。且其中且对偶问题（要求：会写对偶问题）Lagrange对偶问题Dxljxhmixgtsxfji,,1,0)(,,1,0)(..)(min(1)定义(1)的对偶问题:0..),(maxwtsvw(2)Dxxhvxgwxfvwljjjmiii11)()()(inf),(其中对偶函数。称为时，令若上式不存在有限下界Lagrangevwvw),(.),(推论1:.0|),(sup,0)(,0)(|)(infwvwDxxhxgxf，必有对于原问题和对偶问题推论2:题的最优解。分别是原问题和对偶问和，则为原问题的可行解，，其