第3.5章 二次规划算法.doc

第五章 二次规划算法 § 1二次规划问题 若非线性规划的目标函数为自变量的二次函数，约束条件又是线性的，就称这种规划为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解，由于许多方面的问题都可以抽象成二次规划的模型，下面的分析表明它和线性规划又有直接联系，因此受到较为广泛的关注。这方面的一个最直接的感受就是将一般的非线性规划归结为求解一系列的二次规划时（这大体相当于把非线性目标函数按Taylor公式展开取到二次项），其收敛速度要比改用线性规划快得多。 二次规划的数学模型可表示如下： （1） 式中是对称矩阵，，秩，，为n维常向量。显然，二次规划的可行集为凸集。如果二次型的矩阵是半正定的，则是凸函数，因之问题（1）变成凸规划问题，从而其局部极值即为整体极值，并且Kuhn-Tucker条件不但是取极值的必要条件，而且还是充分条件。 对于问题（1），K-T条件具如下形式： （2） 于是，若矩阵半正定，则求（1）的最优解问题归结为：若求得，，，满足（2），则相应的即为（1）的最优解。 为求解（2），文献[28]采用了引入目标函数的作法，实行单纯形迭代，并且规定迭代中和不得同时为基变量（为了满足（2）的第三个约束，通常称之为互补松弛条件），对于这样的特别处理，文献[28]称之为满足换基规定的单纯形法。文献[28]还进一步指出，在“规定”下进行单纯形迭代，一般说来，有可能迭代不下去。为此证明了在一定条件下，若迭代不下去，当前的解也是K-T条件（2）的解。 下边结合（2）的特殊结构对文献[28]中给出的“满足换基规定的单纯形法”做若干实质性的改进，并把它用于求解箱形约束的问题[35]，得到有限步收敛的简易结果。 §2．算法的改进 算法的改进可大体上归纳为以下三点： （一）不必引入目标函数。 文献[28]引入目标函数，把问题（2）的求解归结为一个完整的线性规划问题，这当然是个进步，也是以往经常采用的作法。不过本问题这样做，除了增加n个变量外，还常常成为按“规定”迭代不能进行下去的一个原因。如果不引入目标函数，只是按照通常的作法，令，这里，则（2）变成： （3） 于是问题归结为求出一个满足（3）的非负解。这当然比求有目标函数的最优解要少受限制和简易些。 （二）放宽因“规定”引起的限制。 为了满足（2）或（3）中的第三个约束，文献[28]做出如下规定： 若（或）已经是相应于第个极点的基变量，则（或）在第（）个极点的单纯形迭代中不能选为基变量，除非用（或）替换变量（或），此称为一种规定。 上述“规定”是充分的，即满足“规定”的最优解一定满足（2）中的互补松弛条件，因之是十分有意义的。从最终结果看一般也是必要的，除非某个基变量恰好取零值，否则便不是问题（1）的最优解。从这个意义上讲，完全取消“规定”是不可能的。 但是，我们觉得上述“规定”还是太严了些，其结果是迭代有可能进行不下去，虽然文献[28]下力气证明了即使迭代不下去也会得到满足（2）的解，但终归是在一定的条件下得到的结论，问题并没有完全彻底的解决。事实上，满足互补松弛条件只是对最终结果的要求，而迭代的中间过程，有时它不成立则是应当允许的，就是说在迭代中，如果出现和必须同为基变量，否则迭代便进行不下去的情形时，那就让这种情形发生好了，留待以后有机会再让其中的一个变量和离基就是了。于是我们得到如下的求解过程： 首先求出问题 （4） 的一个可行解（若（4）无可行解，则问题（1）无最优解），然后检查它是否满足 （5） （注意，此时（2）中的互补松弛条件与（5）等价）若满足，则其中的即为（1）的K-T点，不然则把（5）看作是新增约束，继续迭代，直到求得一个满足（5）的可行解，或者证明不存在满足（5）的可行解（此时无K-T点）为止。 三．求解过程的优化。 由于（4）的特殊结构，可使其求解过程大大简化。具体分析如下： 1°首先，由于与在式中仅有符号相反之差别（在迭代过程中也是如此），故与最多仅有一个能做基变量，亦即至少有一个为0，从而可以略去，如果非要做基变量不可时，改变列的符号即得，此时一定为非基变量，去之无妨。今后约定仍用表示，实行上述变号后，则基变量也加负号成－。 2°（4）中第一式已有个现成的基变量，可充分利用之。即不必急于改变它们基变量的性质，而是先求出的一个可行解，不妨设其基变量为，则迭代结果总可得到下表： 表1 其中.对之可采取如下迭代步骤： （i）若表1中，则已得到（4）的一个可行解，转（iii）。若不然，以（－1）乘的行，并去掉该行最左边的基变量，并把这些行叫做无基行，转（ii）。 （ii）先让进基，而主元优先选在（A）无基行中，（