01最优化问题基础.docx

最优化问题基础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也就是构件轮廓曲线拟合问题可以通过极小值问题来描述.10minf(%o,yo,R)=Y(xi-x0)2+(¾-VoT-R22o>yo>RJi=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,目标函数为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<saiti=l,m,况iZIj=bj,j=lf-,n,ZijOJ=1,m;j=1,，n最优化问题数学模型的一般形式min/(x)S.t.G(%)=0,iE=l,2,1,G(%)O,i/=/+1,Z+2,Z+nixRnmin表示求极小值；工是九维向量，X=(XpX2n)n是决策变量。这是为了叙述简便，实际上，根据具体应用和需求，X还可以是矩阵、多维数组或张量等，很多理论和算法可以相应地推广；/(x):即一脓称为目标函数(ObjeCtiVefunction);s.t是subjectto的简写，表示受限制于约束条件；cl(x):W1->脓(iEU/)称为约束函数(constraintfunctions).不等式约束G(%)O可以写成-CiQO有时候用九屋无)=0,iE,OjG)0,j/分别表示等式约束和不等式约束。集合D=xci(x)=0,iE-,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的最小(最大)值不一定存在，但是其下确界inf/、上确界SUPf总是存在的.因此当目标函数的最小(最大)值不存在时，我们便关心其下(上)确界，即将问题(1)中的,min(max)n改为,'inf(sup)'.如果S是一个有上界的实数集，那么存在一个最小的实数乂使得对于xS,%yo称为集合S的最小上界QeaStUPPerboUnd)或上确界(supremum),记为：SUPXeSCo或者supx:XES类似地，集合S的最大下界(greatestlowerbound)或下确界(idfimum)记为：infxes(x)或者infx:xES有限点集一定有一个最大值、最小值，此时最大值和上确界相同，最小值和下确界相同。某些无限点集可能不存在最大值或最小值。如-exp(-x)x>o,没有最大值，但有上确界为1(不可达)。WhensupCC,wesaythesupremumofCisattainedorachieved.例minxx<0,St<1,%R不存在最小值，但存在下确界(O).2 .优化问题存在最优解的条件邻域点XRn的邻域N£(工)=y脓7l:IIy-XII<£,其中，为某个正数。邻域也可视为半径为£、中心为X的球体。例如，在平面修中，点X=xit2V的邻域包含所有以X为中心的圆形内部的点。在脓3中，点X=xltX2tX3的邻域包含所有以X为中心的球体内部的点。球体在R2和R3中点X的邻域示意图如果集合S包含力的某个邻域，即X的某个邻域的所有点都属于S,那么点S称为集合S的内点。S的所有内点的集合称为S的内部(intS)。如果X的邻域既包含S中的点，也包含S外的点，那么称点X为集合S的边界点。注意S的边界点可能是S中的元素，也可能不是S中。S的所有边界点的集合称为S的边界(bdS或。S)。既不是内点，又不是边界点的点，称为外点。若对任意£>0均有Ng(x)nsw0,则称工属于集合S的闭包，记为Cis集合S的闭包ClS=SUdSl它是包含集合D的最小的闭集.如果集合S包含它的每个点的邻域，该集合是开集(OPenSet)°也就是说，如果S的每个点都是内点，或者S不包含任何边界点，那么S是开集。如果集合S包含S的所有边界点，那么称S是闭集(CIOSedset)。定理：一个集合是闭集当且仅当该集合的补是开集。Sl=xrX21:1<X1<2,1<X2<2Sl是开集S2=X1，X2】T：3WX14,1x22S2是闭集111«H012345例Isthesetopen,closed,orneither?Intervalsontherealline(0,+)open(8,0closed0,l)(8, ÷)空集notopen,notclosedopenandclosedopenandclosed unionofanynumberofopensetsisanopenset. theintersectionofafinitenumberofopensetsisopen. Unionsandintersectionsofclosedsetsareclosed. 连续函数的水平集和下水平集是闭集如果一个集合可以被一个有限半径的球体所包围，那么该集合称为有界集(boundedset)o如果一个集合既是闭集又是有界集，那么该集合称为紧集(ComPaetset)o能举出一个是闭集但不是紧集的例子吗？TakeanyboundedopensubsetSRn,thenRn×Sisclosedbutnotbounded.取S=(0,l)1R×S=S=(-,0U1,8)isaclosedbutunboundedset.紧集对于优化问题而言是非常重要的。魏尔斯特拉斯定理魏尔斯特拉斯定理(WeierStraSS定理)：假设fC-脓是一个连续函数，其中CU是紧集。那么，必定存在点X0。，使得对于所有的工。都有/(X0)/(%)。也就是说，/能够在C上取得极小值。定理给出了最优解的存在性条件，定义在紧集上的连续函数一定存在最大(最小)值点。但其对应的解可能不止一个.为了使可行域D为紧集，约束优化问题的约束条件取G(X)40,而不是G(X)<0。在许多实际问题中，定义域可能不是紧集，目标函数也不一定连续，因此需要将此定理推广来保证最优化问题解的存在性.例/(X)=/,%R定义域不是有界闭集广义实值函数数学分析中函数是从向量空间Rn到实数域R的映射，-8VQV+8,V脓。在最优化领域，经常涉及对某个函数取inf(sup)操作，这导致函数的取值可能为无穷。为了能够更方便地描述优化问题，我们需要对函数的定义进行某种扩展.def定义(广义实值函数,extendedreal-valuedfmction)令眩=Ru±为广义实数空间，则映射fn称为广义实值函数.从广义实值函数的定义可以看出，函数的定义域不包含±8,其值域多了两个特殊的值±,BP-,+.规定：<a<÷,R+Q=+,VaR(+)+(+)=+例InX的定义域是x>0,值域是(-8,+8),定义域中不含函数值趋近±8的点。广义实值函数InX的定义域是xo,值域是-8,+8),定义域中包含函数值趋近±8的点O适当函数适当函数是一类很重要的广义实值函数，很多最优化理论都是建立在适当函数之上的.定义(适当函数,Properfiinction)给定广义实值函数/和非空集合X.如果存在%使得fix')<+,并且对任意的%，都有/(X)>-,那么称函数f关于集合X是适当的.适当函数的值域是(-8,+8概括来说，适当函数f的特点是“至少有一处取值不为正无穷”，以及”处处取值不为负无穷”.对最优化问题minx(x),适当函数可以帮助去掉一些我们不感兴趣的函数，从而在一个比较合理的函数类中考虑最优化问题.我们约定：在本书中若无特殊说明，定理中所讨论的函数均为适当函数.对于适当函数/,规定其定义域dom=xI/(X)<+.正是因为适当函数的最小值不可能在函数值为无穷处取到，因此dom的定义方式是自然的.例/(X)=+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