01最优化问题基础.docx

《01最优化问题基础.docx》由会员分享，可在线阅读，更多相关《01最优化问题基础.docx（17页珍藏版）》请在优知文库上搜索。

1、最优化问题基础1 .优化问题的模型例(曲线拟合问题)在工程检测中测得一个圆形构件轮廓上1。个点的坐标，如表所示，建立相应的数学模型确定构件轮廓曲线.轮廓数据点横坐标纵坐标点横坐标纵坐标130.4840.72630.5737.74228.5635.47732.0136.12329.4136.51828.9439.55431.0234.28928.0736.74530.1438.30IO29.4335.21解要确定构件轮廓曲线(-)2+(y-y0)2=/?2.就是要确定三个参数出,y0,R.利用最小二乘原理,使其偏差的平方和最小，f(%O,y,R)=W一*。)2+(%-%)2-的2i=l也就是构件

2、轮廓曲线拟合问题可以通过极小值问题来描述.10minf(%o,yo,R)=Y(xi-x0)2+(-VoT-R22oyoRJi=l这里隐含着约束条件R0,对问题的求解影响不大。例(厂址选择问题)设有几个市场，第/个市场位置为(p,q),它对某种货物的需求量为bj(j=l,-,n).现计划建立m个仓库，第i个仓库的存储容量为ai(i=l,m).试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小.解设第i个仓库的位置为(%i,%)(i=L,m),第i个仓库到第j个市场的货物供应量为Zija=I,m;j=1,11),则第i个仓库到第j个市场的距离为4/=1(勺一口)2+(%)2,目标函数为

3、mnmnJZOaj=22ZljJ(Xi-Pj)2+(%-qj)2i=lJ=Ii=lJ=I约束条件如下：(1)每个仓库向各市场提供的货物量之和不能超过它的存储容量；(2)每个市场从各仓库得到的货物量之和应等于它的需求量；(3)运输量不能为负数.因此，该问题的数学模型为mnmnminf(x)=W%djj=WWZijJ(Xi-Pj)2+(%-%)2i=ly三li=lj=ls.L罟=IZtj脓(iEU/)称为约束函数(constraintfunctions).不等式约束G(%)O可以写成-CiQO有时候用九屋无)=0,iE,OjG)0,j/分别表示等式约束和不等式约束。集合D=xci(x)=0,iE-

4、,ci(x)0,i/;%RnDvl称为问题(1)的可行域(Feasibledomain)o若xWD,则称X为可行点(FeaSibleSOhltiOi1).设亢D,对于OHdRni如果存在0,使得x+dED,60,则称d为无处的可行方向，X处所有可行方向构成的集合记为FD(x)o可行方向在二推空间内的演示.4站个可行方向,4不是可行方向在所有满足约束条件的决策变量中，使目标函数取最小值的变量X*称为优化问题(1)的最优解，即对任意0都有/(X)/(x*).如果求解在约束集合D上目标函数/(X)的最大值，则问题的“min”应相应地替换为“max”.在集合。上，函数f的最小(最大)值不一定存在，但是

5、其下确界inf/、上确界SUPf总是存在的.因此当目标函数的最小(最大)值不存在时，我们便关心其下(上)确界，即将问题(1)中的,min(max)n改为,inf(sup).如果S是一个有上界的实数集，那么存在一个最小的实数乂使得对于xS,%yo称为集合S的最小上界QeaStUPPerboUnd)或上确界(supremum),记为：SUPXeSCo或者supx:XES类似地，集合S的最大下界(greatestlowerbound)或下确界(idfimum)记为：infxes(x)或者infx:xES有限点集一定有一个最大值、最小值，此时最大值和上确界相同，最小值和下确界相同。某些无限点集可能不存

6、在最大值或最小值。如-exp(-x)xo,没有最大值，但有上确界为1(不可达)。WhensupCC,wesaythesupremumofCisattainedorachieved.例minxx0,St1,%R不存在最小值，但存在下确界(O).2 .优化问题存在最优解的条件邻域点XRn的邻域N(工)=y脓7l:IIy-XII0均有Ng(x)nsw0,则称工属于集合S的闭包，记为Cis集合S的闭包ClS=SUdSl它是包含集合D的最小的闭集.如果集合S包含它的每个点的邻域，该集合是开集(OPenSet)也就是说，如果S的每个点都是内点，或者S不包含任何边界点，那么S是开集。如果集合S包含S的所有边

