广义线性互补问题的区间解法

《广义线性互补问题的区间解法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章绪论rlliq+Mz≥o，z>O，Zi兀(gf+Miz)J=o，i=1，．．．，，z，j=l简记为UZC*'(M，g)。如果对每一个f有％=1，那么VLCP退化为线性互补问题。1．2．3广义线’I!tg}l、问题(皿CP(必。，M：，D)设矩阵M。，M：∈R““，PcR”是一多面体，广义线性互补问题就是，求解向量XER”，Y∈R“满足^少一^缸∈P,x≥O，Y≥0，．，J，=0，简记为ELCP(Ml，M2，尸)。当m司，P=例时，ELCF'(M。，M2，尸)化为线性互补问题。1．2．4混幂口线性互枣卜问题(MCP)设么

2、，君分别为n阶，m阶的方阵，且给定C∈彤“，D∈R””，a∈Rn,b∈R”，那么混和线性互补问题就是，求解向量U∈F，1，∈R”，使得其满足简记为MCP。口+Au+C、，=O，b+Du+Bv=O，v≥O，1，r(6+D“+曰v)=0，1．2．5隐线性互补问题设A∈R～，口∈F，h：R”jR”，那么隐线性互补问题即求解向量z∈R”使得a+Az芝O，z≥O，(口+止)r(z—Jil(z))=0．显然，当h鄙时，隐线性互补问题转化为LCP。电子科技大学硕士学位论文1．2．6非线性互补问题非线性互补问题就是，求解向量Z∈R”使得z≥

3、0，f(z)≥0，Zrf(z)=0．简记为NCP。显然，线性互补问题是非线性互补问题的一种特殊形式。1．3线性互补问题的应用如二次规划minilllize厂(功=crz+i1工r@subjecttoAx≥b(1—1)x≥0当Q∈R“”是对称的，C∈R”，A∈R雕”且6∈R”。特别地，若Q=0，N---次规划将化为线性规划。如果x是规划(1．1)的局部最优解，ig／z,存在一个向量Y满足以下条件“：：-簪bA么x冀0’嚣麓。0：m2，1，=+≥0，1，≥O．y1v=．、7则有，条件(1—2)定义了LCP(M，q)，其中膨=[”

4、A∥0]，g槲bf。‘I—另外一种特殊的二次规划形式是X有非负的限制，那么(1．1)就可以简化为1ni枷ze厂(工)=crz+昙石r@subjectto石≥0(1-3)当Q是半正定矩阵，那么(1-3)就完全等价于LCP(Q，c)。也就是对任意Q，LCP(Q，c)等价于(1-3)式这种稳定点问题。形如(3)这种类型的I'口-J题大量地出现在工程和物理4第一章绪论科学中。LCP在解决此类问题中起到了很大的作用。此外，双矩阵对策、市场平衡、最优停止点问题、平面中的凸包闯题都与LCP有着密切的关系。因此，可以通过把原问题转化为较易求

5、解的LCP来寻求原问题的解。相应的，可以看出，LCP的发展对很大一部分与LCP有密切关联的问题有相当大的促进作用。1．4线性互补问题解的存在性在线性互补问题中第一个遇到的就是有没有解的问题，自然引起了很多学者的关注。解的存在性问题最早应该是Samelson，Thrall和Wesler在1958年的文献中提到的。系统矩阵膨为尸矩阵，是对于任意的向量q，LCP(M，q)都有唯一解的充要条件。这个结果可以说是LCP经典的结果，随后很多对LCP的研究都是基于这个结果的。由此也可以看出，LCP涉及到很多矩阵的相关知识。在实际研究过程中

6、，对不同条件下的系统矩阵必，问题的结果大多会很不相同，或者在研究其它方面的问题时对M有一些限制条件。特别地，线性互补问题与P矩阵，即所有主子式为正的矩阵，有着不可分割的联系。1．5本文的主要工作本文从几个方面研究了有关线性互补问题，首先是迭代法，如AOR，MAOR，GAOR，两阶段迭代法等，接着介绍了一些迭代法的误差界的范围。主要研究了广义线性互补问题，得到一种可利用计算机高速运算能力的区间迭代法，推广了基本线性互补问题的区间迭代法，得到很好的收敛效果。电子科技大学硕士学位论文第二章线性互补问题的迭代解法最早的迭代法解线性互

7、补问题出现在19世纪五十年代，一直发展至今。迭代法在解决大型线性系统方面有着很大的优势。对线性互补问题迭代解法的早期研究主要是针对对称问题和在非负约束凸二次规划中的应用。Hildreth在1954年和1957年用映射的松弛Gauss．Seidel方法解决严格凸二次规划问题仅仅使用了不等式约束，他的方法事实上是解决了对偶问题，这恰恰是与线性互补问题等价的。但是当时却没有认识到。经过几十年的发展，众多学者把线性系统的迭代方法应用在解决线性互补问题上，取得了出色的成果。在1977年Mangasarian发表了一个解决LCP的一般方

8、法，并且在一定约束条件下建立了其收敛性。这一文章可以认为是在求解LCP的迭代法中的对称性研究的第一篇文章。从此以后，激发了很多学者来关注这个问题。因为线性互补问题可以等价的转化成线性方程组等线性系统的形式，所以，在这一问题的研究过程中，很多都是从解决线性系统的思路中引用过来并加以扩展。2．