最优化方法及其应用Word格式文档下载.doc

最优化方法及其应用Word格式文档下载.doc

《最优化方法及其应用Word格式文档下载.doc》由会员分享，可在线阅读，更多相关《最优化方法及其应用Word格式文档下载.doc（160页珍藏版）》请在冰点文库上搜索。

由题意可知应是正数，由此，将上面三个等式分别乘以并利用条件，得到

比较以上三式可得

从而．又侧面积固定的长方体的最大体积客观存在，因此侧面积固定的长方体中以正方体体积最大，其最大值为．

例1.3某单位拟建一排四间的停车房，平面位置如图1.1所示．由于资金及材料的限制，围墙和隔墙的总长度不能超过40m，为使车房面积最大，应如何选择长、宽尺寸？

解设四间停车房长为，宽为．由题意可知面积为

且变量，应满足

x2

x1

图1.1

即求 ，

以上三个例子，虽然简单，但是它代表了三种类型的最优化问题．

第一个例子代表无约束极值问题：

一般可表示为或．这里，是定义在上的可微函数．

求极值的方法是从如下含有个未知数的非线性方程组

中解出驻点，然后判定或验证这些驻点是不是极值点．

第二个例子代表具有等式约束的极值问题：

一般可表示为

该问题的求解通常采用拉格朗日乘数法，即把这个问题转化为求

的无约束极值问题．

第三个例子代表具有不等式约束的极值问题．

下面具体分析上述三种类型的最优化问题中按经典极值问题解法可能出现不能解决的情况：

（1）当变量个数增加且方程组又是非线性，求解此方程组只有在相当特殊情况下才能人工解出．正因为如此，通常高等数学中的求极值问题的变量个数一般不超过三个．

（2）当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决．

直到本世纪50年代，最优化理论的建立以及电子计算机的迅速发展，才为求解各种最优化问题提供了雄厚的基础和有效手段．不过最优化方法作为一门崭新的应用学科，有关理论和方法还没有完善，有许多问题还有待解决，目前正处于迅速发展之中．

最优化问题的数学模型包含三个要素：

变量（又称设计变量）、目标函数、约束条件．

一、变量

一个优化设计方案是用一组设计参数的最优组合来表示的．这些设计参数可概括地划分为两类：

一类是可以根据客观规律、具体条件、已有数据等预先给定的参数，统称为常量；

另一类是在优化过程中经过逐步调整，最后达到最优值的独立参数，称为变量．优化问题的目的就是使各变量达到最优组合．变量的个数称为优化问题的维数．例如有个变量的优化问题就是在维空间中寻优．维空间中的点就代表优化问题中的一个方案．当变量为连续量时，称为连续变量；

若变量只能在离散量中取值，称为离散变量．

二、目标函数

反映变量间相互关系的数学表达式称为目标函数．其值的大小可以用来评价优化方案的好坏．按照规范化的形式，一般把优化问题归结为求目标函数的极小化问题，换句话说，目标函数值越小，优化方案越好．对于某些追求目标函数极大的问题，可以转化成求其负值最小的问题，即

因此在本书的叙述中，一律把优化问题描述为目标函数的极小化问题，其一般形式为

如果优化问题只有一个目标函数，称为单目标函数，如果优化问题同时追求多个目标，则该问题的目标函数称为多目标函数．

多目标优化问题的目标函数通常表示为

其中．这时的目标函数在目标空间中是一个维矢量，所以又称之为矢量优化问题（一般用min加一个前缀“”来表示矢量极小化）．

三、约束条件

变量间本身应该遵循的限制条件的数学表达式称为约束条件或约束函数．

约束条件按其表达式可分为不等式约束和等式约束两种，即

上式中“s.t.”为Subjectto的缩写，意即“满足于”或“受限于”．按约束条件的作用还可将约束条件划分为起作用的约束（紧约束、有效约束）和不起作用的约束（松约束、消极约束）．等式约束相当于空间里一条曲线（曲面或超曲面），点X必须为该曲线（曲面或超曲面）上的一点，因而总是紧约束．有一个独立的等式约束，就可用代入法消去一个变量，使优化问题降低一维．因此，数学模型中独立的等式约束个数应小于变量个数；