7、界点，那么称S是闭集(CIOSedset)。定理：一个集合是闭集当且仅当该集合的补是开集。Sl=xrX21:1X12,1X22Sl是开集S2=X1，X2】T：3WX14,1x22S2是闭集111H012345例Isthesetopen,closed,orneither?Intervalsontherealline(0,+)open(8,0closed0,l)(8, )空集notopen,notclosedopenandclosedopenandclosed unionofanynumberofopensetsisanopenset. theintersectionofafinitenumber

8、ofopensetsisopen. Unionsandintersectionsofclosedsetsareclosed. 连续函数的水平集和下水平集是闭集如果一个集合可以被一个有限半径的球体所包围，那么该集合称为有界集(boundedset)o如果一个集合既是闭集又是有界集，那么该集合称为紧集(ComPaetset)o能举出一个是闭集但不是紧集的例子吗？TakeanyboundedopensubsetSRn,thenRnSisclosedbutnotbounded.取S=(0,l)1RS=S=(-,0U1,8)isaclosedbutunboundedset.紧集对于优化问题而言是非常重要

9、的。魏尔斯特拉斯定理魏尔斯特拉斯定理(WeierStraSS定理)：假设fC-脓是一个连续函数，其中CU是紧集。那么，必定存在点X0。，使得对于所有的工。都有/(X0)/(%)。也就是说，/能够在C上取得极小值。定理给出了最优解的存在性条件，定义在紧集上的连续函数一定存在最大(最小)值点。但其对应的解可能不止一个.为了使可行域D为紧集，约束优化问题的约束条件取G(X)40,而不是G(X)0。在许多实际问题中，定义域可能不是紧集，目标函数也不一定连续，因此需要将此定理推广来保证最优化问题解的存在性.例/(X)=/,%R定义域不是有界闭集广义实值函数数学分析中函数是从向量空间Rn到实数域R的映射，

10、-8VQV+8,V脓。在最优化领域，经常涉及对某个函数取inf(sup)操作，这导致函数的取值可能为无穷。为了能够更方便地描述优化问题，我们需要对函数的定义进行某种扩展.def定义(广义实值函数,extendedreal-valuedfmction)令眩=Ru为广义实数空间，则映射fn称为广义实值函数.从广义实值函数的定义可以看出，函数的定义域不包含8,其值域多了两个特殊的值,BP-,+.规定：a0,值域是(-8,+8),定义域中不含函数值趋近8的点。广义实值函数InX的定义域是xo,值域是-8,+8),定义域中包含函数值趋近8的点O适当函数适当函数是一类很重要的广义实值函数，很多最优化理论都

11、是建立在适当函数之上的.定义(适当函数,Properfiinction)给定广义实值函数/和非空集合X.如果存在%使得fix)-,那么称函数f关于集合X是适当的.适当函数的值域是(-8,+8概括来说，适当函数f的特点是“至少有一处取值不为正无穷”，以及”处处取值不为负无穷”.对最优化问题minx(x),适当函数可以帮助去掉一些我们不感兴趣的函数，从而在一个比较合理的函数类中考虑最优化问题.我们约定：在本书中若无特殊说明，定理中所讨论的函数均为适当函数.对于适当函数/,规定其定义域dom=xI/(X)+.正是因为适当函数的最小值不可能在函数值为无穷处取到，因此dom的定义方式是自然的.例/(X)

12、=+8、/(x)=Inx(x0)都不是适当函数。闭函数闭函数是另一类重要的广义实值函数，后面许多定理都建立在闭函数之上.在数学分析课程中我们接触过连续函数，本小节介绍的闭函数可以看成是连续函数的一种推广.在介绍闭函数之前，先引入一些基本概念.下水平集是描述实值函数取值情况的一个重要概念.定义(。下水平集，sub-levelset)对于广义实值函数/：KnCa=xf(x)a称为f的下水平集.在最优化问题中，多数情况都要对函数/(X)求极小值，通过研究。下水平集可以知道具体在哪些点处/(X)的值不超过Q.若Ca非空，就知道/(X)的全局极小点(若存在)一定落在Ca中，因此也就无需考虑Ca之外的点。上方图是从集合的角度来描述一个函数的具体性质.定义(上方图,epigraph)对于广义实值函数广即T曲，epi=(x,t)Rn+11/(*)t称为/的上方图.图2.2函数f和其上方图epif上方图将函数和集合建立了联系，/的很多性质都可以在epi上得到体现.在后面的分析中将看到，可以通过e