《最优化方法及其应用.doc》由会员分享，可在线阅读，更多相关《最优化方法及其应用.doc（160页珍藏版）》请在金锄头文库上搜索。
1、第一章 最优化问题总论无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标这是最简单的最优化问题，实际优化问题一般都比较复杂概括地说，凡是追求最优目标的数学问题都属于最优化问题作为最优化问题，一般要有三个要素：第一是目标；第二是方案；第三是限制条件而且目标应是方案的“函数”如果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题1.1
2、最优化问题数学模型最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题例1.1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解 设剪去的正方形边长为x，由题意易知，与此相应的水槽容积为令，得两个驻点：第一个驻点不合实际，这是因为剪去4个边长为的正方形相当于将铁板全部剪去现在来判断第二个驻点是否为极大点 ， ， 是极大点因此，每个角剪去边长为的正方形可使所制成的水槽容积最大例1.2 求侧面积为常数，体积最大的长方体体积解 设长方体的长、宽、高分别为体积为，则依题意知体积为，条件为由拉格朗日乘数法，考虑
3、函数， 由题意可知应是正数，由此，将上面三个等式分别乘以并利用条件，得到比较以上三式可得，从而又侧面积固定的长方体的最大体积客观存在，因此侧面积固定的长方体中以正方体体积最大，其最大值为例1.3 某单位拟建一排四间的停车房，平面位置如图1.1所示由于资金及材料的限制，围墙和隔墙的总长度不能超过40m，为使车房面积最大，应如何选择长、宽尺寸？解 设四间停车房长为，宽为由题意可知面积为，且变量，应满足，x2x1图1.1 即求，以上三个例子，虽然简单，但是它代表了三种类型的最优化问题第一个例子代表无约束极值问题：一般可表示为或这里，是定义在上的可微函数求极值的方法是从如下含有个未知数的非线性方程组中
4、解出驻点，然后判定或验证这些驻点是不是极值点第二个例子代表具有等式约束的极值问题：一般可表示为该问题的求解通常采用拉格朗日乘数法，即把这个问题转化为求的无约束极值问题第三个例子代表具有不等式约束的极值问题下面具体分析上述三种类型的最优化问题中按经典极值问题解法可能出现不能解决的情况：（1）当变量个数增加且方程组又是非线性，求解此方程组只有在相当特殊情况下才能人工解出正因为如此，通常高等数学中的求极值问题的变量个数一般不超过三个（2）当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决直到本世纪50年代，最优化理论的建立以及电子计算机的迅速发展，才为求解各种最优化问题提供了雄厚的
5、基础和有效手段不过最优化方法作为一门崭新的应用学科，有关理论和方法还没有完善，有许多问题还有待解决，目前正处于迅速发展之中最优化问题的数学模型包含三个要素：变量（又称设计变量）、目标函数、约束条件一、变量一个优化设计方案是用一组设计参数的最优组合来表示的这些设计参数可概括地划分为两类：一类是可以根据客观规律、具体条件、已有数据等预先给定的参数，统称为常量；另一类是在优化过程中经过逐步调整，最后达到最优值的独立参数，称为变量优化问题的目的就是使各变量达到最优组合变量的个数称为优化问题的维数例如有个变量的优化问题就是在维空间中寻优维空间中的点就代表优化问题中的一个方案当变量为连续量时，称为连续变量
6、；若变量只能在离散量中取值，称为离散变量二、目标函数反映变量间相互关系的数学表达式称为目标函数其值的大小可以用来评价优化方案的好坏按照规范化的形式，一般把优化问题归结为求目标函数的极小化问题，换句话说，目标函数值越小，优化方案越好对于某些追求目标函数极大的问题，可以转化成求其负值最小的问题，即因此在本书的叙述中，一律把优化问题描述为目标函数的极小化问题，其一般形式为如果优化问题只有一个目标函数，称为单目标函数，如果优化问题同时追求多个目标，则该问题的目标函数称为多目标函数多目标优化问题的目标函数通常表示为，其中这时的目标函数在目标空间中是一个维矢量，所以又称之为矢量优化问题（一般用min加一个
7、前缀“”来表示矢量极小化）三、约束条件变量间本身应该遵循的限制条件的数学表达式称为约束条件或约束函数约束条件按其表达式可分为不等式约束和等式约束两种，即上式中“s. t.”为Subject to的缩写，意即“满足于”或“受限于”按约束条件的作用还可将约束条件划分为起作用的约束（紧约束、有效约束）和不起作用的约束（松约束、消极约束）等式约束相当于空间里一条曲线（曲面或超曲面），点X必须为该曲线（曲面或超曲面）上的一点，因而总是紧约束有一个独立的等式约束，就可用代入法消去一个变量，使优化问题降低一维因此，数学模型中独立的等式约束个数应小于变量个数；如果相等，就不是一个待定优化系统，而是一个没有优化
8、余地的既定系统不等式约束通常是以其边界表现出约束作用的，它只限制点X必须落在允许的区域内（包括边界上），因而不等式约束的个数与变量个数无关不带约束条件的优化问题称为无约束最优化问题；带约束条件的优化问题称为约束最优化问题四、带约束条件的优化问题数学模型表示形式综上所述，全书所要讨论的问题是如下的（静态）最优化问题，其表示形式有三种：第一种最优化问题表示形式为第二种最优化问题表示形式为 第三种最优化问题表示形式为 （1.1）其中上述三种表示形式中，称为集约束在所讨论的最优化问题中，集约束是无关紧要的这是因为一般，不然的话，通常也可用不等式约束表达出来因此今后一般不再考虑集约束满足所有约束的点称为
9、容许点或可行点容许点的集合称为容许集或可行域可用表示一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点，使得目标函数在该点取得极小值，即这样的称为问题（1.1）的最优点，也称极小点，而相应的目标函数值称为最优值；合起来，称为最优解，但习惯上常把本身称为最优解最优点的各分量和最优值必须是有限数1.2 最优化问题的算法一、二维最优化问题的图解法二维最优化问题具有鲜明的几何解释，这对于理解有关理论和掌握所述的方法是很有益处的下面讨论的二维最优化问题为（一）约束集合当约束函数为线性时，等式约束在的坐标平面上为一条直线；不等式约束在的坐标平面上为一半平面当约束函数（例如）为非线性时，则等式约束
10、条件在的坐标平面上为一条曲线（如图1.2所示）当约束函数（例如）为非线性时，则不等式约束在的坐标平面上为曲线把坐标平面分成两部分当中的一部分（如图1.3所示）图1.2 图1.3综上所述，当把约束条件中的每一个等式所确定的曲线，以及每一个不等式所确定的部分在坐标平面上画出之后，它们相交的公共部分即为约束集合D例1.4 在坐标平面上画出约束集合解 满足的区域为以原点为圆心，半径为1的圆盘；满足的区域为第一象限中的扇形（如图1.4所示）（二）等高线我们知道在三维空间中表示一张曲面（其中为常数）在三维空间中表示平行于平面的一个平面，这个平面上任何一点的高度都等于常数（如图1.5所示）图1.4图1.5现
11、在，在三维空间中曲面与平面有一条交线交线在平面上的投影曲线是，可见曲线上的点到平面的高度都等于常数，也即曲线上的的函数值都具有相同的值当常数取不同的值时，重复上面的讨论，在平面上得到一簇曲线等高线不难看出，等高线的形状完全由曲面的形状所决定；反之，由等高线的形状也可以推测出曲面的形状在以后的讨论中，不必具体画出曲面的图形，只须在平面上变动常数画出曲线簇例1.5 在坐标平面上画出目标函数的等高线解 因为当取时，曲线表示是以原点为圆心，半径为的圆因此等高线是一簇以原点为圆心的同心圆（如图1.6所示）图1.6（三）几何意义及图解法当在坐标平面上分别画出约束集合D以及目标函数的等高线后，不难求出二维最
12、优化问题的最优解下面举例说明例1.6 用图解法求解二维最优化问题解 由例1.4得到约束集合D（如图1.7所示）目标函数的等高线是以为圆心的同心圆，并且这簇同心圆的外圈比内圈的目标函数值大因此，这一问题成为在约束集合中找一点，使其落在半径最小的那个同心圆上不难看出，问题的最优解图1.7二、最优化问题的迭代解法（一）迭代方法在经典极值问题中，解析法虽然具有概念简明，计算精确等优点，但因只能适用于简单或特殊问题的寻优，对于复杂的工程实际问题通常无能为力，所以极少使用最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的步长，从而到
13、达一个新点，用式子表示即为（1.2）式中代表前一次已取得的迭代点，在开始计算时为迭代初始点，代表新的迭代点，代表第次迭代计算的搜索方向，代表第次迭代计算的步长因子按照式（1.2）进行一系列迭代计算所根据的思想是所谓的“爬山法”，就是将寻求函数极小点（无约束或约束极小点）的过程比喻为向“山”的顶峰攀登的过程，始终保持向“高”的方向前进，直至达到“山顶”当然“山顶”可以理解为目标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法这两种算法都有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息如果是下降算法，则序列迭代点的目标函数值
14、必须满足下列关系如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即图1.8为迭代过程示意图由上面的迭代过程可知，在迭代过程中有两个规则需要确定：一个是搜索方向的选取；一个是步长因子的选取一旦和的选取方法确定，则一种迭代算法就确定，即不同的规则就对应不同的最优化方法（二）收敛速度与计算终止准则（1）收敛速度作为一个算法，能够收敛于问题的最优解当然是必要的，但仅收敛还不够，还必须能以较快的速度收敛，这才是好的算法图1.8定义1.1 设由算法A产生的迭代点列在某种“|”的意义下收敛于点，即，若存在实数及一个与迭代次数无关的常数，使得则称算法A产生的迭代点列具有阶收敛速度，或称算法A为阶收敛的特别地： 当时，称迭代点列具有线性收敛速度或称算法A为线性收敛的 当时，或时，称迭代点列具有超线性收敛速度或称算法A是超线性收敛 当时，迭代点列叫做具有二阶收敛速度或算法A是二阶收敛的一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法例1.7 设一算法A产生迭代点列，它收敛于点，试判定算法A的收敛速度解 因为 ，即取 所以算法A具有线性收敛速度例1.8 设一算法A产生迭代点列，它收敛于，试确定A的收敛速度解 因为 ，