如果相等，就不是一个待定优化系统，而是一个没有优化余地的既定系统．不等式约束通常是以其边界表现出约束作用的，它只限制点X必须落在允许的区域内（包括边界上），因而不等式约束的个数与变量个数无关．不带约束条件的优化问题称为无约束最优化问题；

带约束条件的优化问题称为约束最优化问题．

四、带约束条件的优化问题数学模型表示形式

综上所述，全书所要讨论的问题是如下的（静态）最优化问题，其表示形式有三种：

第一种最优化问题表示形式为

第二种最优化问题表示形式为

第三种最优化问题表示形式为

（1.1）

其中．

上述三种表示形式中，称为集约束．在所讨论的最优化问题中，集约束是无关紧要的．这是因为一般，不然的话，通常也可用不等式约束表达出来．因此今后一般不再考虑集约束．

满足所有约束的点称为容许点或可行点．容许点的集合称为容许集或可行域．可用

表示．

一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点，使得目标函数在该点取得极小值，即

这样的称为问题（1.1）的最优点，也称极小点，而相应的目标函数值称为最优值；

合起来，称为最优解，但习惯上常把本身称为最优解．最优点的各分量和最优值必须是有限数．

1.2最优化问题的算法

一、二维最优化问题的图解法

二维最优化问题具有鲜明的几何解释，这对于理解有关理论和掌握所述的方法是很有益处的．下面讨论的二维最优化问题为

（一）约束集合

当约束函数为线性时，等式约束在的坐标平面上为一条直线；

不等式约束在的坐标平面上为一半平面．当约束函数（例如）为非线性时，则等式约束条件在的坐标平面上为一条曲线（如图1.2所示）．当约束函数（例如）为非线性时，则不等式约束在的坐标平面上为曲线把坐标平面分成两部分当中的一部分（如图1.3所示）．

图1.2 图1.3

综上所述，当把约束条件中的每一个等式所确定的曲线，以及每一个不等式所确定的部分在坐标平面上画出之后，它们相交的公共部分即为约束集合D．

例1.4在坐标平面上画出约束集合

解满足的区域为以原点为圆心，半径为1的圆盘；

满足的区域为第一象限中的扇形（如图1.4所示）．

（二）等高线

我们知道

在三维空间中表示一张曲面．（其中为常数）在三维空间中表示平行于平面的一个平面，这个平面上任何一点的高度都等于常数（如图1.5所示）．

图1.4 图1.5

现在，在三维空间中曲面与平面有一条交线．交线在平面上的投影曲线是，可见曲线上的点到平面的高度都等于常数，也即曲线上的的函数值都具有相同的值．当常数取不同的值时，重复上面的讨论，在平面上得到一簇曲线——等高线．不难看出，等高线的形状完全由曲面的形状所决定；

反之，由等高线的形状也可以推测出曲面的形状．在以后的讨论中，不必具体画出曲面的图形，只须在平面上变动常数画出曲线簇．

例1.5在坐标平面上画出目标函数的等高线．

解因为当取时，曲线表示是以原点为圆心，半径为的圆．因此等高线是一簇以原点为圆心的同心圆（如图1.6所示）．

图1.6

（三）几何意义及图解法

当在坐标平面上分别画出约束集合D以及目标函数的等高线后，不难求出二维最优化问题的最优解．下面举例说明．

例1.6用图解法求解二维最优化问题

解由例1.4得到约束集合D（如图1.7所示）．目标函数的等高线是以为圆心的同心圆，并且这簇同心圆的外圈比内圈的目标函数值大．因此，这一问题成为在约束集合中找一点，使其落在半径最小的那个同心圆上．不难看出，问题的最优解．

图1.7

二、最优化问题的迭代解法

（一）迭代方法

在经典极值问题中，解析法虽然具有概念简明，计算精确等优点，但因只能适用于简单或特殊问题的寻优，对于复杂的工程实际问题通常无能为力，所以极少使用．

最优化问题的迭代算法是指：

从某一选定的初始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的步长，从而到达一个新点，用式子表示即为

（1.2）

式中代表前一次已取得的迭代点，在开始计算时为迭代初始点，代表新的迭代点，代表第次迭代计算的搜索方向，代表第次迭代计算的步长因子．

