摘要 互补问题与数学规划、经济学、对策论、力学、变分学、随机最优制等学科关系密切，在科学研究和工程技术各领域有着广泛的应用。从二十世纪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阶非线性方