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)都不是适当函数。闭函数闭函数是另一类重要的广义实值函数，后面许多定理都建立在闭函数之上.在数学分析 课程中我们接触过连续函数，本小节介绍的闭函数可以看成是连续函数的一种推广.在 介绍闭函数之前，先引入一些基本概念.下水平集是描述实值函数取值情况的一个重要概念.定义(。下水平集，sub-level set)对于广义实值函数/： Kn Ca = x f(x) a称为f的下水平集.在最优化问题中，多数情况都要对函数/(X)求极小值，通过研究。下水平集可以知 道具体在哪些点处/(X)的值不超过Q.若Ca非空，就知道/(X)的全局极小点(若 存在)一定落在Ca中，因此也就无需考虑Ca之外的点。上方图是从集合的角度来描述一个函数的具体性质.定义(上方图,epigraph)对于广义实值函数广即T曲，epi = (x, t) Rn+1 1/(*) t称为/的上方图.图2.2函数f和其上方图epi f上方图将函数和集合建立了联系，/的很多性质都可以在epi上得到体现.在后面的 分析中将看到，可以通过epi /的一些性质来反推f的性质.定义(闭函数,closedfunction)设f:Rn R为广义实值函数，若epi f为闭集， 则称/为闭函数.定义(下半连续函数JOWerSemicontiniiity)设广义实值函数f: W1 S,若对任意 的 眩n,有limmf(y) fx,则/(x)为下半连续函数.如图2.3所示，f(x)为脓上的下半连续函数.图2.3下半连续函数/(x)有趣的是，虽然表面上看这两种函数的定义方式截然不同，但闭函数和下半连续函数是 等价的.定理(闭函数和下半连续函数的等价性)设广义实值函数/:DrTR则以下命题等价：(1) f(x)的任意W下水平集都是闭集；(2) /(x)是下半连续的；(3)/(%)是闭函数.证明.(2)=>(3):设(xk,yfc) epi且IimkT8%,打)=(£刃，根据下半连续性和 极限定义，有/ HminV(Xk) % =?，这等价于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下水平集为闭集矛盾.以上等价性为之后证明定理提供了很大的方便.在许多文献中闭函数和下半连续函数 往往只出现一种定义.闭(下半连续)函数间的简单运算会保持原有性质：(1)加法：若/与g均为适当的闭(下半连续)函数，并且dom /ndomg 0,贝IJ f + g也是闭(下半连续)函数.在这里添加适当函数的条件是为了避免出现末定式 (-) + (+)的情况；(2)仿射映射的复合：若/为闭(下半连续)函数，则fAx + b)也为闭(下半连续) 函数；(3)取上确界：若每一个函数fa均为闭(下半连续)函数，则SUPa启Q)也为闭(下 半连续)函数.由于下半连续函数也具有某种连续性，有其相应的最小值存在定理.扩展的Weierstrass定理优化问题：mr(x) s.t. % X Rn(1)定理(WeierStraSS定理)考虑一个适当且闭的函数fX (-8,+8,假设下面三 个条件中任意一个成立：def(1) dom/ = x Xf(x) < +)是有界的；(2)存在一个常数使得下水平集Cy = x(x)y是非空且有界的；(3) f是强制函数，即对于任一满足IIxkII +的点列x"u%,都有触O = +%那么，问题(1)的最小值点集%w%l()<(y),vy%是非空且紧的.证明.假设条件(2)成立.我们先证下确界t = infxe(%) > -.采用反证法.假设t = -,则存在点列”连IUC夕，使得limkoo(xk) = t = -.因为Cy的有 界性，点列与一定存在聚点，记为X-.根据上方图的闭性，我们知道Q*,t) epi,即有/Cr) t = -8.这与函数的适当性矛盾，故t>-8.利用上面的论述，我们知道*)t因为t是下确界，故必有0")=t这就证明 了下确界是可取得的.再根据定理2.2以及Cy的有界性，易知最小值点集是紧的.假设条件(1)成立，贝IJ dom是有界的.因为f是适当的，即存在qX使得 /(0) < +令r = (),则下水平集c?是非空有界的，那么利用条件(2)的结 论，可知问题(1)的最小值点集是非空且紧的.假设条件(3)成立.我们沿用上面定义的X0,Y = /(X0)以及下水平集因为/ 是强制的，则Cy是非空有界的(假设无界，则存在点列%" U Cy满足 IimkT8ll%"Il =+8,由强制性有 limk0(xk) = +,这与 /(x) 矛盾)，即推出条件(2). 定理的三个条件在本质上都是保证/(X)的最小值不能在无穷远处取到，因此可以仅在 一个有界的下水平集中考虑/(X)的最小值.同时要求/(X)为适当且闭的函数，并不 需要/W的连续性.因此定理比数学分析中的WeierStraSS定理应用范围更广.定理给出了最优解的存在性条件，但其对应的解可能不止一个.例/(x) = x2,x 无=脓定义域不是有界闭集，但是强制函数，其全局最优解一定存 在.对于适当且闭的函数/(x) = e-xX = R,它不满足定理三个条件中任意一个，因 此不能断言其全局极小值点存在.事实上，其全局极小值点不存在.3.最优化问题的分类https:neos-guide.org/guide/types/根据可行域D对最优化问题进行分类：若D = RI即元是自由变量，取值没有限制，则称为无约束优化问题(或简称为 无约束优化)，即没有约束条件限制；可行方向是任意的n维向量，即FD(X) = R'若。UR%称为约束优化问题(或简称为约束优化).无约束优化是最优化问题的基础，许多实际问题本身就是无约束问题；一些约束 优化问题往往需要将问题本身转化为无约束优化问题来求解.无约束优化的数学模型简记为喇或 minf(x)x Rn, minf(x)其中X=(Xl,%2,/I)TWnvI为决策变量，f：DVIT脓是目标函数.若最优化问题是求最大值，即max /(x)的形式，可利用max/= -min(-f)等价转化为求最小值的形式. 根据函数的凸性划分如果目标函数是凸函数，可行域是凸集，则成为凸优化问题.如果其中有一个或者两者都不是凸的，那么相应的最小化问题是非凸优化问题.若问题(1)中的min改为max,且目标函数和可行域分别为凹函数和凸集，这样 的问题也称为凸优化问题.因为对凹函数求极大等价于对其相反数(凸函数)求极 小. 根据函数的线性划分若目标函数和约束函数都是线性的，则称为线性规划(LP)；若目标函数和约束函数中至少有一个是非线性的，则称为非线性规划(NLP)。若目标函数是二次函数，约束函数Q(%)(i EU/)是线性函数，则称为二次规划. 根据可行域的性质划分若可行域含有无穷多个点，且可行域内的点可以连续变化，则称为连续最优化问 题.根据连续最优化问题中函数是否连续可微，连续最优化问题又可分为：光滑最优化问题：问题中目标函数与约束函数均连续可微；非光滑最优化问题：问题中只要有一个函数不是连续可微的该问题即为非光滑最 优化问题若可行域内点的个数是有限的，则称为离散最优化问题；对于离散优化问题，若变量均为整数，则称其为整数规划(IP)问题；若部分变量 为整数，而另一部分变量连续变化，则称其为混合整数规划(MlP)问题。离散优化中的主要问题是当决策变量的维度过大时会产生组合爆炸，因此一般采 用采样法求解。 根据函数的向量性质划分若目标函数为向量函数，则称为多目标规划问题；若目标函数为数量函数，则称为单目标规划问题。根据有关信息的确定性划分如果目标函数和可行域都是确定的，则这样的规划问题称为确定性规划问题若目标函数或约束函数具有随机性，也就是问题的表述形式随时间的变化而变 化，具有不确定性，则这样的优化问题称为随机规划；动态优化(DynamiC Optimization): The degrees of freedom are functions of time. Since time is continuous, this means we have infinite degrees of freedom.例 OPtimal Motion Planning of RobotsShort cycle time for production, e.g., minimization of transportation time through optimal motion planning, 要求 Correct positioning of the part during assembly, No collisions during movement如果优化问题的变量(函数)具有模糊性，则这样的优化问题称为模糊规划；主要讨论非线性、连续、单目标、确定性规划问题。例投资组合优化问题1952年MarkoWitZ提出以收益率的方差作为风险的度量标准，建立了极小化风险的投 资组合模型，为现代投资理论奠定了基础。假设有一笔资金，准备投资于几种资产.已知第i种资产的收益率为, i = l,儿 因为投资收益是不确定的，假定收益率是遵循正态分布的随机变量，第i种资产收益率 的期望值为出=E,方差为f = E( -i)2.设每种资产占总资产的比例为阳(i = 1,E),k左=1, X=(无1，,今)T为一个投资 组合(PortfOli0).投资组合的收益率为Rp = 1rixh其期望值与方差分别为E(RP) = E(W Mi) = W E(rM = 7Xi=I / Z=IEKRp-E(RP)升内Xi，n/ (G-出)项 i=ln n=WW E® _ 出)(少一)xixJ = MrGxi=l ;=1其中G是收益率之间的协方差矩阵，其元素为Gu = pgj,这里Plj为Pii是投资收益率与的相关系数，当Plj接近于1时，rl增加，也倾向于增 加；当Pij接近于一1时，增加，q倾向于减少.为使期望收益尽量大而风险(投资组合收益率的方差)尽量小，将这两项结合作为目标函 数.得到下面的优化问题：min q(x) = kx Gx rx,s.t.Hi=lx( = 1,4>0, i=l,，n其中kN O是风险容忍参数，它表示投资者对于风险的偏好.大胆的投资者会选择接近 于。的k值以获得更高的期望收益.该问题是典型的二次规划。如果希望最小化投资风险，且要求期望收益不低于事先指定的数r0,得到下面的 优化问题：minq(x) = xGxs. t.y 内Xi > rQ>nW Xt = 1, Xi > O,i = L ，几i=l这也是二次规划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) 0,ix即是最优化问题的可行 域。若存在广 Di对任意XEDi不等式/(亡) /(x)成立，则称才是问题(1) 的全局极小解(或全局最优解,global minimum point).若存在x* Df对任意工 D,且X W x不等式/(/) < /(X)成立，则称X*为 问题(1)的严格全局极小解(或严格全局最优解,StricHyglobalminiimnn point).若存在实数 >09 以及 丁 。的 6邻域 N3,6) = x I x-x-<fxe D), 使得对任意xN(S),不等式/(x*)(x)成立，则称为问题(1)的局部极 小解(或局部最优解，local minimum point).若存在实数 <5>0,以及 £ D 的 6-邻域 N3,6) =(X I x-r<x D, 使得对任意xN(xd)x*,不等式f(广)V f(幻成立,则称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