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、2 - 的2i=l也就是构件轮廓曲线拟合问题可以通过极小值问题来描述.10min f (%o,yo,R) = Y (xi - x0)2 + ( - VoT - R22 oyoRJi=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,)

3、,则第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 脓(i E U /)称为约束函数(constraint functions)

4、.不等式约束 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不是可行方向在所有满足约束条件的决策变量中，使目标函

5、数取最小值的变量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 或者

6、supx: X E S类似地，集合S的最大下界(greatest lower bound)或下确界(idfimum)记为：infxes(x)或者 infx: x E S有限点集一定有一个最大值、最小值，此时最大值和上确界相同，最小值和下确界 相同。某些无限点集可能不存在最大值或最小值。如-exp(-x)xo,没有最大值，但有上确界为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的邻域

7、N(工)=y 脓7l: IIy-XII0均有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是闭集111H012345例Is the set open, closed

8、, 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. 连续函数的水平集和下水平集是闭集如果一

9、个集合可以被一个有限半径的球体所包围，那么该集合称为有界集 (bounded set)o如果一个集合既是闭集又是有界集，那么该集合称为紧集(ComPaet set)o能举出一个是闭集但不是紧集的例子吗？Take any bounded open subset SRn, then RnS is closed but not bounded.取 S = (0,l)1 RS =S = (-, 0 U 1,8)is a closed but unbounded set.紧集对于优化问题而言是非常重要的。魏尔斯特拉斯定理魏尔斯特拉斯定理(WeierStraSS定理)：假设f C -脓是一个连续函数，其中

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

11、这导致函数的取值可能为无 穷。为了能够更方便地描述优化问题，我们需要对函数的定义进行某种扩展. def定义(广义实值函数,extended real-valued fmction)令眩=R u 为广义实数空间，则映射fn称为广义实值函数.从广义实值函数的定义可以看出，函数的定义域不包含8,其值域多了两个特殊的值, BP-, +.规定： a 0,值域是(-8,+8),定义域中不含函数值趋近8的点。广义实值函数InX的定义域是xo,值域是-8,+8),定义域中包含函数值趋近8的点O适当函数适当函数是一类很重要的广义实值函数，很多最优化理论都是建立在适当函数之上的.定义(适当函数,Properfii

12、nction)给定广义实值函数/和非空集合X.如果存在% %使得fix) -,那么称函数f关 于集合X是适当的.适当函数的值域是(- 8,+8概括来说，适当函数f的特点是“至少有一处取值不为正无穷”，以及”处处取值不为 负无穷”.对最优化问题minx(x),适当函数可以帮助去掉一些我们不感兴趣的函数， 从而在一个比较合理的函数类中考虑最优化问题.我们约定：在本书中若无特殊说明， 定理中所讨论的函数均为适当函数.对于适当函数/,规定其定义域dom = x I/(X) (3):设(xk,yfc) epi且IimkT8%,打)=(刃，根据下半连续性和 极限定义，有/ HminV(Xk) % =?，这

13、等价于G乃W ePi即ep是 闭集.(3) = (1):取 Q下水平集的元素 xk Xf 注意到 3, Q) epi 且(xk, d) (x, a), 由epi f为闭集可知(工)epif,即/(x) .这说明了 /(%)的任意-下水平 集是闭集. =(2)：用反证法.反设存在序列SJ T式k T 8)但f() liminffeoo(xk), 取t使得f(x) t immff(xk).由下极限的定义，%lf(加)t中必定含有无穷多个Xk,不妨设乱)中存在子列 xfci使得/(%)且IimJ8为=E这显然与t下水平集为闭集矛盾.以上等价性为之后证明定理提供了很大的方便.在许多文献中闭函数和下半连

14、续函数 往往只出现一种定义.闭(下半连续)函数间的简单运算会保持原有性质：(1)加法：若/与g均为适当的闭(下半连续)函数，并且dom /ndomg 0,贝IJ f + g也是闭(下半连续)函数.在这里添加适当函数的条件是为了避免出现末定式 (-) + (+)的情况；(2)仿射映射的复合：若/为闭(下半连续)函数，则fAx + b)也为闭(下半连续) 函数；(3)取上确界：若每一个函数fa均为闭(下半连续)函数，则SUPa启Q)也为闭(下 半连续)函数.由于下半连续函数也具有某种连续性，有其相应的最小值存在定理.扩展的Weierstrass定理优化问题：mr(x) s.t. % X Rn(1)

