第1章最优化问题总论

《第1章最优化问题总论》由会员分享，可在线阅读，更多相关《第1章最优化问题总论（49页珍藏版）》请在金锄头文库上搜索。

1、第一章 最优化问题总论,无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标这是最简单的最优化问题，实际优化问题一般都比较复杂,概括地说，凡是追求最优目标的数学问 题都属于最优化问题作为最优化问题，一般 要有三个要素：第一是目标；第二是方案； 第三是限制条件而且目标应是方案的“函 数”如果方案与时间无关，则该问题属于静 态最优化问题；否则称为动态最优

2、化问题 本书只讨论静态最优化问题,第一章 最优化问题总论,1.1 最优化问题数学模型 1.2 最优化问题的算法 1.3 最优化算法分类 1.4 组合优化问题简介,1.1 最优化问题数学模型,最简单的最优化问题实际上在高等数学 中已遇到，这就是所谓函数极值，我们习惯 上又称之为经典极值问题 例1.1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,结论是，每个角剪去边长为的正方形可使 所制成的水槽容积最大,解 设剪去的正方形边长为x，由题意易知，与此相应的水槽容积为 令 得两个驻点： 第一个驻点不合实际，这是因为剪去4个边长为的正方形相当于将铁

3、板全部剪去现在来判断第二个驻点是否为极大点 因为 是极大点,例1.2 求侧面积为常数体积最大的长方体体积 解 设长方体的长、宽、高分别为，体积 为，则依题意知体积为 限制条件为 由拉格朗日乘数法，考虑函数 令,由题意可知 应是正数，由此，将上面三个等式分别乘以，并利用条件，得到 比较以上三式可得,从而x=y=z=a，右侧面积固定的长方 体的最大体积客观存在，因此侧面积固定 的长方体中以正方体体积最大,例1.3 某单位拟建一排四间的停车房，平面位置如图1.1所示由于资金及材料的限制，围墙和隔墙的总长度不能超过40m，为使车房面积最大，应如何选择长、宽尺寸？,解 设四间车房长为，宽为由题意可知面积

4、为 且变量，应满足 即求，,以上三个例子，虽然简单，但是它代表了三种类型的最优化问题 第一个例子代表无约束极值问题： 一般地可表示为或 这里是定义在上的可微函数 求极值的方法是从如下含有个未知数的非线性方程组 中解出驻点，然后判定或验证这些驻点是不是极值点,第二个例子代表具有等式约束的极值问题： 一般地可表示为 该问题的求解通常采用拉格朗日乘数法，即把这个问题转化为求 的无约束极值问题 第三个例子代表具有不等式约束的极值问题,下面具体分析上述三种类型的最优化问题中按经典极值问题解法可能出现不能解决的问题：,（1）当变量个数增加且方程组又是非线性，求解此方程只有在相当特殊情况下才能人工解出正因为

5、如此，通常高等数学中的求极值问题的变量个数一般不超过三个 （2）当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决 要解决上述问题，直到本世纪50年代最优化理论建立以及电子计算机的迅速发展才为求解各种最优化问题提供了雄厚的基础和有效手段而且最优化方法作为一门崭新的应用学科，有关理论和方法还没有完善，有许多问题还有待解决，目前正处于迅速发展之中,最优化问题的数学模型包含有三个要求：即变 量（又称设计变量）、目标函数、约束条件 一、变量 二、目标函数 三、约束条件 四、带约束条件的优化问题数学模型表示形式,综上所述，全书所要讨论的问题是如下的（静态）最优化问 题，其表示形式有三种

6、： 第一种最优化问题表示形式为 第二种最优化问题表示形式为 第三种最优化问题表示形式为 （1.1） 其中,上述三种表示形式中，称为集约束在所讨论的最优化问题中，集约束是无关紧要的这是因为一般，不然的话，通常也可用不等式约束表达出来因此今后一般不再考虑集约束 满足所有约束的点称为容许点或可行点容许点的集合称为容许集或可行域可用 表示 一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点，使得目标函数在该点取得极小值，即 这样的称为问题（1.1）的最优点，也称极小点，而相应的目标函数值称为最优值；合起来，称为最优解，但习惯上，把本身称为最优解最优点的各分量和最优值必须是有限数,1.2 最优

7、化问题的算法,一、二维优化问题的图解法 讨论二维最优化问题为,（一）约束集合 当约束函数为线性时，等式约束在的坐标平面上为一条直线；不等式约束在的坐标平面上为一半平面当约束函数为非线性时，例如，则等式约束条件：在的坐标平面上为一条曲线（如图所示） 当约束函数为非线性时，例如，则不等式约束在的坐标平面上为曲线把坐标平面分成两部分当中的一部分（如图所示）,综上所述，当把约束条件中的每一个 等式所确定的曲线，以及每一个不等式所 确定的部分在坐标平面上画出之后，它 们相交的公共部分即为约束集合D,例1.4 在坐标平面上画出约束集合 解 满足的区域为以原点为圆心，半径为1 的圆；满足的区域为第一象限的扇

8、形（如 图所示）,（二）等高线 我们知道 在三维空间中表示一张曲面 （其中为常数）在三维空间中表示平行于 平面的一个平面，这个平面上任何一点的高度都等于常数 （如图1.5所示） 现在，在三维空间中曲面 与平面 有一条交线 交线在平面上的投影曲线是 ，可见曲线上的点到平面 的高度都等于常数C，也即曲线上的的函数值都具有相同的值当常数取不同的值时，重复上面的讨论，在平面上得到一族曲线等高线不难看出，等高线的形状完全由曲面的形状所决定；反之，由等高线的形状也可以推测出曲面的形状在以后的讨论中，不必具体画出曲线的图形，只须在平面上变动常数画出曲线族,等高线示意图,例1.5 在坐标平面上画出目标函数的等

