最优化方法及其应用

最优化（一）一最优化问题总论二一维搜索法三常用无约束最优化方法四常用约束最优化方法五程序设计及其他优化方法一最优化问题总论无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题．最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科．例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标．这是最简单的最优化问题，实际优化问题一般都比较复杂．概括地说，凡是追求最优目标的数学问题都属于最优化问题作为最优化问题，一般要有三个要素：第一是目标；第二是方案；第三是限制条件．而且目标应是方案的“函数”．如果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题本书只讨论静态最优化问题．一最优化问题总论最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题．例1.1对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？一最优化问题总论解设剪去的正方形边长为x，由题意易知，与此相应的水槽容积为令得两个驻点：2()2(2)(2)(2)fxaxxaxxxaxf2)2()((2)(6)0axaxaxax61,21一最优化问题总论第一个驻点不合实际，这是因为剪去4个边长为的正方形相当于将铁板全部剪去．现在来判断第二个驻点是否为极大点．因为所以是极大点结论是：每个角剪去边长为的正方形可使所制成的水槽容积最大．()248fxxa()40afab6ax一最优化问题总论例1.2求侧面积为常数体积最大的长方体体积．解设长方体的长、宽、高分别为，，，体积为，则依题意知体积为限制条件为由拉格朗日乘数法，考虑函数xyzv(,,)vfxyzxyz2(,,)2()60xyzyzxzxya)6222(),,(2axyzxyzxyzzyxF§1.1最优化问题数学模型令由题意可知应是正数，由此，将上面三个等式分别乘以，并利用已知条件得到§1.1最优化问题数学模型2()02()02()0xyzFyzyzFxzzxFxyxy，，，2222(3)02(3)02(3)0xyzayzxyzazxxyzaxy，，．zyx,,zyx,,比较以上三式可得xyazxayza222333从而x=y=z=a，右侧面积固定的长方体的最大体积客观存在，因此侧面积固定的长方体中以正方体体积最大．一最优化问题总论例1.3某单位拟建一排四间的停车房，平面位置如图1.1所示．由于资金及材料的限制，围墙和隔墙的总长度不能超过40m，为使车房面积最大，应如何选择长、宽尺寸？x1x2一最优化问题总论解设四间车房长为，宽为．由题意可知面积为且变量，，应满足即求，1x2x2121),(xxxxf1x2x405221xx1200xx，2121),(maxxxxxf1212254000xxxx，，．一最优化问题总论最优化问题的数学模型包含有三个要求：即变量（又称设计变量）、目标函数、约束条件．一、变量二、目标函数三、约束条件四、带约束条件的优化问题数学模型表示形式一最优化问题总论综上所述，全书所要讨论的问题是如下的（静态）最优化问题，其表示形式有三种：第一种最优化问题表示形式为第二种最优化问题表示形式为1212[]1212min()()012..()012()Tnnxxxinjnfxxxgxxxilsthxxxjmmn，，，，，，，，，，，，，，，，，，，，，，．min()()0..()0XfGXstHX，，，X一最优化问题总论第三种最优化问题表示形式为（1.1）其中min()()012..()012()XijfXgXilsthXjmmn，，，，，，，，，，．11()[()()]()[()()]TTlmGXgXgXHXhXhX，，，，，一最优化问题总论上述三种表示形式中，称为集约束．在所讨论的最优化问题中，集约束是无关紧要的．这是因为一般，不然的话，通常也可用不等式约束表达出来．因此今后一般不再考虑集约束．满足所有约束的点称为容许点或可行点．容许点的集合称为容许集或可行域．可用表示．{|()012()012()}ijDXgXilhXjmmn，，，，；，，，，一最优化问题总论一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点，使得目标函数在该点取得极小值，即这样的称为问题（1.1）的最优点，也称极小点，而相应的目标函数值称为最优值；合起来称为最优解，但习惯上把本身称为最优解．最优点的各分量和最优值必须是有限数．***()min()()0..()0fXfXGXstHX，，．*()fX**(,())XfX*X一最优化问题总论一、二维最优化问题的图解法讨论二维最优化问题为121212min()()012..()012ijfxxgxxilsthxxjm，，，，，，，，，，，，，．一最优化问题总论（一）约束集合当约束函数为线性时，等式约束在坐标平面上为一条直线，不等式约束在坐标平面上为一半平面；当约束函数为非线性时，等式约束条件在坐标平面上为一条曲线（如图），不等式约束把坐标平面分成两部分当中的一部分（如图）．一最优化问题总论综上所述，当把约束条件中的每一个等式所确定的曲线，以及每一个不等式所确定的部分在坐标平面上画出之后，它们相交的公共部分即为约束集合D．一最优化问题总论例1.4在坐标平面上画出约束集合解:满足的区域为以原点为圆心，半径为1的圆；满足的区域为第一象限的扇形（如图所示）．22121212{()|100}TDxxxxxx，，，一最优化问题总论（二）等高线我们知道在三维空间中表示一张曲面．其中为常数）在三维空间中表示平行于平面的一个平面，这个平面上任何一点的高度都等于常数（如图）．在三维空间中曲面与平面有一条交线．交线在平面上的投影曲线是，可见曲线上的点到平面的高度都等于常数C，也即曲线上的的函数值都具有相同的值．12()tfxx，ct21,xxc12()tfxx，LL12[]Txx，cct一最优化问题总论当常数取不同的值时，重复上面的讨论，在平面上得到一族曲线——等高线.等高线的形状完全由曲面的形状所决定；反之，由等高线的形状也可以推测出曲面的形状．一最优化问题总论例1.5在坐标平面上画出目标函数的等高线．解:因为当取时，曲线表示是以原点为圆心，半径为的圆．因此等高线是一族以原点为圆心的同心圆（如图所示）21xx，21xx，222121)(xxxxf，一最优化问题总论例1.6用图解法求解二维最优化问题解:如图，目标函数的等高线是以为圆心的同心圆，并且这族同心圆的外圈比内圈的目标函数值大．因此，该问题为在约束集中找一点,使其落在半径最小的那个同心圆上。问题的最优解为：2212221212min[(2)(2)]1..00xxxxstxx，，，．[22]T，*12[][00]TTXxx，，一最优化问题总论二、最优化问题的迭代解法（一）迭代方法在经典极值问题中，解析法虽然具有概念简明,计算精确等优点，但因只能适用于简单或特殊问题的寻优,对于复杂的工程实际问题通常无能为力，所以极少使用。最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的步长，从而到达一个新点，用式子表示即为(1.2)一最优化问题总论式中,——前一次已取得的迭代点，在开始计算时为迭代初始点；——新的迭代点；——第k次迭代计算的搜索方向；——第k次迭代计算的步长因子．kX1kXkPkt0X0X一最优化问题总论1012kkkkXXtPk，，，，按照式（1.2）进行一系列迭代计算所根据的思想是所谓的“爬山法”，就是将寻求函数极小点（无约束或约束极小点）的过程比喻为向“山”的顶峰攀登的过程，始终保持向“高”的方向前进，直至达到“山顶”．当然“山顶”可以理解为目标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法．这两种算法都有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息．如果是下降算法，则序列迭代点的目标函数值必须满足下列关系011()()()()kkfXfXfXfX一最优化问题总论012kXDk，，，，如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即下图为迭代过程一最优化问题总论（二）收敛速度与计算终止准则（1）收敛速度作为一个算法A，能够收敛于问题的最优解当然是必要的，但光能收敛还不够，还必须能以较快的速度收敛，这才是好的算法．定义1.1设由算法A产生的迭代点列在某种“||·||”的意义下收敛于点，即,若存在实数及一个与迭代次数无关的常数使得则算法A产生的迭代点列叫做具有阶收敛速度,或算法A叫做是阶收敛的，特别地:*X*lim||||0kkXX0k*1*||||lim||||kkkXXqXX{}kX0q一最优化问题总论①当，迭代点列称为具有线性收敛速度或算法A称为线性收敛的．②当，或时，迭代点列叫做具有超线性收敛速度或称算法A是超线性收敛．③当时，迭代点列叫做具有二阶收敛速度或算法A是二阶收敛的．一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法．0,1q}{kX0,21q0,1q}{kX2}{kX一最优化问题总论(2)计算终止准则用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问题．从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代．但是这在实际上是办不到的．因为对于一个待求的优化问题，其理论极小点在哪里并不知道．所知道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代．对于无约束优化问题通常采用的迭代终止准则有以下几种：一最优化问题总论①点距准则相邻两迭代点之间的距离已达到充分小，即式中是一个充分小正数，代表计算精度．②函数下降量准则相邻两迭代点的函数值下降量已达到充分小．当时，可用函数绝对下降量准则当时，可用函数相对下降量准则③梯度准则目标函数在迭代点的梯度已达到充分小，即这一准则对于定义域上的凸函数是完全正确的．若是非凸函数，有可能导致误把驻点作为最优点。对于约束优化问题，不同的优化方法有各自的终止准则．||||1kkXX1|)(|1kXf|)()(|1kkXfXf1|)(|1kXf|)()()(|11kkkXfXfXf)(1kXf一最优化问题总论综上所述，优化算法的基本迭代过程如下：①选定初始点，置．②按照某种规则确定搜索方向．③按某种规则确定使得④计算⑤判定是否满足终止准则．若满足，则打印和,停机；否则置,转②．0X0kkPkt)()(kkkkXfPtXfkkkkPtXX11kX1kX)(1kXf1kk一最优化问题总论NYX是否满足终止准则输出X，f(X)开始结束选定X0确定P确定t，使得f(X0+tP)f(X0)X=X0+tPX0=X上述算法框图如右图一最优化问题总论就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典算法、构造型算法、改进型算法、基于系统动态演化的算法和混合型算法等．（1）经典算法．包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法，其算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用．一最优化问题总论（2）构造型算法．用构造的方法快速建立问题的解