《《高级运筹学》约束非线性规划》由会员分享，可在线阅读，更多相关《《高级运筹学》约束非线性规划（149页珍藏版）》请在金锄头文库上搜索。
1、约束非线性规划高级运筹学高级运筹学教学课件教学课件2015-10本章内容本章内容 第一节 最优性条件 第二节 可行方向法 第三节 惩罚函数法 第四节 复形法本章讨论如下的约束非线性规划问题本章讨论如下的约束非线性规划问题其中 f, gi,hj均为实值连续函数，且一般具有二阶连续偏导数。求解一般约束非线性规划问题，比无约束问题和线性规划问题都要复杂得多。x2x*o11可行域是一个三角形及其内部，目标函数等值线是以原点为圆心的同心圆。最优解：最优值考虑问题x1 线性规划的最优解总可以在可行域的顶点中找到，而顶点个数有限。 约束非线性规划问题的困难性：约束非线性规划问题的困难性：1.最优解不一定在顶
2、点上；最优解不一定在顶点上；2.求解无约束问题的迭代法不能直接搬过来用。求解无约束问题的迭代法不能直接搬过来用。例如：对于上面的问题，如果不存在约束，从任意初始点例如：对于上面的问题，如果不存在约束，从任意初始点x (0)出发，沿出发，沿f(x)的负梯度方向进行一维搜索，便求得极小的负梯度方向进行一维搜索，便求得极小点点(0,0)T。有了约束，在进行一维搜索时，为了使求得的点是一个可有了约束，在进行一维搜索时，为了使求得的点是一个可行点，就必须对步长加以限制，这样，最远只能跑到边界行点，就必须对步长加以限制，这样，最远只能跑到边界上的一个点。上的一个点。当所取的x (0)不在直线x1-x2=0
3、上时，x (1)点就不会是最优解x*,因此还必须继续迭代下去找一个新的可行点，使目标函数取更小的值。x2x*o11x1x(1)x(0)可是，沿f(x)在x (1)处的负梯度方向已经找不到可行点，因而梯度迭代已经不能继续进行，尽管离最优解还可能很远。为了使迭代能继续下去，不仅要求搜索方向具有使目标函数下降的性质，而且要求在这个方向上有可行点。例如有一小段整个包含在可行域内，这样的方向称为可行方向。设计求解约束非线性规划的迭代法，关键是在每个迭代点处构造一个下降可行方向。求解约束非线性规划的另一个途径是：在某个近似解处，以已有较好解法的较为简单的问题近似代替原问题，用其最优解作为原来问题的新的近似
4、解。如将目标函数及约束条件中的非线性函数分别以它们的一阶泰勒多项式或二阶泰勒多项式近似代替，或以一无约束非线性规划近似代替。如何判断约束非线性规划的一个可行解是否为最优解？第一节 最优性条件一、等式约束极小化问题的最优性条件考虑下面的约束优化问题其中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
5、*处的切线，由l的任意性知， f(x*)必垂直于在x*处的切平面方向。由上面的分析知f(x*) 和h(x*)必在同一直线方向上，即存在数*, 满足可以证明，对于一般等式约束问题在最优解x*处，必存在数值 (1*, 2*, l*),使为便于记忆，引进拉格朗日函数（2）定理定理1 1（等式约束问题最优解的一阶必要条件）（等式约束问题最优解的一阶必要条件）解 （1）建立数学模型 取点A(x1,y1,z1), B(x2,y2,z2)，限制A在曲面上变化，B在平面上变化，则A、B 间距离S的最小值为解。问题的数学模型为：其中已把距离S最小等价地替换成S2 最小，以简化目标函数。 （2）利用最优性条件求解
6、再加约束条件由上述方程组解得相应目标函数值为由问题的几何意义知最优解肯定存在，又据必要条件仅此一个解，故以上所求即为最优解和最优值。二、一般非线性规划的最优性条件考虑问题其中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，统一写成把和2*=0，统一写成（5）（7）（6）从几何上看，(5)式的f(x*)
7、和 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*)考虑一般不等式约束问题g2(x)=0 x*g1(x)=0g1(x*)=0, g1为有效约束不等式约束问题的不等式约束问题的K-T点的点的几何意义几何意义
8、对于一般约束非线性规划问题（9）构造拉格朗日函数（10）定理2 （Kuhn-Tucher必要条件，简称K-T条件）对于非线性规划（9），若f, gi,hj 均可微且gi(x*),iI(x*), hj(x*), j=1,l线性无关，则x*为（9）的最优解的必要条件为：存在相应的拉格朗日乘子*和*使（9）K-TK-T条件条件条件条件是多元函数取得约束极值的是多元函数取得约束极值的必要条件必要条件必要条件必要条件,可以用来可以用来作为约束极值的判断条件。作为约束极值的判断条件。对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，对于
9、目标函数和约束函数都是凸函数的情况， 符合符合符合符合K-TK-T条件的点一定是全局最优点。条件的点一定是全局最优点。条件的点一定是全局最优点。条件的点一定是全局最优点。这种情况这种情况K-T条件即为多条件即为多元函数取得约束极值的充分必要条件。元函数取得约束极值的充分必要条件。满足满足K-T条件的可行点称为条件的可行点称为K-T点，最优性条件指在梯度线点，最优性条件指在梯度线性无关的条件下，最优点必定是性无关的条件下，最优点必定是K-T点。点。在实际应用中，很难验证所得的点是否为非线性规划的在实际应用中，很难验证所得的点是否为非线性规划的最优解，若能验证其是最优解，若能验证其是K-T点，就已
10、经满足了。有时构点，就已经满足了。有时构造算法也是以得到造算法也是以得到K-T点为目标的。点为目标的。例例2求以下非线性规划的求以下非线性规划的K-T点点解：非线性规划的解：非线性规划的K-T条件为条件为再加上约束（11）（12）（13）（14）（15）（16）x1f(x1)x1x2解解：在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，使对任意，使对任意t (0, )均有均有x+td D,则称则称d为从为从x点
11、出发的可行方向。点出发的可行方向。d为可行方向为可行方向d1不是可行方向不是可行方向xdd1D第二节第二节 可行方向法可行方向法基本思想基本思想：在每一个迭代点处，寻找一个下降可行方向，在每一个迭代点处，寻找一个下降可行方向，沿下降可行方向进行一维搜索。沿下降可行方向进行一维搜索。如何寻找可行方向？如何寻找可行方向？可行方向：设可行域DRn是非空集，xD.若对于某非零向量，d Rn,存在0，使对任意t (0, )均有x+td D,则称d为从点x出发的可行方向。例例7在由约束在由约束所确定的可行域内，任求一个在点x=(0,1,2,3)T处的可行方向。解解：首先检查在点x处哪些约束为有效约束，经检
12、查，约束（1）（2）（3）和x10为有效约束。设所求可行方向为根据可行方向的定义，应存在，使对任意 t(0,)有也能满足所有有效约束，即整理得整理得满足上述不等式的 均为可行方向。现只求一个可行方向，可令不等号改为等号，求解得得为使d10，可取d3=1得一可行方向利用可行方向的概念，典型的策略是：由可行点x (k)出发，找一下降可行方向d (k)作搜索方向，然后确定沿此方向移动的步长，得下一迭代点x (k+1).这类方法称可行方向法。搜索方向的选择方式不同就形成不同的可行方向法。Zoutendijk可行方向法考虑(1)上述问题的约束是线性的，仅目标函数是非线性的，在迭代点x (k)附近，可以用
13、f(x)的一阶泰勒展开式近似代替f(x).假设x (k)满足于是得到线性规划(2) 注意到d=0为上述线性规划(2)的可行点，其对应的目标函数值为0， 所以若d*为问题(2)的最优解，则若则d* 为问题(1)在x (k)处的下降可行方向； 若则x (k)为问题(1)的K-T点。(证明略)(2)(1)Zoutendijk可行方向法的具体步骤可行方向法的具体步骤1.任选可行点x (0)作初始点，令k=0; 2. 根据x (k)的有效约束把A分解为A1，A2， 相应地把b分解为b1,b2,使3. 求解线性规划设其最优解为d (k) 。解：取x (0) =(0,2)T,注意在x (0)点，有效约束仅x
14、10一个，故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（
15、2）取初始点 x (1) =(2,0)T（3）取初始点 x (1) =(1,2)T第三节第三节惩罚函数法惩罚函数法 基本思想基本思想：通过构造罚函数把约束优化问题转：通过构造罚函数把约束优化问题转化为化为一系列无约束最优化问题一系列无约束最优化问题，进而用无约束最优，进而用无约束最优化方法去求解。化方法去求解。 又称为序列无约束最小化方法。又称为序列无约束最小化方法。考虑一般约束非线性规划问题考虑一般约束非线性规划问题根据约束的特点，构造某种根据约束的特点，构造某种“惩罚惩罚”项，然后把它加到项，然后把它加到目标函数中去，使得约束问题的求解，转化成一系列无目标函数中去，使得约束问题的求解，转化
16、成一系列无约束问题的求解。约束问题的求解。“惩罚惩罚”策略：对于无约束问题求解过程中企图违反约策略：对于无约束问题求解过程中企图违反约束的那些迭代点，给以很大的目标函数值，迫使这一系束的那些迭代点，给以很大的目标函数值，迫使这一系列无约束问题的极小点或者不断的向可行域靠近，或者列无约束问题的极小点或者不断的向可行域靠近，或者一直保持在可行域内部移动，直到收敛于原约束问题的一直保持在可行域内部移动，直到收敛于原约束问题的极小点。极小点。常用的惩罚函数法有三种：一、外部惩罚函数法（外点法）一、外部惩罚函数法（外点法） 对违反约束的点在目标函数中加入相应的对违反约束的点在目标函数中加入相应的“惩罚惩罚”，而对可行点不予惩罚。此法的迭代点一般在可行域外部移而对可行点不予惩罚。此法的迭代点一般在可行域外部移动。动。二、内部惩罚函数法（内点法）二、内部惩罚函数法（内点法） 对企图从内部穿越可行域边界的点在目标函数中加入对企图从内部穿越可行域边界的点在目标函数中加入相应的相应的“障碍障碍”，距边界越近，障碍越大，在边界上给以，距边界越近，障碍越大，在边界上给以无穷大的障碍，从而保障迭代一直在可行域内
