东北财经大学：《运筹学》课程教学资源（教案讲义）第三篇非线性规划第五章二次规划算法.doc_大学文库

第五章二次规划算法 §1二次规划问题若非线性规划的目标函数为自变量x∈R"的二次函数,约束条件又是线性的,就称这种规划为二次规划。二次规划是非线性规划中比较简单的一类,它较容易求解,由于许多方面的问题都可以抽象成二次规划的模型,下面的分析表明它和线性规划又有直接联系,因此受到较为广泛的关注。这方面的一个最直接的感受就是将一般的非线性规划归结为求解一系列的二次规划时(这大体相当于把非线性目标函数按 Taylor公式展开取到二次项),其收敛速度要比改用线性规划快得多二次规划的数学模型可表示如下: min f=x' Cx+px s.t. Ax=b (1) x≥0 式中C=(cn)m是对称矩阵,A=(an)mx,秩A=m≤n,x∈R",p,b为n维常向量。显然,二次规划的可行集为凸集。如果二次型的矩阵C是半正定的,则f(x)是凸函数,因之问题(1)变成凸规划问题,从而其局部极值即为整体极值,并且Kuhn- Tucker条件不但是取极值的必要条件,而且还是充分条件对于问题(1),K-T条件具如下形式 -Cx+A'u+v=p Vx=0 x≥0.y≥0 于是,若矩阵C半正定,则求(1)的最优解问题归结为:若求得x∈R”,v∈R",'∈Rm 满足(2),则相应的x即为(1)的最优解。为求解(2),文献[28]采用了引入目标函数的作法,实行单纯形迭代,并且规定迭代中 x和v(=1…,n)不得同时为基变量(为了满足(2)的第三个约東,通常称之为互补松弛条件),对于这样的特别处理,文献[28]称之为满足换基规定的单纯形法。文献28还进一步指出,在“规定”下进行单纯形迭代,一般说来,有可能迭代不下去。为此证明了在一定条件下,若迭代不下去,当前的解也是KT条件(2)的解。下边结合(2)的特殊结构对文献([28]中给出的“满足换基规定的单纯形法”做若干实质性的改进,并把它用于求解箱形约束的问题35,得到有限步收敛的简易结果。 §2.算法的改进算法的改进可大体上归纳为以下三点 (一)不必引入目标函数。 215

215 第五章二次规划算法 §1 二次规划问题若非线性规划的目标函数为自变量 n x R  的二次函数，约束条件又是线性的，就称这种规划为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解，由于许多方面的问题都可以抽象成二次规划的模型，下面的分析表明它和线性规划又有直接联系，因此受到较为广泛的关注。这方面的一个最直接的感受就是将一般的非线性规划归结为求解一系列的二次规划时（这大体相当于把非线性目标函数按 Taylor 公式展开取到二次项），其收敛速度要比改用线性规划快得多。二次规划的数学模型可表示如下： 1 min 2 . . 0 T T f x Cx p x s t Ax b x = + =  （1）式中 ( ) C c = ij n n 是对称矩阵， ( ) A a = ij m n ，秩 A m n =  ， n x R  ， p b, 为 n 维常向量。显然，二次规划的可行集为凸集。如果二次型的矩阵 C 是半正定的，则 f x( ) 是凸函数，因之问题（1）变成凸规划问题，从而其局部极值即为整体极值，并且 Kuhn-Tucker 条件不但是取极值的必要条件，而且还是充分条件。对于问题（1），K-T 条件具如下形式： 0 0, 0 T T Cx A u v p Ax b v x x v − + + =   =  =      （2）于是，若矩阵 C 半正定，则求（1）的最优解问题归结为：若求得 n x R   ， n v R   ， m u R   ，满足（2），则相应的 x  即为（1）的最优解。为求解（2），文献[28]采用了引入目标函数的作法，实行单纯形迭代，并且规定迭代中 i x 和 ( 1, , ) i v i n = 不得同时为基变量（为了满足（2）的第三个约束，通常称之为互补松弛条件），对于这样的特别处理，文献[28]称之为满足换基规定的单纯形法。文献[28]还进一步指出，在“规定”下进行单纯形迭代，一般说来，有可能迭代不下去。为此证明了在一定条件下，若迭代不下去，当前的解也是 K-T 条件（2）的解。下边结合（2）的特殊结构对文献[28]中给出的“满足换基规定的单纯形法”做若干实质性的改进，并把它用于求解箱形约束的问题[35]，得到有限步收敛的简易结果。 §2．算法的改进算法的改进可大体上归纳为以下三点：（一）不必引入目标函数

文献[28]引入目标函数,把问题(2)的求解归结为一个完整的线性规划问题,这当然是个进步,也是以往经常采用的作法。不过本问题这样做,除了增加n个变量外,还常常成为按“规定”迭代不能进行下去的一个原因。如果不引入目标函数,只是按照通常的作法, 令u=1)-12),这里l≥0,2)≥0,则(2)变成 Cx+Auo-Au2)+v=p A x= b vx=0 x≥0.t()≥0.u2)≥0.y≥0 于是问题归结为求出一个满足(3)的非负解。这当然比求有目标函数的最优解要少受限制和简易些 (二)放宽因“规定”引起的限制。为了满足(2)或(3)中的第三个约束vx=0,文献8做出如下规定: 若x1(或v)已经是相应于第k个极点的基变量,则v(或x)在第(k+1)个极点的单纯形迭代中不能选为基变量,除非用v(或x,)替换变量x,(或v),此称为一种规定上述“规定”是充分的,即满足“规定”的最优解一定满足(2)中的互补松弛条件vx=0 因之是十分有意义的。从最终结果看一般也是必要的,除非某个基变量恰好取零值,否则便不是问题(1)的最优解。从这个意义上讲,完全取消“规定”是不可能的但是,我们觉得上述“规定”还是太严了些,其结果是迭代有可能进行不下去,虽然文献(28]下力气证明了即使迭代不下去也会得到满足(2)的解,但终归是在一定的条件下得到的结论,问题并没有完全彻底的解决。事实上,满足互补松弛条件yx=0只是对最终结果的要求,而迭代的中间过程,有时它不成立则是应当允许的,就是说在迭代中,如果出现 x和ν必须同为基变量,否则迭代便进行不下去的情形时,那就让这种情形发生好了,留待以后有机会再让其中的一个变量x,和v离基就是了。于是我们得到如下的求解过程首先求出问题 -Cx+Au-Au+v= Ax= b (4) x≥0.,≥0,u(2)≥0,v≥0 的一个可行解(若(4)无可行解,则问题(1)无最优解),然后检查它是否满足 xV=0,i=1, (注意,此时(2)中的互补松弛条件vx=0与(5)等价)若满足,则其中的x即为(1) 的K-T点,不然则把(5)看作是新增约束,继续迭代,直到求得一个满足(5)的可行解, 或者证明不存在满足(5)的可行解(此时无K-T点)为止 216

