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也就是构件轮廓曲线拟合问题可以通过极小值问题来描述.10min f (%o,yo,R) = Y (xi - x0)2 + (¾ - VoT - R22 o>yo>RJi=l这里隐含着约束条件R 0,对问题的求解影响不大。例(厂址选择问题)设有几个市场，第/个市场位置为(p,q),它对某种货物的需求量为bj(j = l,-,n).现计划建立m个仓库，第i个仓库的存储容量为ai(i= l,m).试确定仓库 的位置，使各仓库对各市场的运输量与路程乘积之和为最小.解设第i个仓库的位置为(%i,%)(i = L,m),第i个仓库到第j个市场的货 物供应量为Zija = I,m;j = 1,),则第i个仓库到第j个市场的距离为4/=1(勺一口)2 + (% )2,目标函数为m nm nJZOaj= 2 2 ZljJ(Xi- Pj)2 + (% - qj)2i=l J=Ii=l J=I约束条件如下：(1)每个仓库向各市场提供的货物量之和不能超过它的存储容量；(2)每个市场从各仓库得到的货物量之和应等于它的需求量；(3)运输量不能为负数.因此，该问题的数学模型为m nm n min f(x)=W %djj = W W ZijJ(Xi- Pj)2 + (% - %)2i=l yli=l j=ls.L罟=IZtj <saiti = l,m,况i ZIj = bj,j = lf-,n,Zij OJ = 1,m;j = 1,，n最优化问题数学模型的一般形式min /(x)S. t.G(%) = 0,iE = l,2,1,G(%) O, i / = / + 1, Z + 2, , Z + nix Rnmin表示求极小值；工是九维向量，X=(XpX2n)n是决策变量。这是为了叙述简便，实际 上，根据具体应用和需求，X还可以是矩阵、多维数组或张量等，很多理论和算法可以 相应地推广；/(x):即一脓 称为目标函数(ObjeCtiVefunction);s.t是subject to的简写，表示受限制于约束条件；cl(x): W1 -> 脓(i E U /)称为约束函数(constraint functions).不等式约束 G(%) O可以写成-CiQO 有时候用九屋无)=0,i E, OjG) 0,j /分别表示 等式约束和不等式约束。集合 D = x ci(x) = 0,i E-, ci(x) 0,i /;% Rn Dvl称为问题(1)的可行域 (Feasible domain) o若 x W D,则称 X 为可行点(FeaSibleSOhltiOi1).设亢 D,对于OH d Rni如果存在>0,使得x + dED, 6 0,贝IJ 称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是一个有上界的实数集，那么存在一个最小的实数乂使得对于x S, % y o称为集合S的最小上界QeaStUPPerboUnd)或上确界(supremum),记为：SUPXeS Co 或者 supx: X E S类似地，集合S的最大下界(greatest lower bound)或下确界(idfimum)记为：infxes(x)或者 infx: x E S有限点集一定有一个最大值、最小值，此时最大值和上确界相同，最小值和下确界 相同。某些无限点集可能不存在最大值或最小值。如-exp(-x)x>o,没有最大值，但有上确界为1 (不可达)。When supC C, we say the supremum of C is attained or achieved.例 min xx < 0,S t < 1, % R不存在最小值，但存在下确界(O).2 .优化问题存在最优解的条件邻域点X Rn的邻域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是闭集(CIOSed set)。定理：一个集合是闭集当且仅当该集合的补是开集。Sl = xrX21: 1 <X1 < 2,1 <X2 < 2Sl是开集S2=X1，X2】T：3WX1 4,1x2 2S2是闭集111«H012345例Is the set open, closed, or neither? Intervals on the real line(0, +)open(8,0closed0,l)(8, ÷)空集not open, not closedopen and closedopen and closed union of any number of open sets is an open set. the intersection of a finite number of open sets is open. Unions and intersections of closed sets are closed. 连续函数的水平集和下水平集是闭集如果一个集合可以被一个有限半径的球体所包围，那么该集合称为有界集 (bounded set)o如果一个集合既是闭集又是有界集，那么该集合称为紧集(ComPaet set)o能举出一个是闭集但不是紧集的例子吗？Take any bounded open subset SRn, then Rn×S is closed but not bounded.取 S = (0,l)1 R×S =S = (-, 0 U 1,8)is a closed but unbounded set.紧集对于优化问题而言是非常重要的。魏尔斯特拉斯定理魏尔斯特拉斯定理(WeierStraSS定理)：假设f C -脓是一个连续函数，其中CU 是紧集。那么，必定存在点X0 。，使得对于所有的工。都有/(X0) /(%)。也就是说，/能够在C上取得极小值。定理给出了最优解的存在性条件，定义在紧集上的连续函数一定存在最大(最小)值 点。但其对应的解可能不止一个.为了使可行域D为紧集，约束优化问题的约束条件取G(X)40,而不是G(X) <0。在许多实际问题中，定义域可能不是紧集，目标函数也不一定连续，因此需要将此定 理推广来保证最优化问题解的存在性.例/(X) = /,% R定义域不是有界闭集广义实值函数数学分析中函数是从向量空间Rn到实数域R的映射，-8VQV+8, V脓。在最优化领域，经常涉及对某个函数取inf (sup)操作，这导致函数的取值可能为无 穷。为了能够更方便地描述优化问题，我们需要对函数的定义进行某种扩展. def定义(广义实值函数,extended real-valued fmction)令眩=R u ±为广义实数空间，则映射fn称为广义实值函数.从广义实值函数的定义可以看出，函数的定义域不包含±8,其值域多了两个特殊的值±, BP-, +.规定： < a < ÷, R+ + Q = +,Va R(+) + (+) = +例InX的定义域是x>0,值域是(-8,+8),定义域中不含函数值趋近±8的点。广义实值函数InX的定义域是xo,值域是-8,+8),定义域中包含函数值趋近±8的点O适当函数适当函数是一类很重要的广义实值函数，很多最优化理论都是建立在适当函数之上的.定义(适当函数,Properfiinction)给定广义实值函数/和非空集合X.如果存在% %使得fix') < +,并且对任意的 %，都有/(X) > -,那么称函数f关 于集合X是适当的.适当函数的值域是(- 8,+8概括来说，适当函数f的特点是“至少有一处取值不为正无穷”，以及”处处取值不为 负无穷”.对最优化问题minx(x),适当函数可以帮助去掉一些我们不感兴趣的函数， 从而在一个比较合理的函数类中考虑最优化问题.我们约定：在本书中若无特殊说明， 定理中所讨论的函数均为适当函数.对于适当函数/,规定其定义域dom = x I/(X) < +.正是因为适当函数的最小值不可能在函数值为无穷处取到，因此dom的定义方式是 自然的.例/(X) = +8、/(x) = Inx (x 0)都不是适当函数。闭函数闭函数是另一类重要的广义实值函数，后面许多定理都建立在闭函数之上.在数学分析 课程中我们接触过连续函数，本小节介绍的闭函