按照式（1.2）进行一系列迭代计算所根据的思想是所谓的“爬山法”，就是将寻求函数极小点（无约束或约束极小点）的过程比喻为向“山”的顶峰攀登的过程，始终保持向“高”的方向前进，直至达到“山顶”．当然“山顶”可以理解为目标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法．这两种算法都有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息．如果是下降算法，则序列迭代点的目标函数值必须满足下列关系

如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即

图1.8为迭代过程示意图．

由上面的迭代过程可知，在迭代过程中有两个规则需要确定：

一个是搜索方向的选取；

一个是步长因子的选取．一旦和的选取方法确定，则一种迭代算法就确定，即不同的规则就对应不同的最优化方法．

（二）收敛速度与计算终止准则

（1）收敛速度

作为一个算法，能够收敛于问题的最优解当然是必要８的，但仅收敛还不够，还必须能以较快的速度收敛，这才是好的算法．

图1.8

定义1.1设由算法A产生的迭代点列在某种“||·

||”的意义下收敛

于点，即，若存在实数及一个与迭代次数无关

的常数，使得

则称算法A产生的迭代点列具有阶收敛速度，或称算法A为阶收敛的．特别地：

①当时，称迭代点列具有线性收敛速度或称算法A为线性收敛的．

②当时，或时，称迭代点列具有超线性收敛速度或称算法A是超线性收敛．

③当时，迭代点列叫做具有二阶收敛速度或算法A是二阶收敛的．

一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法．

例1.7设一算法A产生迭代点列，它收敛于点，试判定算法A的收敛速度．

解因为 ，

即取．

所以算法A具有线性收敛速度．

例1.8设一算法A产生迭代点列，它收敛于，试确定A的收敛速度．

解因为

即取．

所以A是超线性收敛的．

（2）计算终止准则

用迭代方法寻优时，其迭代过程不能无限制地进行下去，那么什么时候截断这种迭代呢？

这就是迭代什么时候终止的问题．

从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代．但是这在实际上是办不到的．因为对于一个待求的优化问题，其理论极小点在哪里并不知道．所知道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代．

对于无约束优化问题通常采用的迭代终止准则有以下几种：

①点距准则

相邻两迭代点之间的距离已达到充分小，即

上式中是一个充分小的正数，代表计算精度．

②函数下降量准则

相邻两迭代点的函数值下降量已达到充分小．当时，可用函数绝对下降量准则

当时，可用函数相对下降量准则

③梯度准则

目标函数在迭代点的梯度已达到充分小，即

这一准则对于定义域上的凸函数是完全正确的．若是非凸函数，有可能导致误把驻点作为最优点．（凸函数的定义请参见第二章2.6节）

对于约束优化问题，不同的优化方法有各自的终止准则．

综上所述，优化算法的基本迭代过程如下：

①选定初始点，置．

②按照某种规则确定搜索方向．

③按某种规则确定使得

④计算

⑤判定是否满足终止准则．若满足，则打印和，停机；

否则置，转②．

上述算法用框图表达如图1.9．

N

Y

X是否满足终止准则

输出X，f（X）

开始

结束

选定X0

确定P

确定t，使得f（X0+tP）<

f（X0）

X=X0+tP

X0=X

图1.9

1.3最优化算法分类

所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规则来得到满足用户要求的问题的解．

就优化机制与行为而分，目前工程中常用的优化算法主要可分为：

经典算法、构造型算法、改进型算法、基于系统动态演化的算法和混合型算法等．

（1）经典算法．包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法，其算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用．

（2）构造型算法．用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要．譬如，调度问题中的典型构造型方法有：

Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、NEH法等．

（3）改进型算法，或称邻域搜索算法．从任一解出发，对其邻域的不断搜索和当前解的替换来实现优化．根据搜索行为，它又可分为局部搜索法和指导性搜索法．

①局部搜索法．以局部优化策略在当前解的邻域中贪婪搜索，如只接受优于当前解的状态作为下一当前解的爬山法；

接受当前解邻域中的最好解作为下一当前解的最陡下降法等．

②指导性搜索法．利用一些指导规则来指导整个解空间中优良解的探索，如SA、GA、TS等．

（4）基于系统动态演化的算法．将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等．

（5）混合型算法．指上述各算法从结构或操作上相混合而产生的各类算法．

优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法，局部优化算法和全局优化算法等．