216 文献[28]引入目标函数，把问题（2）的求解归结为一个完整的线性规划问题，这当然是个进步，也是以往经常采用的作法。不过本问题这样做，除了增加 n 个变量外，还常常成为按“规定”迭代不能进行下去的一个原因。如果不引入目标函数，只是按照通常的作法，令 (1) (2) u u u = − ，这里 (1) (2) u u   0, 0 ，则（2）变成： (1) (2) (1) (2) 0 0, 0, 0, 0 T T T Cx A u A u v p Ax b v x x u u v − + − + =   =  =        （3）于是问题归结为求出一个满足（3）的非负解。这当然比求有目标函数的最优解要少受限制和简易些。（二）放宽因“规定”引起的限制。为了满足（2）或（3）中的第三个约束 0 T v x = ，文献[28]做出如下规定：若 i x （或 i v ）已经是相应于第 k 个极点的基变量，则 i v （或 i x ）在第（ k +1 ）个极点的单纯形迭代中不能选为基变量，除非用 i v （或 i x ）替换变量 i x （或 i v ），此称为一种规定。上述“规定”是充分的，即满足“规定”的最优解一定满足（2）中的互补松弛条件 0 T v x = ，因之是十分有意义的。从最终结果看一般也是必要的，除非某个基变量恰好取零值，否则便不是问题（1）的最优解。从这个意义上讲，完全取消“规定”是不可能的。但是，我们觉得上述“规定”还是太严了些，其结果是迭代有可能进行不下去，虽然文献[28]下力气证明了即使迭代不下去也会得到满足（2）的解，但终归是在一定的条件下得到的结论，问题并没有完全彻底的解决。事实上，满足互补松弛条件 0 T v x = 只是对最终结果的要求，而迭代的中间过程，有时它不成立则是应当允许的，就是说在迭代中，如果出现 i x 和 i v 必须同为基变量，否则迭代便进行不下去的情形时，那就让这种情形发生好了，留待以后有机会再让其中的一个变量 i x 和 i v 离基就是了。于是我们得到如下的求解过程：首先求出问题 (1) (2) (1) (2) 0, 0, 0, 0 T T Cx A u A u v p Ax b x u u v − + − + =   =       （4）的一个可行解（若（4）无可行解，则问题（1）无最优解），然后检查它是否满足 0, 1, , i i x v i n = = （5）（注意，此时（2）中的互补松弛条件 0 T v x = 与（5）等价）若满足，则其中的 x 即为（1）的 K-T 点，不然则把（5）看作是新增约束，继续迭代，直到求得一个满足（5）的可行解，或者证明不存在满足（5）的可行解（此时无 K-T 点）为止

