互补问题和二次规划的关系论文00240.doc

摘要互补问题与数学规划、经济学、对策论、力学、变分学、随机最优制等学科关系密切，在科学研究和工程技术各领域有着广泛的应用。从二十世纪60年代以后，互补问题的理论和算法研究一直是应用数学和计算数学领域中的一个热点课题，有关互补问题的算法不断涌现。互补问题可以分为线性互补问题和非线性互补问题。对互补问题的研究又可以分为理论和算法。前者主要研究问题解的存在性、唯一性、稳定性以及灵敏度分析等性质。后者集中研究如何构造有效算法及其理论分析。本文旨在有效算法方面的研究。本篇文章主要介绍线性互补问题基本概念、算法；二次规划问题基本概念、理论。重点探讨二次规划问题与线性互补问题的关系，以及如何利用二次规划的方法求解线性互补问题。关键词：线性互补问题，二次规划，算法，互补问题和二次规划的关系翻译对应着摘要改 abstractthe theory and algorithm of the linear complementary problem (lcp) is widely used in mathematics programming and. as lcp is related to nonlinear scientific knowledge and many practical problems, the theory and algorithm of the lcp was a hot task since 20th 60, and many algorithms about lcp were generated.the research of the lcp included theory and algorithm. the former include existence, uniqueness and stabilize of the problem. the later was concentrate on how to construct efficient algorithm and the analysis about the theory. in this paper we were mainly talking about the algorithm of lcp.in this paper, we were mainly introduced the basic conception and algorithm of lcp, and the basic conception and algorithm of quadratic programming problems.key words: linear complementary problem, quadratic programming problem, algorithm, theory, the relationship of lcp and qpp目录摘要1目录3引言4第一章：互补问题51.1 互补问题介绍51.2 互补问题的算法介绍8第二章：二次规划142.1 库恩塔克条件：142.2 二次规划14第三章：线性互补问题与二次规划问题173.1 用线性互补问题解决二次规划问题173.2 解线性互补问题的lemke方法183.3 用二次规划解决线性互补问题233.4 解二次规划问题的起作用集方法23第四章：应用举例论文总结27参考文献28致谢30引言互补问题是运筹学与计算数学的一个交叉研究领域。作为一类新的数学模型，互补问题首先是由著名运筹学家、数学规划的创始人g.b.dantzig和他的学生r.w.cottle于1963年提出，并很快引起了当时运筹学界和应用数学界的广泛关注和浓厚兴趣，许多人参与了这类问题的研究。由于与最优化、变分不等式、平衡问题、对策论、不动点理论等分支的紧密联系，以及在力学、工程、经济、交通等许多实际部门的广泛应用，互补问题越来越显示其重要性，这激励了人们对其理论与算法的进一步研究，出现了20世纪90年代以来的研究高潮。 互补问题的求解方法根据模型为线性和非线性分为两大类：(i)对线性互补问题，有直接方法(如lemke法，cottle-dentzig法)和迭代法(如mangsarian法)；(ii)对非线性互补问题，有不动点法，同伦法，投影法，newton法。在本文中，第一章，我们简要介绍互补问题和几个互补问题的经典算法；第二章我们介绍了二次规划问题的基本概念和kkt条件；第三章，旨在探究线性互补问题与二次规划的问题的关系,并在此基础上，讨论如何利用线性互补问题的方法求解二次规划问题、以及利用二次规划问题的方法求解线性互补问题。这也是本文的重点内容。第一章 互补问题1.1 互补问题介绍互补问题是运筹学与计算数学的一个交叉研究领域，与数学规划、经济学、对策论、力学、变分学、随机最优制等学科关系密切，在科学研究和工程技术各领域有着广泛的应用。互补问题自20世纪60年代开始发展到现在，无论在理论还是在算法研究上都取得了丰硕的成果。 互补问题的研究又可以分为理论和算法。前者主要研究问题解的存在性、唯一性、稳定性以及灵敏度分析等性质。后者集中研究如何构造有效算法及其理论分析。本文旨在有效算法方面的研究。 我们首先给出互补问题的定义：定义1.1（线性互补问题）：给定一个的矩阵，q是一个维向量，找到一个向量w和z使得： （1.1）； （1.2）； （1.3）在这里，表示一对互补向量。线性系统的一个解叫做互补问题可行解。另外，如果对变量都适合，是（1.1）和（1.2）的基可行解，则这个解也叫做互补问题可行基解。定义1.1（非线性互补问题）： 求一个p维向量x，使得：， （1.4）； （1.5） （1.6）其中，是：连续可微。互补问题与最优化问题关系密切，最优化中的许多问题都可以转化为互补问题求解，下面分别给出说明。（1）线性规划考虑原始线性规划问题： （1.7）其中：。它的对偶问题为： （1.8）设，分别是和的可行解，则，同为最优解的充要条件是：；设：，则：；在，同为最优解的条件下，可以构造如下的互补问题：求，使得，且。是的解当且仅当，是和的最优解。（2）二次规划考虑二次规划问题：其中，。引入松弛变量，使得。则由条件，存在向量乘子，使得：将上面的条件改写成如下形式：若令，则条件等价地可以写为：求，使得，且，而这正是线性互补问题的形式。（3）非线性规划考虑非线性规划其中连续可微，。令则由约束最优化的条件：将上面的式子展开写成：若令，则条件等价于：求，使得，且；这也是互补问题。1.2 互补问题的算法介绍我们简要介绍几个互补问题的经典算法和近几年的解互补问题的发展情况，对我们以后分析和解决互补问题有很大的帮助。主要有光滑方程法、可微的无约束优化法、glp投影法、内点法。1.光滑方程法：这类方法就是把互补问题转化为一个与之等价的光滑方程组，然后用newton类型法求解。mangasarian于1976年首先提出这种方程族（3）（4）这里是指的第个分量，是一个严格递增的函数，满足，称为函数或者势函数，mangasarian证明了两个重要结论：定理1： 假设由（4）定义，则；进一步，解。定理1： 假设解且在连续可微，如果下列条件成立（a）是非退化的，即；（b）在点的jacobian矩阵非奇异；（c）连续可微、严格递增，且当时，；那么，在点的jacobian矩阵非奇异。显然，满足定理2（c）的函数很多，例如光滑方程法：，此时的函数。于是我们可再生出许多光滑方程，并能用newton程序解之。当然，满足定理2条件的解点附近，算法有超线性收敛性。为了保证大范围收敛性，waston建立了一个同伦算法（取）。subbramanian则提出一个带阻尼因子的gauss-newton法（取），迭代格式为：；（5）这里为步长，由精确armijo搜索求得；，；表示适当维数的单位矩阵；。ferris和lucidi用非单调线性搜索技术改进程序(5)，得到好的数值结果最近本文第一作者和subramanian合作证明：在连续可微时，算法(5)是大范围收敛的；在定理2的条件下，其点列局部超线性收敛。基于函数(4)，kanzow考虑下面2n阶光滑方程组（6）他给出了jacobian矩阵在的非解点处存在逆的几个充分条件。显然，算法的大范围收敛性与水平集（7）的有界性有密切联系。对此，文64也做了研究。tseng则把（6）变成方程；（8）进而研究和的增长行为。虽然这类方法有一定的优越性。但缺点是， 即使一个线性互补问题，转化后的方程往往是非线性的，且非线性程度较高这就导致理论与计算的复杂化。下面的一类方法恰能弥补这一不足。2可微的无约束优化法这是把互补问题转化为一个与之等价的可微无约束优化问题，然后用某种大范围或newton类型法求解由于无约束优化法较为成熟，因此，对这类方法的研究重心在于如何转化上。mangasarian和solodov又先于他人，给出一个可微的势函数这里表示2-范数。 称为隐lagrange函数。他们证明了定理6 对，且解实际上， 可由可微的函数；并取向量1-范数生成，即文7研究了稳定点与极小点之间的关系，得到定理7 假设f是可微的，且正定，则是(17)的稳定点是的一个解。文8的9做了统一处理。基于fukushimp的结果，中国科学院计算数学所青年学者彭积明10给出了变分问题的可微无约束优化再生。有趣的是，它恰是隐lagrange函数在变分问题中的推广。 自此至今的三年间， 出现了构造函数热。关于这个方向的综述，可见fukushima的文章11最近，对可微无约束优化再生的研究兴趣转向增加非负约束，因为实际计算表明，仅用无约束优化求出的的解并不理想。为此给出一个可行的信赖域方法；提出一降势内点法。这方面的文献陆续增多，有12，13等3glp 投影法就是基于goldsteinlevitin-polyak求解凸规划的梯度投影法思想，求解互补问题。基本迭代格式为这里 为步长。然而它的收敛性需要是强单调的假设。为此， korpelevich(1976)提出外梯度法， 即它的收敛性仅要求单调且解集。sun14,15应用armijo搜索技术得到，在是伪单调且的假设下，迭代点列收敛到。虽然这类方法最多只有线性收敛速度，但它运算量小，存储量小，保稀疏性。因此近几年又有新的发展。4内点法这是把互补问题转化为一个与之等价的非负约束方程组，然后用newton类型法求解。它的研究起源于karmarkar的求解线性与凸二次规划的内点法，也是这种方法的自然延伸。其研究高潮在1990年前后，至今取得极大成功。这方面的文献很多很多，大都集中在杂志siam joptimization， mp， jota， math.operres上。 现在来考察内点法的基本思想。令，则互补问题(1)可转化为：这里。显然， (24)是一个带有非负约束的2n阶非线性方程组。当时，仅第二个方程是非线性的，且有特殊形式的表达式。容易证明， 当是函数时， jacobian矩阵是非奇异的。 因此，在迭代中可取newton方向傲为搜索方向。给定点，内点法的一般迭代格式为： (25) (26)这里是由经过一个微小扰动而得，其目的是调节迭代的收敛速度；为步长，它的取法使新点，且效益函数有一定量的下降。如果在迭代过程中能保证，则称为可行内点法； 否则称为不可行内点法。如果取的自然势函数作为效益函数，则称为路径跟踪法；如果取某种对数函数作为效益函数，则称为降势函数法。对于可行内点法，它首先由kojima，mizuno和yoshise提出,限于篇幅，不再一一举例。内点法的收敛结果大致有：(1)大范围收敛性：若单调，可行集存在内点，那么由内点法产生的迭代点列满足且q-线性(2)局部超线性收敛：假设单调且可行集存在内点若是的一个极限点且有某种正则性，则或者超线性收敛于零或。(3)多项式复杂性若单调且可行集存在内点，那么对可行内点法，最好的复杂性界为；对不可行内点法，最好的复杂性界为。总之，关于1994年以前内点法的情况，请见新书16。这三年，关于内点法的文章不多，在此仅向读者推荐几篇文献 bonnans和gonzaga17证明了求解内点法的迭代点列收敛性。 sun和zhao18，19提出了一个求解的长步内点法，它仅用一次newton步可得到局部二次收敛性。 tseng20借用非内点法的思想改进中心路径邻域，并引进积极约束集策略，使算法的局部超线性收敛性不需要严格互补条件。目前，人们正在发展用内点法求解半定线性规划。第二章 二次规划2.1 库恩塔克条件：在介绍二次规划之前，我们先引入条件，因为库恩塔克 条件是非线性规划领域中最重要的理论成果之一，是确定某点为最 优点的必要条件。只要是最优点，就必要满足这个条件。但一般说，它并不是充分条件，因而满足这个条件的点不一定是最优 点（对于凸规划，它既是最优点存在的必要条件，同时也是充分条件）。库恩塔克 条件的叙述如下：设是非线性规划的极小值点，而且在点的各起作用约束的梯度线性无关，则存在向量，使下列条件成立： （2.1）条件（2.1）称为条件。满足这个条件的点（它当然也满足非线性规划的所有约束条件）称为点。2.2 二次规划若某些非线性规划问题的目标函数为自变量的二元函数，约束条件又全是线性的，就成这种规划为二次规划问题。二次规划为是非线性规划中比较简单的一类，比较容易求解。由于很多方面的问题都可以抽象为二次规划的模型，而且它和线性规划又有直接联系，因而我们此处专门提出来说明一下。二次规划的数学模型可表述如下：（2.1）式的右端的第二项为二次型。如果该二次型为正定（或者半正定），则目标函数为严格凸函数（或者凸函数）；此外，二次型的可行域为凸集，因而，上述规划属于凸规划（在极大值问题中，如果上述二次型为负定或半负定，则也属于凸规划）。在文献【运筹学】中第六章已经指出，凸规划的局部极值即为其全局极值。对这种问题来说，条件不但是极值点存在的必要条件，而且是充分条件。将条件的第一个条件应用于二次规划（2.2）（2.4）中，并用y代替条件中的，即可得到在（2.3）式中引入松弛变量，（2.3）式即变为（假定）：再将条件的第二个条件应用于上述二次规划，并考虑（2.6）式，这样就得到：此外还有：联立（2.5）式和（2.6）式，如果得到的解也满足（2.7）式和（2.8）式，则这样的解就是原二次规划问题的解。但是，在（2.7）式，可能为正，也可能为负。为了方便于求解，先引入人工变量（，其前面的符号可以取正或负，以便得出可行解）。这样（2.5）式就变成了：其中是符号函数，当时，；当时，。这样一来，可立即得到初始基本可行解如下：但是，只有当时才能得到原来问题的解，故必须对上述问题进行修正，从而得到如下线性规划问题：该线性规划尚应满足（2.7）式。这相当于说，不能使和（对于每一个）同时为基变量。解线性规划问题（2.10），若得到最优解：则就是原问题的最优解。第三章 二次规划问题与线性互补问题3.1 利用线性互补问题求解二次规划问题现在考虑二次规划问题（3.1）其中h是n阶对称矩阵，c是n维列向量，a是矩阵，b是m维列向量。引入乘子y和u，定义lagrange函数（3.2）再引入松弛变量，使得（3.3）这样根据（3.2）式，可将问题（3.1）的条件写成（3.4）记：， ，于是，（3.4）式可以写成下列形式：（3.5）（3.6）其中w，z，q均为维列向量，m是维矩阵。（3.5）和（3.6）合称为线性互补问题，它的每一个解都具有这样的特征：解的个分量中，至少有个取零值，而且其中没对变量中至少有一个为零，其余分量均是负数，下面研究怎样求出线性互补问题的解。定义3.1 设是（3.5）式的一个基本可行解，而且每个互补变量对中有一个变量是基变量，则称互补基本可行解。这样，求二次规划点的问题就转化为求互补基本可行解。3.2 求解线性互补问题的lemke方法现在介绍求互补可行解的lemke方法。我们分两种情形讨论：（1） 如果，则就是一个互补基本可行解。（2） 如果不满足，则引入人工变量，令其中是分量全为1的维列向量。在求解（3.7）（3.9）式之前，先引入准互补基本可行解的概念。定义3.2 设是（3.7）、（3.8）、（3.9）式的一个可行解，并且满足下列条件，则称是准互补基本可行解。（1）是（3.7）和（3.8）的一个基本可行解；（2）对某个，和都不是基变量；（3）是基变量，每个互补变量对中恰好有一个变量是基变量。下面用主消去法求准互补基可行解。首先，令；则是一个准互补基本可行解，其中和式基变量，其余变量为非基变量。以这个解为起始解，用主元消去法求新的准互补基本可行解，力图用这种方法迫使变为非基变量。为了确保可行性，选择主元时要遵守下面两条规则：（1） 若（或者）离基，则（或者）进基；（2） 按照单纯形法中的最小比例规则确定立即变量。这样就能实现从一个准互补基本可行解到另一个互补基本可行解可行解的转换，直至得到互补基本可行解，即变为非基变量，或者由（3.7）、（3.8）、（3.9）式所定义的可行域无界的结论。lemke方法的计算步骤：计算步骤如下：（1） 若，则停止计算，就是一个互补基本可行解；否则，用表格形式表示方程组（3.7），设取s行为主行，为对应的主列，进行主元消去，令。（2） 设现在行列表中变量下面的列为。若，则停止计算，得到（3.7）式和（3.8）式的可行域的极方向；否则，按最小比例值规则确定指标r，使：；（3） 设r行的基变量为或者（对于某个），变量进基，以r行为主行，对应的列为主列，进行主元消去。如果离基变量是，则令；如果离基变量是，则令。转到步骤（2）。（4） 变量进基，离基。以r行为主行，对应的列为主列，进行主元消去，得到互补可行解，停止计算。3.3 利用二次规划求解互补问题考虑互补问题：求一个p维向量x，使得：； （3.10）， （3.11） （3.12）其中，m是p阶对称矩阵，q是p维向量；是：连续可微。二次规划问题（3.13）比较两者可以明显看出有以下结论：因为，（3.13）中约束条件保证二次规划问题一定存在最优解，但是，当最优解f*0时，线性互补问题无解，当f*=0，则线性互补问题一定有解。因此，对于线性互补问题就可以转化为讨论二次规划的问题。然后，下面我们再介绍一下二次规划的简单的算法起作用集解法。3.4 解二次规划问题的起作用集方法1. 起作用集方法的分析推导：考虑具有不等式约束的二次规划问题：（3.14）其中是n阶对称正定矩阵，c是n维列向量，a是矩阵，秩为m， b是m维列向量，。由于不等式约束的出现，问题（3.14）不能直接使用消元法和lagrange方法求解。解决这个问题的策略之一，是起作用集方法将它转化为求解等式的约束问题。设在地k次迭代中，已知可行点，在该点起作用约束集用表示。这时需要求解等式约束问题（3.15）其中表示矩阵a的第i行。也是在处起作用约束函数的梯度。为方便起见，现将坐标原点移至，令则：（3.16）于是问题（3.15）就变成求校正量的问题（3.17）解二次规划问题（3.17），求出最优解，然后区别不同情形，决定下面应采取的步骤。如果是可行点，且，则在第次迭代中，已知点取作如果不是可行点，则列方向并沿搜索，令；现在分析怎样确定沿方向的步长。根据保持可行性的要求，的值应使得对于每一个成立（3.18）由于是可行点，因此由上式可知，当时，对于任意的非负数，（3.18）总成立；当时，只要取正数对于每一个，（3.18）总成立。记由于是问题（3.17）的最优解，为在第k次迭代中得到较好的可行点，应取（3.19）并令如果（3.20）则在点，有因此，在处，为起作用约束。这时，把指标p加入，得到在的起作用约束指标集。如果，则是问题（3.15）的最优解。这时应判断是否为问题（3.14）的最优解。为此，需用（3.20）式计算起作用约束乘子。如果这些，则是问题（3.14）的点。由于（3.14）是凸规划，因此是问题（3.14）的最优解。如果存在，使得，则不可能是最优解。可以验证，当时，在处存在可行下降方向。比如，是起作用约束系数矩阵，且满秩，令方向是单位向量，对应下标q的分量为1，则有因此d是在处的下降方向。容易验证d也是可行方向。当时，把下标q从中删除。如果有几个乘子同时为负，令将对应的约束从起作用约束集中去掉，再解问题（3.17）2. 起作用约束集方法计算步骤计算步骤如下：（1） 给定初始可行点，相应的起作用约束指标集为，置（2） 求解问题（3.17），设其最优解为。若，则进入步骤（5）；否则，进行步骤（3）（3） 令，由（3.19）式确定，令，计算式。（4） 若，则置，返回步骤（2）；若，记点处起作用约束指标集为，置，进行步骤（5）（5） 用（3.20）式计算对于起作用约束的lagrange乘子，设若，则停止计算，得到最优解；否则，从中删除q，返回步骤（2）。 第四章 应用举例例1.用lemke方法求解下面例题：解：有题意可得：，；线性互补问题为：引入人工变量，建立下表： 1 0 0 0 0 0 1 1 -1 0 1 0 0 0 0 -1 2 -10 0 1 0 -1 1 -2 2 -10 0 0 1 -1 -2 2 -4 22-2-6因为，所以，主元，已经用方括号括起来，经主元消去得到： 1 0 0 -1 1 2 -1 5 0 0 1 0 -1 1 2 -3 6 00 0 1 -1 0 3 -4 00 0 0 -1 1 2 -2 4 18846在这里， 进基，离基，进入下一迭代，得到下表： 1 0 1 0 0 0 1 -1 0 1 -1 1 0 00 0 0 1 00 0 1 0 0 12，根据最小比例规则，进基，离基；进入下一迭代，得到下表： 0 1 1 1 0 1 0 这里，根据最小比例规则，进基，离基，最终得到下表结果， 0 0 1 1 0 1 0 0 1 0 1 得到互补基本可行解：因此可以得到二次规划问题的最优解为。例2. 用起作用集方法方法求解下面例题：论文总结互补问题是运筹学与计算数学的一个交叉研究领域。作为一类新的数学模型，互补问题首先是由著名运筹学家、数学规划的创始人g.b.dantzig和他的学生r.w.cottle于1963年提出，并很快引起了当时运筹学界和应用数学界的广泛关注和浓厚兴趣，许多人参与了这类问题的研究。由于与最优化、变分不等式、平衡问题、对策论、不动点理论等分支的紧密联系，以及在力学、工程、经济、交通等许多实际部门的广泛应用，互补问题越来越显示其重要性，这激励了人们对其理论与算法的进一步研究，出现了20世纪90年代以来的研究高潮。本篇文章主要介绍线性互补问题及其算法。首先，本文简要给出线性互补问题基本概念、若干个经典算法；二次规划问题基本概念和最优性理论；重点探讨二次规划问题与线性互补问题的关系，以及如何利用二次规划的方法求解线性互补问题。自己可以再加些内容参考文献1 运筹学教材编写组.运筹学（修订版）.北京：清华大学出版社，19902 陈宝林，最优化理论与算法（第2版）.清华大学出版社.20053 rockafellar, r. t. c onvex analys is. princeton univ. press,princeton, 19704 isac g. complementarity problems. lecture notes in matheanatics, springer-verlag, berlin, 1992.5 cottle r w, pang j s and stone r ethe linear complementary problem. academic press, boston. 1992.6 kangow c, yamehita n and fukushima m. new ncp-functions and their properties. jota, 1997, 94, 115-1357 yamashita nand fukushima mon stationary points of the implicit lngrangian for nonline complementaftty problems jota 1995，84：653-6638 kanzow cnonlinear complementaxity aunconstr2med optimization jota，1996，88(1)：139-1559 tseng yamashita n and fukushima m equivalence of complementarity pro blems to diferentiable minimization：a unified approachsiam optimization,to appear10 pei1g j m equiw lece of variational inequality problem s to unconstrained optimization technical report，state key laboratory of scientific and engineering computing，academia sinicabeijing，china，1995，to appearin math preforming11 fukushima merit function for wriational inequality and complementarity problems in diplilog and giannessl feds nonlinear clptimizntion and applications plenum press，new york，1996，155-17012 peng j m derivative-free methods for monotone variational inequality and complementarity problems technical report1 state key laboratory of scientific and engineering computing academia sinica，bering china，199713 solodov m v-stationary points of bound constrained minimization reform ulations of complementaity problemsjota 199794：11513214 sun d-a new step skill fur solving a class of nonlinear projection eqttations jcoput math，1995，13(4)：357-36815 sun algorithms and convergence analysis for nonsmooth optimization and nonsmooth equations ph d thesis，institute of applied math，academia sinica beijing china，199516 nesteroy and nemirovskii interior point polynomial algorithm in convex programming siam publications，philadelphiapausa，199417 bonnans jf and gonzngaconvergenceo finite pointal gorithm for the monotone linear complementarity problem math res，1996 21：1-2518 sun j and zhao g aquad ratically converg