1.4组合优化问题简介

一、组合优化问题建模

优化问题涉及的工程领域很广，问题种类与性质繁多，归纳而言，最优化问题可分为函数优化问题和组合优化问题两大类，上一节介绍的最优化数学模型属于函数优化问题，该函数优化的对象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态．本节重点介绍组合优化问题．

组合优化问题是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域，该问题数学模型可表示为

其中为目标函数，和为约束函数，X为决策变量，表示有限个点组成的集合．

一个组合优化问题可用3个参数表示，其中表示决策变量的定义域，D表示可行解区域，D中的任何一个元素称为该问题的可行解，表示目标函数，满足的可行解称为该问题的最优解．组合最优化问题的特点是可行解集合为有限集．由直观可知，只要将中有限个点逐一判别是否满足约束条件和比较目标函数值的大小，该问题的最优解一定存在并可以求得，下面是三个典型的组合优化问题．

例1.90-1背包问题（knapsackproblem）

设有一个容积为的背包，个体积分别为，价值分别为的物品，如何以最大的价值装包?

这个问题称为0-1背包问题．用数学模型表示为

， （1.3）

其中目标（1.3）欲使包内所装物品的价值最大，式（1.4）为包的能力限制，式（1.5）表示为二进制变量，表示装第i个物品，则表示不装．

例1.10旅行商问题（TSP，travelingsalesmanproblem）

一个商人欲到个城市推销商品，每两个城市i和之间的距离为，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短．TSP还可以细分为对称和非对称距离两大类问题．当对任意的时都有，则称该TSP为对称距离TSP，否则称为非对称距离TSP．对一般的TSP，它的一种数学模型描述为

， （1.6）

以上是基于图论的数学模型．其中式（1.10）中的决策变量=1表示商人行走的路线包含从城市到城市的路径，表示商人没有选择走这条路．的约束可以减少变量的个数，使得共有个决策变量．目标（1.6）要求距离之和最小．式（1.7）要求商人从城市出来一次，式（1.8）要求商人走入城市只有一次．式（1.7）和式（1.8）表示每个城市经过一次．仅有式（1.7）和式（1.8）的约束无法避免回路的产生，一条回路是由个城市和条弧组成，因此，式（1.9）约束旅行商在任何一个城市子集中不形成回路，其中表示集合中元素个数．

例1.11聚类问题

m维空间上的个模式要求聚类成类，使得各类本身内的点最相近，即，其中为第类的中心，，，为第类中的点数．

二、算法复杂性

前面给大家介绍的三个组合优化问题例子，模型建立都比较简单，但要求它们的最优解却很困难，而解模型的困难主要原因是所谓的“组合爆炸”，如聚类问题的可能划分方式有个，TSP问题有个．显然状态数量随问题规模呈超指数增长，若计算机每秒处理1亿种排列，则列举20个城市问题的20！

种排列约需几百年．如此巨大的计算量是无法承受的，更不用谈更大规模问题的求解，因此解决这些问题的关键在于寻求有效的优化算法，也正是由于组合优化问题算法的复杂性，激起了人们对它的理论与算法研究的兴趣．

算法的复杂性是指算法对时间复杂性和对空间复杂性．按照算法复杂性求解的难易程度，可把组合优化问题分为P类，NP类和NP完全类．

算法或问题的复杂性一般表示为问题规模（如TSP问题中的城市数）的函数，时间的复杂性记为，空间的复杂性记为．在算法分析和设计中，沿用实用性的复杂性概念，即把求解问题的关键操作，如加、减、乘，比较等运算指定为基本操作，算法执行基本操作的次数则定义的算法的时间复杂性，算法执行期间占用的存储单元则定义为算法的空间复杂性．P类问题指具有多项式时间求解算法的问题类．许多优化问题仍没有找到求得最优解的多项式时间算法，称这种比P类问题更广泛的问题为非确定型多项式算法的问题类，即NP问题．

三、NP完全问题

离散问题的求解常常要从有限个方案中选出一个满意的结果来，也许有人认为，从有限个方案中挑选一个，总是比较容易的．然而，事实并非如此，关键在于问题的规模．由于计算机的出现，人们对问题的求解在观念上发生了改变，一个在理论上可解的问题如果在求解时需要花费相当多，以至于不合理的时间（如几百年甚至更长时间），我们不能认为它已解决，而应当努力寻找更好的算法．