217 三．求解过程的优化。由于（4）的特殊结构，可使其求解过程大大简化。具体分析如下： 1°首先，由于 T (1) A u 与 T (2) A u 在式中仅有符号相反之差别（在迭代过程中也是如此），故 (1) i u 与 (2) i u 最多仅有一个能做基变量，亦即至少有一个为 0，从而可以略去 T (2) A u ，如果非要 (2) i u 做基变量不可时，改变 (1) i u 列的符号即得 (2) i u ，此时 (1) i u 一定为非基变量，去之无妨。今后约定仍用 i u 表示 (1) i u ，实行上述变号后，则基变量也加负号成－ i u 。 2°（4）中第一式已有 n 个现成的基变量 1 2 , , , n v v v ，可充分利用之。即不必急于改变它们基变量的性质，而是先求出 Ax b = 的一个可行解，不妨设其基变量为 1 2 , , , m x x x ，则迭代结果总可得到下表：表 1 1 2 1 1 2 m n m n x x x x u u v v v 1 2 1 2 n m v v v x x x 1 1 1 1 2 2 1 2 1 1 2 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 n n n m n n n m nn n n n n m n n n n n m n             + + + + + + + + + 1 2 1 2 n n n n m       + + + 其中 0, 1, , n j  +  =j m .对之可采取如下迭代步骤：（i）若表 1 中 0, 1, , i   =i n ，则已得到（4）的一个可行解，转（iii）。若不然，以（－1）乘 i  0 的行，并去掉该行最左边的基变量，并把这些行叫做无基行，转（ii）。（ii）先让 1 , , u um 进基，而主元优先选在（A）无基行中，（B）基变量 1 , , m v v 所在行中。迭代中，由于我们略去了 j −u 所在列，它与 j u 列仅符号相反。故对 j u 列，除了用正系数计算最小比值求得一元素，称之为准主元外，还应以负系数，取绝对值再求最小比值，确定另一准主元（这相当于在 j −u 列选主元），稍有不同的是，若最后迭代主元选定为负系数，则迭代前应将该列元素全变号，且用 j −u 代替 j u 。一般的，我们可以根据需要随时改

218 变变量 j u 所在列的符号（若已为 j −u ，则变号后又成为 j u ），进而找到更理想的主元。迭代结果若不存在无基行，转（iii），否则于当前的非基变量 1 , , m n x x + 等所在列，选择主元，实行 Gauss 消元，直到不存在无基行为止，转（iii）。迭代中，若对某无基行，出现常数项大于 0，而该行其余系数小于或等于 0，结束，此时问题（4）无可行解。（iii）检查（4）的可行解是否满足（5），若满足，则已得问题（1）的 K-T 点，结束。若不然，则集合 { | 0,1 } G i x v i n =    i i 非空。任取一指标 i G ，考查基变量 i x 和 i v 所在行，若对 i x （或 i v ）行除主元外已无正系数且 u (i 1, ,m) i =  的系数均为 0（常数项除外），则 i x （或 i v ）必为非 0 基变量，这时转而考查 i v （或 i x ），若亦然，结束，问题（1）无 K-T 点。不然，于 i v （或 i x ）行正系数所在列，确定准主元。若准主元不止一个，则于其中选择一主元，实行 Gauss 消元，优先选择满足（1°）落在 i v （或 i x ）行的，（2°）迭代后不产生新的 v xi i  0 的，则集合 G 中的元素至少减少 1 个，（3°）主元所在行的常数项不为 0 的，直到主元选在 i v （或 i x ）行，迭代后返回（iii）。如果迭代在各种选择之下均不可避免的出现循环，结束，说明集合 G 永远非空，故问题无 K-T 点。以上迭代程序表明，求解二次规划问题（1），有以下几种可能：（A）（1）的可行集非空，矩阵 C 半正定。此时问题（1）一定有解，且问题（4）的任一满足（5）的可行解均是（1）的最优解。（B）矩阵 C 非半正定，但问题（4）有满足（5）的可行解，则该可行解是问题（1）的 K-T 点，其最优解若存在则是诸 K-T 点中使目标函数达最小值者。（C）问题（4）没有满足（5）的可行解，则问题（1）无 K-T 点，因此亦无最优解。（D）问题（1）无满足 Ax b = 的可行解。 §3．各种情形的例子例 1．已知 2 2 0 1 2 5 0 1 0 0 2 1 1 1 1 1 C       =   −     − 为半正定矩阵， 1 1 3 1 p     −   =   −     ， 1 2 1 1 0 1 1 1 A   − − =     − ， 1 1 b   =     试求此二次规划问题（1）的解。解：经简单计算可得相应的表 1：

