约束问题最优化方法

第9章约束问题最优化方法9.1约束优化问题的最优牲条件约束条件下求极小值的非线性规划问题的数学模型如下：min().()0(1,2,,)()0(1,2,,)ijfxsthximgxjl（9-1）9．1．1基本概念1．起作用约束设非线性规划问题（9.1.1）的可行域为H{,()0,()0,1,2,,,1,2,,}nijHxxEhxgximjl(1)xH,考虑某一个不等式约束()0jgx，(1)x满足它有两种可能：其一是()0jgx，这时，(1)x不是处于由这一约束条件形成的可行域的边界上，因此当点不论沿什么方向稍微离开(1)x时，都不会违背这一约束条件，这样的约束就称为(1)x点的不起作用约束，它对(1)x的微小扰动不起限制作用；注意，不起作用约束并不是无效约束！其二是()0jgx，这时(1)x处于由这一约束条件形成的可行域的边界上，它对(1)x点的扰动起到了某种限制作用，即当点沿某些方向稍微离开(1)x时，仍能满足约束条件，而当点沿另一些方向离开(1)x时，不论步长多么小，都将违背该约束条件．这样的约束称为(1)x点的起作用约束．显然，等式约束对所有可行点来说都是起作用约束．特别地，对于只含不等式约束的非线性规划问题，严格内点（即不在可行域边界上的点）不存在起作用的约束．2．正则点对于非线性规划问题(9-1)，如果可行点(1)x处，各起作用约束的梯度线性无关，则(1)x是约束条件的一个正则点，特别地，严格内点也是约束条件的正则点．3．可行下降方向的判定条件在7.4节，我们给出了可行下降方向的定义，在这里我们推导可行下降方向的判定条件．设(1)xH，定义集合(1)(1)(){()0,1}iIxigxil为(1)x点所有起作用约束的下标的集合．可行下降方向的判定条件(1)(1)()0(())TjgxdjIx(1)()0Tfxd可行下降方向有十分明确的几何意义:点(1)x处的可行下降方向d与该点处目标函数的负梯度方向的夹角为锐角，与该点处起作用约束函数的梯度方向的夹角也为锐角．9.1.2Kuhn-Tucker条件（一阶必要条件）•Kuhn-Tucker条件是非线性规划领域中最重要的理论成果之一，是确定某点是最优点的一阶必要条件．只要是最优点（且为正则点）就必须满足这个条件，但一般来说它并不是充分条件，因而满足这个条件的点不一定是最优点．但对于凸规划，Kuhn-Tucker条件既是最优点存在的必要条件，同时也是充分条件．1．Kuhn-Tucker条件Kuhn-Tucker条件就是下面的定理．定理9-1考虑问题(9-1)，设***,(){()0,1}ixHIxigxil，()fx与*()(())igxiIx在点*x处可微，*()(())igxiIx在点*x处连续，()jhx),,2,1(mj在点*x处连续可微，且向量集***{(),()(),1,2,,}ijgxhxiIxjl线性无关．若*x是(9-1)的局部最优解，则比存在****12(,,,)Tl和向量****12(,,,)Tm，使下述条件成立：*****11***()()()0()0,1,2,,0,1,2,,lmjjiijijjjfxgxhxgxjlil(9-6)式(9-6)就是既含有等式约束又含有不等式约束的非线性规划问题的Kuhn-Tucker条件，简称K-T条件，满足Kuhn-Tucker条件的点称为Kuhn-Tucker条件点或者K-T点．如果一个非线性规划问题只含有等式约束或者只含有不等式约束，其相应的Kuhn-Tucker条件也相应地具有更简化的形式．通常称函数11[()()()]lmjjiijifxgxhx为问题(9-1)的广义拉格朗日函数，称乘子**2*1,,,l和**2*1,,,m为广义拉格朗日乘子，称向量*和*为乘子向量．由（9-.6）的第二个向量方程可知，当不等式约束()0jgx在*x处为不起作用约束时，*j必为零，在运用K-T条件求K-T点时，利用这一点可以大大地简化计算，另外还要把约束条件都加上．2．求满足Kuhn-Tucker条件的点例9-1求下列非线性规划问题的Kuhn-Tucker点．22112212min()221010fxxxxxxx03605..212221xxxxts例9-2求下列非线性规划问题的Kuhn-Tucker点．11min()..()0npiiniifxxsthxxa其中0,1ap．9.1.3关于凸规划的全局最优解定理对于非线性规划问题(9-1)而言，若()fx是凸函数，()(1,2,,)jgxjl是凹函数，()(1,2,,)ihxim是线性函数，可行域为H，*xH，且在*x处有Kuhn-Tucker条件(9-6)成立，则*x是全局最优解．显然，上述定理中的可行域H是凸集，又目标函数()fx是凸函数，故问题属于凸规划．由上述定理可知，对凸规划问题而言，Kuhn-Tucker条件是局部极小点的一阶必要条件，同时也是充分条件，而且局部极小点就是全局极小点．例9-1和例9-2（当0x时）中的问题都是凸规划，因此所求得的K-T点是全局极小点．9.1.4二阶充分条件1.二阶充分条件对非线性规划问题（9-1）而言，若()fx、()(1,2,,)igxjl、()(1,2,,)ihxim二次连续可微，*x是可行点，又存在向量****12(,,,)Tm和****12(,,,)Tm使Kuhn-Tucker条件(9-6)成立，且对满足下述(9-7)、(9-8)、(9-9)三条件的任意非零向量z有(9-10)成立，则*x是问题(9-1)的严格局部极小点．*******()0()0(97)()0()0(98)()01,2,,(99)TjjTjjTizgxjIxzgxjIxzhxim且且2**2**2*11[()()()]0mlTiijjijzfxhxgxz(9-10)其中*()Ix是*x处起作用的不等式约束函数的下标j的集合．显然，上述二阶充分条件中的(9-10)式的2**2**2*11[()()()]mliijjijfxhxgx即广义拉格朗日函数在点*x处的海赛矩阵．若令满足(9-7)、(9-8)、(9-9)三条件的非零向量z构成的子空间为M，则(9-10)式表明，广义拉格朗日函数在点*x处的海赛矩阵在子空间M上是正定的．2．利用Kuhn-Tucker条件和二阶充分条件求约束极小（1）第一种情况如果能用其它方法（如几何作图或通过解约束方程组求出约束条件的交点等）先求出一个点*x，这个点是约束极小的可能性很大，不妨先假设其为约束极小，再逐一证之．①证明*x是可行点．②证明*x是正则点．③把*x代入Kuhn-Tucker条件(9.1.6)式中，应能求出符合条件的向量*和*．④证明广义拉格朗日函数在点*x处的海赛矩阵在子空间M上是正定的．若能证明上述四点，则*x是一个严格局部极小点．（2）第二种情况若不能先求出一个可能极小点的具体值，就先求出满足Kuhn-Tucker条件的点*x，再证明上述③和④，则*x是一个严格局部极小点．9．2近似规划法近似规划法是一种线性化的方法：将非线性规划线性化，然后通过求解一系列线性规划来求原问题的近似最优解．考虑非线性规划问题min().()0(1,2,,)()0(1,2,,)ijnfxsthximgxjlxHE（9-11）其中H是可行域，nR是n维欧氏空间．()()(1,2,,)ifxhxim、和()(1,2,,)jgxjl均存在一阶连续偏导数．近似规划法的基本思想是：将问题（9-11）中的目标函数和各约束函数都近似为线性函数，并对各变量的取值范围加以限制，从而得到一近似的线性规划，再用单纯形法求解之，把符合原始约束条件的最优解作为问题（9-11）的解的近似．每得到一个近似解后，都从这一点出发，重复以上步骤．这样，通过求解一系列线性规划，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解．应用近似规划法时，必须给定一个初始的可行点．9.2.1线性近似规划的构成设()kxH，将目标函数()fx与约束条件函数()(1,2,,)ihxim和()(1,2,,)jgxjl在点()kx处作一阶Taylor展开，并取其线性近似式，可得到下列线性规划问题：()()()()()()()()()()()min()()();.()()()0(1,2,,),()()()0(1,2,,),(1,2,,).kkTkkkTkjjkkTkiikkjjjfxfxxxstgxgxxxjlhxhxxximxxjn（9-12）上述线性规划中最后一组不等式约束，即是对变量x所施加的限制．其中jx是x的第j个分量，),,2,1()(njkj是预先给定的变量限制范围，称为步长限制量．求解线性规划（9-12），设得到的最优解为(1)kx，若(1)kx是原问题（9-11）的可行解，则在这一点再将目标函数与各约束函数线性化，并沿用步长限制：)()1(:kjkj),,2,1(nj；若(1)kx不属于原问题（9-11）的可行域，则减少步长限制量，取),,,2,1(:)()1(njkjkj一般取41,21等值，重新求解当前的线性规划问题．9.2.2近似规划法的算法步骤1．给定初始可行点(1)xH，步长限制),,2,1()1(njj，缩小系数)1,0(，允许误差21,,置1k．2．求解线性规划问题：()()()()()()()()()()()min()()();.()()()0(1,2,,),()()()0(1,2,,),(1,2,,).kkTkkkTkjjkkTkiikkjjjfxfxxxstgxgxxxjlhxhxxximxxjn得最优解x．3．若x满足原问题(9.2.1)的可行性，则令(1)kxx，转第4步；否则，置),,,2,1(:)()1(njkjkj返回第2步．4．若(1)()1()()kkfxfx，且满足(1)()2,kkxx或),,,2,1(2)(njkj则(1)kx为原问题的近似最优解，停止迭代，输出(1)kx．否则，令),,,2,1(:)()1(njkjkj置1kk，返回第2步．9．3可行方向法考虑非线性规划问题：min().()0(1,2,,)jnfxstgxjlxHE（9-13）其中H是问题(9-13)的可行域，设()kx是它的一个可行点，但并不是所要求的极小点．为了求得极小点或近似极小点，应在()kx的可行下降方向中选取某一方向)(kd为搜索方向，然后确定该方向上的步长k，使(1)()()(1)()()()kkkkkkxxdHfxfx若满足精度要求，停止迭代，(1)kx就是所要求的点；否则，从(1)kx出发继续迭代，直到满足要求为止．上述方法称为可行方向法．它具有下述特点：迭代过程中所采用的搜索方向为可行方向，所产生的迭代点列(){}kx始终在可行域内，目标函数值单调下降．这是一类算法，由不同的规则产生出的可行方向作为搜索方向形成了不同的可行方向法，这类方法可以看作无约束非线性规划问题下降迭代类算法的自然推广．但通常说的可行方向法，指的是Zoutendijk在1960年提出的算法及其变形，下面介绍Zoutendijk可行方向法．这是一种线性化方法．9.3.1基本原理与算法步骤1．给定初始可行点(1)xH，允许误差0,021，并置1k．2．确定()kx点处的起作用约束下标集()()KIx：()