如何比较算法的好坏呢？

从不同的角度出发可以有不同的回答．这里，仅就算法的计算速度作一个十分粗略的比较．

设有一台每小时能进行M次运算的计算机．并设问题已有两种不同的算法，算法A对规模为的问题约需作次运算，算法B则约需作次运算．运用算法A在一个小时内大约可解一个规模为的问题，而算法B则大约可解一个规模为的问题．

现在假设计算机有了改进，例如计算速度提高了100倍．此时，利用算法A能求解的问题规模增大了10倍，利用算法B可解的问题规模只增加了．前者得到了成倍的增加，而后者则几乎没有什么改变，今天无法求解的问题，将来也很少有希望解决．由于这一原因，对算法作如下分类．

定义1.2（多项式算法）设A是求解某类问题D的一个算法，为问题D的规模，用表示用算法A在计算机上求解这一问题时需作的初等运算的次数．若存在一个多项式和正整数N，当时，总有（不论求解的D是怎样的具体实例），则称算法A是求解问题D的一个多项式算法．

定义1.3（指数算法）设算法B是求解某类问题D的一个算法，若存在一个常数，对任意，总可以找到问题D的一个规模为的实例，用算法B求解时，所需的计算量约为，则称B为求解问题D的一个指数算法．

多项式算法被称为是“好”算法（或有效算法），而指数算法则一般认为是“坏”算法，因为它只能用来求解规模很小的问题．

这样看来，对一个问题只有在找到求解它的多项式算法后才能较为放心．然而十分可惜的是，对于许多具有广泛应用价值的离散模型，人们至今仍未找到多项式算法．现在的任何算法在最坏的情况下计算量均可达到或接近．

1971年和1972年，S.Cook和R.Karp分别发表了相关论文，奠定了NP完全理论基础．Cook指出，NP完全类问题，具有两个性质：

（1）这类问题中的任何一个问题至今均未发现有多项式算法．

（2）只要其中任一个问题找到了多项式算法，那么其他所有问题也就有了多项式算法．

现在，NP完全类中的问题已被扩充到了四千多个，其中包括前面讨论的旅行商问题．对它们的研究使人们越来越相信这样一个猜测：

对这类问题也许根本不存在多项式算法．

第二章最优化问题数学基础

为了便于学习最优化方法，本章将对与优化方法密切相关的数学知识作一简要介绍，而有些数学知识将在讲解各种算法时，随之介绍．

2.1二次型与正定矩阵

一、二次型与实对称矩阵

二次型理论在最优化设计中应用十分广泛．应用矩阵的乘法运算，二次型与实对称矩阵紧密地联系在一起了，从而二次型的基本问题又可转化成实对称矩阵问题．

二次型理论问题起源于化二次曲线和二次曲面的方程为标准形式的问题．推广到n维空间中，二次超曲面的一般方程为

用矩阵表示可简记为

其中矩阵A的元素正是二次型的项的系数的一半，是二次型的项的系数．因此，二次型和它的矩阵A是相互唯一决定的，且．

二、正定矩阵

定义2.1如果二次型

对于任何一组不全为零的数恒有

则称正定，且二次型矩阵A也称为正定．

简言之，一个对称矩阵A如果是正定的，则二次型对于所有非零向量X其值总为正．类似可以给出定义，若二次型，则A为半正定矩阵；

若，则A为半负定矩阵；

若二次型既不是半正定又不是半负定，就称矩阵A为不定的．

矩阵A为正定的充要条件是它的行列式的顺序主子式全部大于零，即

由此可见，正定矩阵必然是非奇异的．

例2.1判断矩阵是否正定．

解∵，

∴A是正定的．

2.2方向导数与梯度

一、方向导数

所谓方向导数的概念是作为偏导数的一个推广而引入的，它主要研究函数沿任一给定方向的变化率．

定义2.2设在点处可微，P是固定不变的非零向量，是方向P上的单位向量，则称极限

（2.1）

为函数在点处沿P方向的方向导数，式中是它的记号．

定义2.3设是连续函数，，且，若存在，当时都有，则称P为在点处的下降方向．若，则称P为在点处的上升方