222 1 2 3 1 v v v x 0 3 1 0 0 8 2 3 3 0 8 0 4 0 1 0 0 0 0 1 0 0 1 1 0 0 4 1 3 3 − − − 8 4 0 4 1 1 3 1 v u v x 0 0 1 0 10 3 2 3 3 4 0 2 0 1 0 0 1 4 0 2 0 0 0 1 1 4 1 0 0 0 0 4 1 3 3 − − − − 5 1 1 4 此行非基变量系数全为负，故必有 v1  0 ，从而应在 1 x 行的正系数所在列寻找主元 1 1 2 1 v u x x 0 0 0 1 2 1 5 3 3 3 0 0 0 1 0 0 1 0 1 0 0 0 1 1 8 2 1 0 0 0 1 1 2 3 6 3 − − − − − 20 3 0 1 2 10 3 最末行非基变量系数全为负，故必有 x1  0 至此，知必有 xv1 1  0 ，故问题没有满足（5）的可行解，这说明原问题无 K-T 点，从而亦无最优解。 §4 算法的理论分析一、关于无基行由于无基行中无基变量，因此在迭代中可能出现行中系数全非正（有基行不会发生此情形）的情形（若该行有 i u 的系数不为 0，则应认为该行既有正系数又有负系数），这时，若无基行的常数项大于 0，则问题（4）便无可行解，若常数项等于 0，则该行非 0 系数对应的变量都必须取 0 值，结果该行成为恒等式，故可删去，取 0 值的变量亦应删去，称上述过程为置零处理（若系数均为正，而常数项为 0，亦可实行置 0 处理）。经置零处理后，问题规模变小了，求解过程得以简化。上述分析可概括为下面的定理。定理 1、迭代中若对某无基行，出现系数全非正且 u (i 1, ,m) i =  的系数均为 0 而常数项大于 0 的情形，则问题（4）无可行解，从而问题（1）无最优解。若常数项为 0，则经置零处理后，该无基行和取零值的变量均可去掉。二、关于增加约束 x v i n i i =   0,1 的处理迭代中在求得（4）的一个可行解之后，需检查互补松弛条件约束（5）是否成立，亦即集合 { | 0,1 } G i x v i n =    i i 是否为空集，若非空，则任取 i G ，实行步骤（iii），则有以下结论：定理 2、对于任意的 0 i G ，实行步骤（iii）进行迭代的结果，则只有两种情形，一是

224 可能实现了 0 0 x vi i = 0 ，结果却可能导致另一 1 1 x vi i  0 。捺下个葫芦起来了个瓢，甚至出现循环现象，致使迭代无休止的进行。对此，有以下定理。定理 3、在任取 i G ，实行迭代程序的过程中，如果迭代在各种选择的情况下，均不可避免的出现循环，且 G 始终保持非空，则问题（1）无 K-T 点。证：注意到这样一个事实，即从任一个基可行解出发，通过 Gauss 消元，可以达到任一基可行解，从几何上看，这是显然的，因为从可行域的某一指定的顶点出发，实行一次 Gauss 消元，可达到其任一相邻顶点，然后再从相邻顶点出发，又可达到另一顶点，如此进行，总可达到任意一个顶点。注意到基可行解的有限性，故如果迭代不出现死循环，则可以跑遍每一个顶点。如果问题存在 K-T 点，则它必将在某—选择下经迭代后达到，从而导致不出现循环和集合 G 为空集。这与定理假设矛盾，故问题无 K-T 点。 §5．对于箱形约束规划的应用下面考虑将上面的分析结果应用于一种特殊情况，即所谓如下的箱形约束的问题。 1 min 2 . . T T f x Cx p x s t a x d = +   （7）这里 a 和 d 是 n 维常向量， a d  。对于问题（7），K-T 条件变成如下更简单的形式：定理 4、若对 j n =1, 2, , 成立： ( ) 0 Cx p x a j j j   +  = 当（8） ( ) 0 Cx p x d j j j   +  = 当（9） ( ) 0 Cx p a x d j j j j   + =   当（10）其中 ( ) Cx p j  + 是向量 Cx p  + 的第 j 个分量，则 x  是问题（7）的 K-T 点。由于（7）的约束可以写成 0 0 x a x d − +  −  故（7）的 K-T 条件为： , 0, , 0 0, 0 , 0, 0 i i i i i i i i i i i Cx v u p x a v x d u a x d v u d x a v u  − + − =   =  =     = =        若则若则若，则（11）注意到把（10）式的若干倍，加于（8）或（9），并不会改变（8）和（9）的符号。而若 i i x a = ，则必有 i i x d  ，这说明 i v 和 i u 至少有一个取 0 值，故仿前作法可将其中一个略去，这样（11）

东北财经大学：《运筹学》课程教学资源（教案讲义）第三篇 非线性规划 第五章 二次规划算法

东北财经大学：《运筹学》课程教学资源（教案讲义）第三篇非线性规划第五章二次规划算法