第五章二次规划算法 §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 点）为止
三.求解过程的优化 由于(4)的特殊结构,可使其求解过程大大简化。具体分析如下 1°首先,由于Au(与Au2)在式中仅有符号相反之差别(在迭代过程中也是如此), 故u1)与t42)最多仅有一个能做基变量,亦即至少有一个为0,从而可以略去Au(2),如果 非要2)做基变量不可时,改变u列的符号即得2),此时4)一定为非基变量,去之无妨。 今后约定仍用1表示u,实行上述变号后,则基变量也加负号成-41 2°(4)中第一式已有n个现成的基变量v1V2…,Vn,可充分利用之。即不必急于改 变它们基变量的性质,而是先求出Ax=b的一个可行解,不妨设其基变量为x1,x2…,xm, 则迭代结果总可得到下表 表1 xI 2 Bn ly l4 BnB1nt…Bnn10 B,n B 0 n00 Bmn B B,00 B 0 B Bn 000 其中∝n≥0,j=1…,m对之可采取如下迭代步骤 (i)若表1中α,≥0,1=1,…,n,则已得到(4)的一个可行解,转(ⅲ)。若不然,以 (-1)乘,<0的行,并去掉该行最左边的基变量,并把这些行叫做无基行,转(ⅱ)。 (ⅱi)先让l1…,Ln进基,而主元优先选在(A)无基行中,(B)基变量,…,Vm所在 行中。迭代中,由于我们略去了-2所在列,它与l2列仅符号相反。故对u,列,除了用正 系数计算最小比值求得一元素,称之为准主元外,还应以负系数,取绝对值再求最小比值, 确定另一准主元(这相当于在-,列选主元),稍有不同的是,若最后迭代主元选定为负系 数,则迭代前应将该列元素全变号,且用-l1代替l,。一般的,我们可以根据需要随时改 217
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 。一般的，我们可以根据需要随时改
变变量所在列的符号(若已为-u,则变号后又成为y,进而找到更理想的主元。送代 结果若不存在无基行,转(ⅲ),否则于当前的非基变量xn+1…xn等所在列,选择主元 实行 Gauss消元,直到不存在无基行为止,转(iⅲ1)。 迭代中,若对某无基行,出现常数项大于0,而该行其余系数小于或等于0,结束,此 时问题(4)无可行解。 (ⅲi)检査(4)的可行解是否满足(5),若满足,则已得问题(1)的K-T点,结束。 若不然,则集合G={xv>0,1≤i≤n}非空。任取一指标i∈G,考查基变量x和v所 在行,若对x(或v)行除主元外已无正系数且u1(=1,…m)的系数均为0(常数项除外), 则x(或v)必为非0基变量,这时转而考查v1(或x,),若亦然,结束,问题(1)无K-T 不然,于v(或x)行正系数所在列,确定准主元。若准主元不止一个,则于其中选 择一主元,实行 Gauss消元,优先选择满足(1°)落在ν(或x,)行的,(2°)迭代后不 产生新的vx>0的,则集合G中的元素至少减少1个,(3°)主元所在行的常数项不为0 的,直到主元选在v;(或x,)行,迭代后返回(i) 如果迭代在各种选择之下均不可避免的出现循环,结束,说明集合G永远非空,故问 题无KT点 以上迭代程序表明,求解二次规划问题(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.已知 2201 2501 为半正定矩阵,P=-3/ b 002-1 试求此二次规划问题(1)的解。 解:经简单计算可得相应的表1: 218
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：
x_0 v2yv 141 12 30 0 000 213 00000 l 000 y0010 2000100000 53-22 第 三 00 14 0 00000100000 00000 2 1000 0100 成行 为 3122 无 基 右 上 角是 有准 圈主 131 的 方主 框元 内 vxxy24 0 为 6 00001000 已 得 可 0100 仃 00000 2 按 000 411321 解宜元 选 为行 主中 3 的量 非只 基有 变 xyx以 100 个正系数) 0000 00000 33% 00 % 00000 000 选为 1 11 xyy 0000 000 5y% 0 3为 %%%为 0 0 100 00000 13% 00000 33 y3 000 3%33%%% 00 - 0 00
219 1 2 3 4 1 2 1 2 3 4 x x x x u u v v v v 1 2 3 4 1 3 v v v v x x 0 4 0 5 1 0 1 0 0 0 0 1 0 5 2 1 0 1 0 0 0 2 0 1 1 1 0 0 1 0 0 1 0 2 1 1 0 0 0 1 1 3 0 2 0 0 0 1 1 1 0 0 − − − − − − − − − 5 3 1 2 2 1 − 以（－1） 乘第三行 1 2 4 1 3 v v v x x 0 4 0 5 1 0 1 0 0 0 0 1 0 5 2 1 0 1 0 0 0 2 0 1 1 1 0 0 1 0 0 1 0 2 1 1 0 0 0 1 1 3 0 2 0 0 0 1 1 1 0 0 − − − − − − − − − − 5 3 1 2 2 1 三行成为 无基行，右 上角有圈 的是准主 元，方框内 为主元 1 2 1 4 1 3 v v u v x x 0 6 0 6 0 1 1 0 1 0 0 5 0 7 0 3 0 1 2 0 0 2 0 1 1 1 0 0 1 0 0 1 0 1 0 2 0 0 1 1 1 3 0 2 0 0 0 1 1 1 0 0 − − − − − − − − − − − 4 1 1 3 2 1 已得可行 解，按（iii） 宜选 5 为主 元（ 1 x 行中 的非基变 量只有一 个正系数） 1 2 1 4 1 3 v x u v x x 12 13 6 7 0 0 0 0 1 0 5 5 5 5 0 1 0 0 0 0 7 3 1 2 5 5 5 5 0 0 0 1 0 0 9 1 2 1 5 5 5 5 12 1 7 3 0 0 0 0 0 1 5 5 5 5 11 9 3 6 1 0 0 0 0 0 5 5 5 5 2 1 2 3 0 0 1 0 0 0 5 5 5 5 − − − − − − − − − − − − − 14 5 1 5 7 5 16 5 7 5 4 5 不选 11 5 因为（2°） 之（ⅱ） 1 2 1 4 2 3 v x u v u x − 13 7 0 0 0 0 1 0 1 1 9 9 3 3 1 2 1 0 0 0 0 0 0 0 3 3 1 14 1 1 0 0 1 0 0 0 9 9 3 3 7 37 0 0 0 0 0 1 2 1 9 9 3 3 5 0 0 0 1 0 0 11 1 2 9 9 3 3 1 1 0 1 0 0 0 0 0 0 3 3 − − − − − − − − − − − 7 9 2 3 14 9 19 9 7 9 1 3