15、定理(WeierStraSS定理)考虑一个适当且闭的函数fX (-8,+8,假设下面三 个条件中任意一个成立：def(1) dom/ = x Xf(x) +)是有界的；(2)存在一个常数使得下水平集Cy = x(x)y是非空且有界的；(3) f是强制函数，即对于任一满足IIxkII +的点列xu%,都有触O = +%那么，问题(1)的最小值点集%w%l() -.采用反证法.假设t = -,则存在点列”连IUC夕，使得limkoo(xk) = t = -.因为Cy的有 界性，点列与一定存在聚点，记为X-.根据上方图的闭性，我们知道Q*,t) epi,即有/Cr) t = -8.这与函数的适当性矛

16、盾，故t-8.利用上面的论述，我们知道*)t因为t是下确界，故必有0)=t这就证明 了下确界是可取得的.再根据定理2.2以及Cy的有界性，易知最小值点集是紧的.假设条件(1)成立，贝IJ dom是有界的.因为f是适当的，即存在qX使得 /(0) 0, i=l,，n其中kN O是风险容忍参数，它表示投资者对于风险的偏好.大胆的投资者会选择接近 于。的k值以获得更高的期望收益.该问题是典型的二次规划。如果希望最小化投资风险，且要求期望收益不低于事先指定的数r0,得到下面的 优化问题：minq(x) = xGxs. t.y 内Xi rQnW Xt = 1, Xi O,i = L ，几i=l这也是二次

17、规划C如果要求投资于第i种资产时上限是田，下限是灰，也可以不投资，则需要增加约束 条件：aiyi xi biyh yi(yi - 1)=0该问题是混合整数规划。例项目投资问题假定国家计划用于发展某种工业的总投资为b亿元，可供选择的项目共有n个.已知 第j个项目的投资为Q/亿元，可得收益为Cz亿元，问:应如何进行投资才能使盈利 率(即单位投资可得到的收益)为最高？解令决策变量为巧，则目标函数是要求盈利率/(x,x2,%n) = HvJ=1 ajXjXj 应满足约束条件：Xj(xj - 1) = O, ajXj b.该问题是整数规划C4.最优解的分类设集合D=x ci(x) = 0J E; Q(X

18、) 0,ix即是最优化问题的可行 域。若存在广 Di对任意XEDi不等式/(亡) /(x)成立，则称才是问题(1) 的全局极小解(或全局最优解,global minimum point).若存在x* Df对任意工 D,且X W x不等式/(/) 09 以及 丁 。的 6邻域 N3,6) = x I x-x-fxe D), 使得对任意xN(S),不等式/(x*)(x)成立，则称为问题(1)的局部极 小解(或局部最优解，local minimum point).若存在实数 0,以及 D 的 6-邻域 N3,6) =(X I x-rx D, 使得对任意xN(xd)x*,不等式f(广)V f(幻成立,

19、则称X*为问题(1)的严 格局部极小解(或严格局部最优解,strictly local minimum point).极小解(或最优解)有时也称为极小点(或最优点)，对应的函数值称为极小值(或 最优值).所有属于集合S并使得函数.心）达到最小值的元素X构成的集合记为argmin （x）: xSo。，亭nax表示arguments of maxima,最大值的参数，也就是“使得函数出现最 大值的参数argmax是自变量（参数）的集合，可能存在多个值。max是函数值的集合，最终只有一个值。例图最优解集图中给出了一维无约束优化问题最优解的例子，X1是（严格）全局最优解，1,X2和 X3是局部最优解，Xi和X3是严格局部最优解. 全局最优解一定是局部最优解 严格全局最优解一定是全局最优解，反之则不然. 严格局部最优解一定是局部最优解，反之则不然.尽管目前有许多求全局解的算法，但一般来说这是一个相当困难的任务.实际可行的 只是求一个局部（或严格局部）解，而非全局解求解优化问题通常是指求局部解， 仅当问题具有某种凸性时，局部解才是全局解。为了得到优化问题取得最优解的最优性条件，需要了解函数的相关性质.5.怎么学习最优化Geometric intuition mathematic manipulation Computer programming