9、高线 解 因为当取时，曲线表示是以原点为圆心，半径为的圆因此等高线是一族以原点为圆心的同心圆（如图所示）,例1.6 用图解法求解二维最优化问题 解 由例1.4得到约束集合D（如图所示）目标函数的等高 线是以为圆心的同心圆，并且这族同心圆的外圈比内圈的 目标函数值大因此，这一问题成为在约束集合中找一点 使其落在半径最小的那个同心圆上不难看出，问题的最优 解,二、最优化问题的迭代解法,在经典极值问题中，解析法虽然具有概念简明,计算 精确等优点，但因只能适用于简单或特殊问题的寻优, 对于复杂的工程实际问题通常无能为力，所以极少使用 最优化问题的迭代算法A是指：从某一选定的初始点 出发，根据目标函数、

10、约束函数在该点的某些信息，确 定本次迭代的一个搜索方向和适当的步长，从而到达一 个新点，用式子表示即为,(1.2) 式中, 前一次已取得的迭代点，在 开始计算时为迭代初始点； 新的迭代点； 第次迭代计算的搜索方向； 第次迭代计算的步长因子,按照式（1.2）进行一系列迭代计算所根据 的思想是所谓的“爬山法”，就是将寻求函数极小 点（无约束或约束极小点）的过程比喻为向“山” 的顶峰攀登的过程，始终保持向“高”的方向前 进，直至达到“山顶”当然“山顶”可以理解为目 标函数的极大值，也可以理解为极小值，前者称 为上升算法，后者称为下降算法这两种算法都 有一个共同的特点，就是每前进一步都应该使目 标函数

11、有所改善，同时还要为下一步移动的搜索 方向提供有用的信息如果是下降算法，则序列 迭代点的目标函数值必须满足下列关系,如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即 迭代过程示意图 由上面的迭代过程可知，在迭代过程中有两个规则需要确 定：一个是搜索方向的选取；一个是步长因子的选取一 旦选取方法和的选取方法确定，则一种迭代算法A就确 定，即不同的规则就对应不同的最优化方法,（二）收敛速度与计算终止准则 （1）收敛速度 作为一个算法A，能够收敛于问题的最优解当然 是必要的，但光能收敛还不够，还必须能以较快 的速度收敛，这才是好的算法 定义1.1 设由算法A产生的迭代点列 在某种

12、“|” 的意义下收敛于点 ，即 ,若 存在实数 及一个与迭代次数 无关的常数使得 则算法A产生的迭代点列叫做具有阶收敛速度,或 算法A叫做是阶收敛的，特别地 :, 当 ，迭代点列 称为具有线性收敛速度或算法A称为线性收敛的 当 ，或 时，迭代点列 叫做具有超线性收敛速度或称算法A是超线性收敛 当 时，迭代点列 叫做具有二阶收敛速度或算法A是二阶收敛的 一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法,例1.7 设一算法A产生迭代点列 ，它收敛于点 试判定算法A的收敛速度 解 ， 存在 算法A具有线性收敛速度 例1.8 设一算法A产生迭代点列 ，它收敛于 ，试确定A的收敛速度 解 A具有超

13、线性收敛,(2)计算终止准则 用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问题 从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代但是这在实际上是办不到的因为对于一个待求的优化问题，其理论极小点在哪里并不知道所知道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代 对于无约束优化问题通常采用的迭代终止准则有以下几种：,点距准则 相邻两迭代点之间的距离已达到充分小，即 式中， 是一个充分小正数，代表计算精度 函数下降量准则 相邻两迭代点的函数值下降量已达

14、到充分小当 时， 可用函数绝对下降量准则 当 时，可用函数相对下降量准则 梯度准则 目标函数在迭代点的梯度已达到充分小，即 这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有 可能导致误把驻点作为最优点.(凸函数的定义请参见第二章2.6节) 对于约束优化问题，不同的优化方法有各自的终止准则,综上所述，优化算法的基本迭代过程如下： 选定初始点 ，置 按照某种规则确定搜索方向 按某种规则确定 使得 计算 判定 是否满足终止准则若满足，则打印 和 ,停机；否则置 ,转 上述算法用框图表达如图.,N,Y,结束,确定t，使得 f (X0+t P) f (X0),X=X0+t P,X0=X,开始,选

15、定,确定P,X是否满足终止准则,输出X， f (X),1.3 最优化算法分类,所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规则来得到满足用户要求的问题的解 就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典算法、构造型算法、改进型算法、基于系统动态演化的算法和混合型算法等 （1）经典算法包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法，其算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用 （2）构造型算法用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要譬如，调度问题中的典型构造型方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、NEH法等,(3）改进型算法，或称邻域搜索算法从任一解出发，对其邻域的不断搜索和当前解的替换来实现优化根据搜索行为，它又可分为局部搜索法和指导性搜索法 局部搜索法以局部优化策略在当前解的邻域中贪婪搜索，如只接受优于当前解的状态作为下一当前解的爬山法；接受当前解邻域中的最好解作为下一当前解的最陡下降法等 指导性搜索法利用一些指