《高级运筹学》约束非线性规划.ppt

约束非线性规划,高级运筹学教学课件,2015-10,本章内容 第一节 最优性条件 第二节 可行方向法 第三节 惩罚函数法 第四节 复形法,本章讨论如下的约束非线性规划问题,其中 f,gi,hj均为实值连续函数，且一般具有二阶连续偏导数。,求解一般约束非线性规划问题，比无约束问题和线性规划问题都要复杂得多。,x2,x*,o,1,1,可行域是一个三角形及其内部，目标函数等值线是以原点为圆心的同心圆。,最优解：,最优值,考虑问题,x1,线性规划的最优解总可以在可行域的顶点中找到，而顶点个数有限。,约束非线性规划问题的困难性：最优解不一定在顶点上；求解无约束问题的迭代法不能直接搬过来用。,例如：对于上面的问题，如果不存在约束，从任意初始点x(0)出发，沿f(x)的负梯度方向进行一维搜索，便求得极小点(0,0)T。有了约束，在进行一维搜索时，为了使求得的点是一个可行点，就必须对步长加以限制，这样，最远只能跑到边界上的一个点。,当所取的x(0)不在直线x1-x2=0上时，x(1)点就不会是最优解x*,因此还必须继续迭代下去找一个新的可行点，使目标函数取更小的值。,x(1),x(0),可是，沿f(x)在x(1)处的负梯度方向已经找不到可行点，因而梯度迭代已经不能继续进行，尽管离最优解还可能很远。,为了使迭代能继续下去，不仅要求搜索方向具有使目标函数下降的性质，而且要求在这个方向上有可行点。例如有一小段整个包含在可行域内，这样的方向称为可行方向。,设计求解约束非线性规划的迭代法，关键是在每个迭代点处构造一个下降可行方向。,求解约束非线性规划的另一个途径是：在某个近似解处，以已有较好解法的较为简单的问题近似代替原问题，用其最优解作为原来问题的新的近似解。如将目标函数及约束条件中的非线性函数分别以它们的一阶泰勒多项式或二阶泰勒多项式近似代替，或以一无约束非线性规划近似代替。,如何判断约束非线性规划的一个可行解是否为最优解？,第一节 最优性条件,一、等式约束极小化问题的最优性条件,考虑下面的约束优化问题,其中f,h 均为可微函数。,以上问题的几何意义：在曲面,上寻找函数 f(x1,x2,x3)的最小值。,（1）,设以上问题的最优解为,在曲面上任作一条通过点x*的光滑曲线,则必有,显然，限于曲线 l 上 x*亦是使f(x1,x2,x3)取极小值的点，即t*是一元函数F(t)=f(x1(t),x2(t),x3(t)的极小点,因此必有,即梯度f(x*)垂直于曲线l在点x*处的切线，由l的任意性知，f(x*)必垂直于在x*处的切平面方向。,由上面的分析知f(x*)和h(x*)必在同一直线方向上，即存在数*,满足,可以证明，对于一般等式约束问题,在最优解x*处，必存在数值(1*,2*,l*),使,为便于记忆，引进拉格朗日函数,（2）,定理1（等式约束问题最优解的一阶必要条件）,解（1）建立数学模型 取点A(x1,y1,z1),B(x2,y2,z2)，限制A在曲面上变化，B在平面上变化，则A、B 间距离S的最小值为解。问题的数学模型为：,其中已把距离S最小等价地替换成S2 最小，以简化目标函数。,（2）利用最优性条件求解,再加约束条件,由上述方程组解得,相应目标函数值为,由问题的几何意义知最优解肯定存在，又据必要条件仅此一个解，故以上所求即为最优解和最优值。,二、一般非线性规划的最优性条件,考虑问题,其中f,g1,g2均可微。,（3）,设 为（3）的最优解，且设,由于x*为区域(x1,x2,x3)|g2(x1,x2,x3)0的内点，所以，对于x*而言，约束g2(x1,x2,x3)0 实际并没有起作用。,称约束g1(x1,x2,x3)0为点x*处的有效约束。,于是x*实际上也是问题,（4）,的最优解，由定理1知，必有1*，使,为使形式整齐起见，引进2*=0，统一写成,（5）,（7）,（6）,从几何上看，(5)式的f(x*)和 g1(x*)都通过x*且应共线。实际上，由于x*是(4)的最优解，所以，当动点x由x*出发沿着g1(x)=0上的各个方向移动时，目标函数值f(x)均增加，不仅如此，而且 x由x*出发往g1(x)0的内部移动时（即下图所示箭头方向），f(x)也应增加。,x*,由于梯度指向函数值的增加方向，因此，f(x*)和g1(x*)不仅共线，而且应该是同方向的。即（6）中的,总之，(4)的最优解x*应满足条件(6)(7)(8),（8）,x*,g1(x*),f(x*),考虑一般不等式约束问题,不等式约束问题的K-T点的几何意义,对于一般约束非线性规划问题,（9）,构造拉格朗日函数,（10）,定理2（Kuhn-Tucher必要条件，简称K-T条件）对于非线性规划（9），若f,gi,hj 均可微且gi(x*),iI(x*),hj(x*),j=1,l线性无关，则x*为（9）的最优解的必要条件为：存在相应的拉格朗日乘子*和*使,（9）,K-T条件是多元函数取得约束极值的必要条件,可以用来作为约束极值的判断条件。,对于目标函数和约束函数都是凸函数的情况，符合K-T条件的点一定是全局最优点。这种情况K-T条件即为多元函数取得约束极值的充分必要条件。,满足K-T条件的可行点称为K-T点，最优性条件指在梯度线性无关的条件下，最优点必定是K-T点。,在实际应用中，很难验证所得的点是否为非线性规划的最优解，若能验证其是K-T点，就已经满足了。有时构造算法也是以得到K-T点为目标的。,例2 求以下非线性规划的K-T点,解：非线性规划的K-T条件为,再加上约束,（11）,（12）,（13）,（14）,（15）,（16）,解：,在x1=(2,1)T 点，I=1,2,且，g1(x1),g2(x1)线性无关。为使,成立，只要取,即可。所以，x1是K-T点。,在x2=(0,0)T 点，I=3,4,且，g3(x2),g4(x2)线性无关。为使,成立，只有取,由于30,40,所以，x2不是K-T点。,在最优解(0，0)T处，I=1,2，有效约束的梯度向量线性相关,解：最优解 x*=(0,0)T。,在x*=(1,1,1)T 点，I=1,例6：求解非线性规划问题,解：,K-T条件,不难求得,即x*=(1,0)T满足K-T条件。,因为f(x),g1(x),g2(x)为凸函数，且在x*可微，以定理3知，x*为全局最优解。,1.写出下列问题的K-T条件，并利用所得表达式求出它们的最优解,练习题,3.对于问题,写出K-T条件，并判断点 是否为K-T点。,（1）直接法 直接法是在满足约束的可行区域内直接搜索问题的最优解x*和最优值f(x*)。（2）间接法 间接法是将优化问题转化为一系列无约束优化问题来求解。,三、约束非线性规划问题的求解方法,直接解法思路:,步长,可行方向,可行方向的定义：设可行域DRn是非空集，xD.若对于某非零向量，d Rn,存在0，使对任意t(0,)均有x+td D,则称d为从x点出发的可行方向。,d 为可行方向d1不是可行方向,第二节 可行方向法,基本思想：在每一个迭代点处，寻找一个下降可行方向，沿下降可行方向进行一维搜索。,如何寻找可行方向？,可行方向：设可行域DRn是非空集，xD.若对于某非零向量，d Rn,存在0，使对任意t(0,)均有x+td D,则称d为从点x出发的可行方向。,例7 在由约束,所确定的可行域内，任求一个在点x=(0,1,2,3)T处的可行方向。,解：首先检查在点x处哪些约束为有效约束，经检查，约束（1）（2）（3）和x10为有效约束。设所求可行方向为,根据可行方向的定义，应存在，使对任意 t(0,)有,也能满足所有有效约束，即,整理得,满足上述不等式的 均为可行方向。,现只求一个可行方向，可令不等号改为等号，求解,得,为使d10，可取d3=1得一可行方向,利用可行方向的概念，典型的策略是：由可行点x(k)出发，找一下降可行方向d(k)作搜索方向，然后确定沿此方向移动的步长，得下一迭代点x(k+1).这类方法称可行方向法。搜索方向的选择方式不同就形成不同的可行方向法。,Zoutendijk可行方向法,考虑,(1),上述问题的约束是线性的，仅目标函数是非线性的，在迭代点x(k)附近，可以用f(x)的一阶泰勒展开式近似代替f(x).假设x(k)满足,于是得到线性规划,(2),注意到d=0为上述线性规划(2)的可行点，其对应的目标函数值为0，所以若d*为问题(2)的最优解，则,(2),(1),Zoutendijk可行方向法的具体步骤,任选可行点x(0)作初始点，令k=0;,2.根据x(k)的有效约束把A分解为A1，A2，相应地把b分解为b1,b2,使,3.求解线性规划,设其最优解为d(k)。,解：取x(0)=(0,2)T,注意,在x(0)点，有效约束仅x10一个，故A2=(1,0),b2=0.,设所求的下降可行方向d(0)=(d1,d2)T,其相应的线性规划为,求得最优解 d(0)=(0,-1)T.因,还需继续迭代。,求搜索区间。计算,在t0,4/5中求,作第二次迭代,关于x(1)的有效约束为,求得最优解 d(1)=(2/3,-1)T.因,还需继续迭代。,在t0,3/5中求,作第三次迭代,关于x(2)的有效约束为,还需继续迭代。,求得最优解 d(2)=(1,-1)T.因,在t0,3/5中求,作第四次迭代,关于x(3)的有效约束为,求解得,即得本题的最优解为,由于,用Zoutendijk可行方向法解下列问题,（1）,取初始点 x(1)=(0,0)T,（2）,取初始点 x(1)=(2,0)T,（3）,取初始点 x(1)=(1,2)T,第三节 惩罚函数法,基本思想：通过构造罚函数把约束优化问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。又称为序列无约束最小化方法。,考虑一般约束非线性规划问题,根据约束的特点，构造某种“惩罚”项，然后把它加到目标函数中去，使得约束问题的求解，转化成一系列无约束问题的求解。,“惩罚”策略：对于无约束问题求解过程中企图违反约束的那些迭代点，给以很大的目标函数值，迫使这一系列无约束问题的极小点或者不断的向可行域靠近，或者一直保持在可行域内部移动，直到收敛于原约束问题的极小点。,常用的惩罚函数法有三种：,一、外部惩罚函数法（外点法）对违反约束的点在目标函数中加入相应的“惩罚”，而对可行点不予惩罚。此法的迭代点一般在可行域外部移动。二、内部惩罚函数法（内点法）对企图从内部穿越可行域边界的点在目标函数中加入相应的“障碍”，距边界越近，障碍越大，在边界上给以无穷大的障碍，从而保障迭代一直在可行域内部移动。三、乘子法 在拉格朗日函数中加入相应的惩罚。,一、外点法,基本原理：外点法是从可行域的外部构造一个极小点序列去逼近原约束问题的最优解。,对于等式约束问题：,定义辅助函数,参数是很大的正数。,（1）,（2）,当求解无约束问题,（3）,得到的最优解x*，满足 hj(x*)=0,j=1,2,l 时，显然x*就是原问题(1)的最优解。,在求解问题(3)的过程中，若x(k)不满足 hj(x(k)=0,则(2)中第二项将是很大的正数，限制它成为极小点，以迫使无约束问题(3)的最优解满足（或接近满足）hj(x)=0(j=1,2,l).可见，求解问题(3)能够得到问题(1)的近似解。,对于不等式约束问题,构造辅助函数,这样可以将问题（4）转化为无约束问题,（4）,（5）,（6）,对于一般约束问题,可以定义辅助函数,这样约束问题（7）转化为无约束问题,（7）,（8）,（9）,其中,，1，通常取=2,（10）,（9）,（10）,（7）,当x为问题(7)的可行点时，P(x)=0，从而F(x,)=f(x);当x 不是问题(7)的可行点时，P(x)是很大的正数，可视为对x脱离可行域的一种惩罚，其作用是在极小化问题(10)的过程中迫使迭代点靠近问题(7)的可行域。因此，求解问题(10)能得到问题(7)的近似解，而且越大，近似程度越好。通常将P(x)称为惩罚项，称为惩罚因子，F(x,)称为惩罚函数。,例9 求解非线性规划问题,解：定义罚函数,用解析法求解minF(x,)，有,x*恰为所求非线性规划问题的最优解,用此法求得的无约束问题最优解往往是不满足约束条件的，它是从可行域外部，随着的增大而趋于x*的，故称此法为外点法。,惩罚因子 的选择策略：选取一个趋于无穷大的严格递增正数列k，逐个求解,而得到一个极小点序列xk*，在适当条件下，这个序列将收敛于约束问题的最优解。,通过一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法，简称SUMT方法(Sequential Unconstrained Minimization Techniques),外点法的计算步骤,给定初始点x(0)，初始惩罚因子1，放大系数c1,允许误差 0；2.以x(k-1)为初始点，求解无约束问题,设其极小点为x(k)；,若kP(x(k)，则停；得近似解x(k)；否则，令 k+1=ck,k=k+1,转2。,例10 求解下列非线性规划问题,给定初始惩罚因子1=1,放大系数c=10.,解：构造惩罚函数,用解析法求 minF(x,k)的最优解,验证可行域：x*=2,f(x*)=4,例11 用外点法求解下列问题,解：首先构造惩罚函数,D1,D3,D2,D4,根据极值的必要条件 F(x,k)=0，当xD1、D2、D3时均推出矛盾。当x D4时，可以求得无约束优化问题的最优解序列为,当惩罚因子k渐增时，由下表可以看出收敛情况,习题：用外点法求解下列问题,二、内点法,这种方法将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近约束边界上的最优点。内点法只能用来求解具有不等式约束的优化问题。,将可行域记为,保持迭代点含于D内的方法是定义障碍函数,其中惩罚项B(x)是连续函数，当点x在可行域内趋向D的边界时,B(x)的两种重要形式是：,r是很小的正数。,当x趋向边界时，G(x,r)+;否则，由于r很小，G(x,r)f(x).,因此，可以通过求解问题,得到问题,的近似最优解。,由于B(x)的存在，在D的边界形成“围墙”，因此问题（1）从D的内部出发的迭代点必在D的内部。正由于B(x)的阻挡作用，使xD自动满足，故问题（1）实质上是一个无约束问题。根据G(x,r)的定义，显然r越小，问题(1)的解越接近于问题(2)。,（1）,（2）,在实际计算中，也是采用序列无约束极小化的方法(SUMT),取一个严格单调减少且趋于零的惩罚因子（障碍因子）数列rk，对每个rk,从D内部出发，求解,内点法的具体步骤,1.给定初始点x(0)intD,允许误差0，初始参数r10,缩小系数(0,1),k=1。,2.以x(k-1)为初始点，求解问题,设求得极小点为x(k)；,3.若rkB(x(k)，则停，得近似解x(k)；否则，令rk+1=rk,k=k+1,回2。,例12 用内点法求解,解：首先构造内点罚函数（障碍函数）,用解析法求解,根据极值存在的必要条件得,求解得,考虑约束 x1-10,应舍去。,无约束问题的极值点为,取r1=4,=0.3 得,x(r1),x(r2),最优点图解,例13 用内点法求解,定义障碍函数,用解析法求解,令,解得,内点法注意事项：1.初始点选取：尽量选择离约束边界较远的可行点 可以采用随机生成的方法产生2.惩罚因子r初值的选取：过大：迭代次数多 太小：惩罚函数形态恶劣 通常选取初始惩罚因子为150 之间的数3.缩小系数 通常选取：0.10.7 之间的数,例14 用内点法求解,解：构造障碍函数,用解析法求解,根据极值存在的必要条件得,解得,内点法和外点法的简单比较,内点法的特点：（1）初始点必须为严格内点（2）不适于具有等式约束的优化问题（3）迭代过程中各个点均为可行解（4）初始罚因子要选择得当（5）罚因子递减(0)，递减率有01,外点法的特点：（1）初始点可以任选（2）对等式约束和不等式约束均可适用（3）仅最优解为可行解（4）初始罚因子要选择得当（5）罚因子递增()，递增率有1,外点法和内点法使用序列无约束极小化技巧，方法简单，使用方便，并且能用来求解目标函数和约束函数导数不存在的问题，因此，这种算法得到了广泛的应用。固有缺点：随着惩罚因子趋向其极限，惩罚函数的Hessen矩阵的条件数无限增大，因而越来越变得病态。惩罚函数的这种性态给无约束极小化带来很大的困难。为了克服这个困难，Hestenes和Powell于1969年各自独立地提出了乘子法。,练习：用内点法求解下列问题,三、乘子法,1.等式约束的情形,考虑问题,其中f,hj(j=1,2,l)为二次连续可微函数，xRn,运用乘子法，需要定义增广拉格朗日函数（乘子惩罚函数）,其中,乘子惩罚函数(x,)与拉格朗日函数的区别在于增加了惩罚项,与惩罚函数的区别在于增加了乘子项,这种区别使得增广拉格朗日函数与拉格朗日函数及惩罚函数具有不同的性态。对于(x,)，只要取足够大 的惩罚因子，不必趋向无穷大，就可以通过极小化(x,)求得原问题的局部最优解。,（1）,若x*是问题(1)的局部最优解，*是相应的最优拉格朗日乘子，且对每个满足dThj(x*)=0(j=1,2,l)的非零向量d，均有二阶充分条件成立，即,则存在00,使得对所有 0,x*是(x,*,)的严格局部极小点。,根据上述结论，如果知道最优乘子*，那么只要取充分大的惩罚因子，不需趋向无穷大，就能通过极小化(x,*,)求出问题（1）的解。,问题：如何确定最优乘子*？,方法:先给定充分大的和拉格朗日乘子的初始估计，然后在迭代过程中修正，力图使趋向*。,修正的迭代公式：,如果(k)不收敛，或者收敛太慢，则增大参数，再进行迭代。收敛快慢的衡量标准,乘子法的计算步骤,例15用乘子法求解,解：构造广义拉格朗日函数（乘子惩罚函数）,修正，得,再解,得,如此继续，一般地，在第k次迭代时，(x,(k),2)的极小点为,将的递推公式展开得,非线性规划问题的最优乘子和最优解分别为,2.不等式约束的情形,对于只有不等式约束的问题,利用等式约束的结果，引入变量yi,把(2)化为等式约束问题,（2）,定义增广拉格朗日函数,从而把问题（2）转化为求解,（2）,为此，将,变形得,将,代入,可以消去yi，因此定义增广拉格朗日函数,从而将问题（2）转化为无约束问题,对于既含不等式又含等式约束的问题,定义增广拉格朗日函数,以充分大的参数，并通过下列公式对迭代过程中的乘子进行修正。,计算步骤与等式约束相同。,例16 问题,的最优解为x*=(0.25,0.75)T,分别用惩罚函数法和乘子法求它的迭代点列。,解：1.惩罚函数法，对于,可求得最优解为,2.乘子法，对于,可求得最优解为,所得迭代点列见下表,由上表可见，用乘子法迭代6次就达到惩罚函数法迭代15次的效果。惩罚因子在惩罚函数法中要增大到15=3276.8,而在乘子法中只要增大到6=6.4.因此乘子法不需过分增大惩罚因子，因此，乘子法比惩罚函数法有效。,第四节 复形法,无论是无约束最优化还是约束最优化问题，前面介绍的方法均是利用梯度作为工具的。在实际应用中还有一类方法，它在迭代时仅仅涉及目标函数及约束函数的函数值计算。复形法是求解约束非线性最优化问题的一种重要的直接方法。复形法既可以用于无约束最优化问题，也可以用于约束最优化问题。,引例 求解,基本思想：在可行域内构造一个具有k(kn+1)个顶点的初始复形。对该复形各顶点的目标函数值进行比较，找到目标函数值最大的顶点(称最坏点)，然后按一定的法则求出目标函数值有所下降的新可行点，并用此点代替最坏点，构成新的复形，复形的形状每改变一次，就向最优点移动一步，直至逼近最优点。,在可行域内随机选取k个点构成初始复形。找出坏点x(l)。,求x(l)关于x(0)的倍反射点x()=x(0)+(x(0)-x(l),x()为反射点，=1.3。,计算除最坏点以外的其余点的中点为x(0)。,在迭代过程中，若反射点不满足可行性和适用性，将反射系数减小，重新求x()，使它满足可行性和适用性。,复形的顶点k通常取n+1k2n个。方法1：设计者确定；方法2：随机产生：1、产生k个随机点 xi=ai+i(bi-ai)i=1,2,.,ni为(0，1)区间内产生的均匀分布的随机数，需要n个随机数产生一个点 x(1)。同样，产生其它的随机点x(2)、x(3)、x(K)。,初始复形的构成,2、将非可行点调入可行域判断产生的k个随机点是否在可行域内，并重新排列，将可行点依次排在前面，如有q个顶点x(1)、x(2)、x(q)是可行点，其它k-q个为非可行点。对x(q+1)，将其调入可行域的步骤是：,（1）计算q个点集的中心x(s)；（2）将第q+1点朝着点x(s)的方向移动，按下式产生新的x(q+1)，即 x(q+1)=x(s)+0.5(x(q+1)x(s),这个新点x(q+1)实际就是x(s)与原x(q+1)两点连线的中点，如图。若新的x(q+1)点仍为非可行点，按上式再产生x(q+1)，使它更向x(s)靠拢，最终使其成为可行点。按照这个方法，同样使x(q+2)、x(q+3)、x(K)都变为可行点，这k个点就构成了初始复形,例17 求解约束非线性规划问题,随机产生点(2,0)T,(0,2)T,(3,3)T.说明调入可行域的过程。,复形法的计算步骤,构成初始复形2.形成反射点 计算各点的目标函数值，比较出最坏的点x(l),即,3.检查可行性,4.形成新的复形,5.返回2。,常用的停机准则有如下两种,1.在第二步中，若,则停机。,2.在第四步中，若,则停机，停机时所得到的最好点即作为所求的近似最优点。,例19 用复形法求解,解：任取k=4个点构成初始复形,分别计算相应的函数值,比较得最坏点,计算由x(1),x(2),x(3)构成的三角形的形心。,计算x(4)关于x(0)的反射点（取=1）和相应函数值,比较出最坏点x(l)=(5,6)T,计算由(3,5)T,(4,7)T,(2,9)T构成的三角形形心,计算(5,6)T关于(3,7)T的反射点和相应函数值,继续迭代可以求出满足精度要求的近似最优解。,例20 用复形法求解下列约束最优化问题,解:(1)任取k=4个点构成初始复形,验证满足约束条件。,(2)计算函数值，找出最坏点,比较得最坏点,(3)计算其余各点的形心,(4)检查形心的可行性,(5)求反射点并检查可行性（取=1.3）,经验证，反射点满足约束条件。,(6)比较反射点与坏点的目标函数值,替换坏点，构成新复形：,进行第二轮迭代，找出坏点,（要求学生接着做）,（1）复形法是求解约束非线性最优化问题的一种直接方法，仅通过选取各顶点并比较各点处函数值的大小，就可寻找下一步的探索方向。但复形各顶点的选择和替换，不仅要满足目标函数值下降的要求，还应当满足所有的约束条件。（2）复形法适用于仅含不等式约束的问题。,复形法的特点：,练习题：用复形法求解下列约束非线性规划问题,（1）,初始复形顶点取：(2,1)T；(4,1)T；(3,3)T；,（2）,