大型稀疏线性互补问题的行作用法

且引言考虑线性互补问题＊＊P（q，M）：求X二（X；，x。，…，x。厂E”使得x＞O，训x）E＊x＋g＞o，／U（X）一O（1）其中M一（m；。）为nXn矩阵（不必对称），q一切，q。，…，q。）rER“为给定常向量．通常情况下已有求解LCP（q，M）的若干著名算法［‘－’j．本文提出求解LCP（q，M）的一种新算法一行作用法，方法具有如下特点：（i）每次迭代只需n个简单的投影运算，每次投影只涉及矩阵M的一行；（n）生成新的迭代点x‘“‘时只利用前次迭代点／；（iii）对矩阵M不实施任何整体运算．因而适合于求解大型（巨型）稀疏问题，且…     

线性互补问题的一个正则互补模型

正1引言线性互补问题的一般形式为z~TF(z)=0,F(z):=Az+q≥0,z≥0,(1)简记为LCP(A,q),其中A∈R~(n×n),q∈R~n已知,z∈R~n为所求.线性互补问题最早产生于求解非线性规划问题时所需要的KKT优化条件.随着科学的发展,线性互补问题在经济和工程方面出现比较多,参见[1,2,3,4]等.几十年来,线性互补问题LCP(A,q)得到很多学者的重视,在此研究领域有丰富的成果,参见文献[5,6]及其中参考文献.对于任意的q,线性互补问题LCP(A,q)都存在唯一解的充分必要条件是A具有各阶正主子式.这类矩阵称为P-矩阵,如正定矩阵和H_+-矩     

B-矩阵线性互补问题的误差界估计

正1引言线性互补问题在诸多领域具有广泛的应用,如二次规划、市场均衡、最优停步、双矩阵对策等~([1-3]),线性互补问题的数学模型为求x∈R~n,满足(Mx+q)~Tx=0,Mx+q≥0,x≥0,记作LCP(M,q),其中M=(m_(ij))∈R~(n×n)和q∈R~n为给定的矩阵和向量.线性互补问题解的性质主要取决于所定义矩阵的性质.例如,当矩阵是P-矩阵(即它     

解一类线性互补问题的区间方法

1引言线性互补问题简记为LCP(M,q)是指对给定的n×n阶实方阵M和N维实向量q,求满足下列条件的实向量x：x≥0,Mx q≥0,(1．1) x~T(Mx q)=0．它在工程物理、管理学、经济学、约束最优化等领域有着广泛的应用背景．备受人们关注     

矩阵方程X+A~*X~(-q)A=I(q>0)的Hermite正定解

1.引言 本文研究矩阵方程 X+A*X-qA=I (1)的Hermite正定解,其中I是一个n×n阶单位矩阵, A是一个n×n阶复矩阵, q是实数且q>0.q=1,q=2时的方程是从动态规划,随机过滤,控制理论和统计学中推导出来的,最近已有许多人对此进行了研究(见参考文献[1,2,4]),本文我们将研究方程(1)的解的存在性和解的性质,并讨论迭代求解及迭代解的收敛性. 对于Hermite矩阵X和Y,文中X≥Y表示X-Y是半正定的,X>y表示X-Y是正定的;对于方阵M,M*表示M的共轭转置,ρ(M)表示M的谱半径,λi(M)     

关于线性互补问题解的存在性

讨论线性互补问题解的存在性。证明关于解的唯一性定理。用反例表明:对于线性互补问题解的存在性,"M是半正定矩阵"既不是充分条件,也不是必要条件。     

Whc114研究的一些进展

杨之先生在[1]中提出了如下证解课题：Whc114M于二阶非常系数线性递归数列应选择百种有价值的，研究它的通顶公式和性质．本文将对数列（1）的通顶公式进行探讨，获据了一些有趣的结果．定理1如果存在数列｛a。｝、｛｝，使得那么二阶非常采数线性递归数列（1）的通项因之，当n＞4肘（3）成立．当n—3的（3）贵然成立，从而（3）得证．证毕．推论在定理1的到提下（I）如果a。一a（常数），那么（1）的通顶作为推进的一个有趣应用，我门合命题1对于数列（a。｝证在推进Z（D）中，置a。一n，p。＋；一p③一个自然的问题是：怎样的户（n）、q…     

关于矩阵方程X+A*X-1A=P的解及其扰动分析

考虑非线性矩阵方程X＋A^＊（X^-1）A=P其中A是n阶非奇异复矩阵,P是n阶Hermite正定矩阵．本文给出了Hermite正定解和最大解的存在性以及获得最大解的一阶扰动界,改进了文[5,6]中的部分结论．     

线性互补问题的一类新的带参数价值函数的阻尼牛顿法

本文给出了线性互补问题LCP(q ,M)的一类新的带参数光滑价值函数 ,基此价值函数提出了一种阻尼牛顿类算法 ,并证明了当M为P 矩阵时 ,该算法全局收敛且有限步终止 .通过数值实验说明了该算法高效可靠 .与互补问题的磨光方程组中所采用的带参数价值函数不同 ,这里的参数最终并不趋向于零 ,而是趋向于被称作解的乘子向量 (与凸非线性极小极大问题的Lagrange乘子完全一致 ) ,这一思想是本文作者首次提出来的 ,同时本文中所采用的阻尼牛顿类方法也有其独到之处 ,在互补问题的研究中有进一步发展的潜力     

Ax=b在广义正定矩阵类中的反问题求解

有许多类直接控制系统的绝对稳定性[1]涉及到这样一类线性方程组协Ax＝b的反问题：对于给定的x，b∈Rn，n阶实矩阵类Ⅱ（n），求解集Ⅰ（Ⅱ（n）；x，b）＝｛A∈Ⅱ（n）｜Ax＝b｝非空的条件．文[2]讨论了反问题Ⅰ（Ps（n）；x，b）≠（Ps（n）为正定降类）和Ⅰ（O（n）；x，b）≠（O（n）为正交阵类）的条件，文[3]进一步给出了Ⅰ（M-阵类；x，b）和Ⅰ（S-阵类；x，b）有解的条件．本文将研究这类反问题在更广的一类矩阵类─—广义正定矩阵[4，5]类中的求解，从而使这类反问题得到了较完满的解决．     

Exceptional Families and Existence Theorems for Variational Inequality Problems

This paper introduces the concept of exceptional family for nonlinear variational inequality problems. Among other things, we show that the nonexistence of an exceptional family is a sufficient condition for the existence of a solution to variational inequalities. This sufficient condition is weaker than many known solution conditions and it is also necessary for pseudomonotone variational inequalities. From the results in this paper, we believe that the concept of exceptional families of variational inequalities provides a new powerful tool for the study of the existence theory for variational inequalities.     

Exceptional family and solvability of copositive complementarity problems

In this paper, by extending the concept of exceptional family to complementarity problems over the cone of symmetric copositive real matrices, we propose an existence theorem of a solution to the copositive complementarity problem. Extensions of Isac–Carbone?s condition, Karamardian?s condition, weakly properness and coercivity are also introduced. Several applications of these results are presented, and we prove that without exceptional family is a sufficient and necessary condition for the solvability of pseudomonotone copositive complementarity problems.     

Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem

This paper deals with the LCP (linear complementarity problem) with a positive semi-definite matrix. Assuming that a strictly positive feasible solution of the LCP is available, we propose ellipsoids each of which contains all the solutions of the LCP. We use such an ellipsoid for computing a lower bound and an upper bound for each coordinate of the solutions of the LCP. We can apply the lower bound to test whether a given variable is positive over the solution set of the LCP. That is, if the lower bound is positive, we know that the variable is positive over the solution set of the LCP; hence, by the complementarity condition, its complement is zero. In this case we can eliminate the variable and its complement from the LCP. We also show how we efficiently combine the ellipsoid method for computing bounds for the solution set with the path-following algorithm proposed by the authors for the LCP. If the LCP has a unique non-degenerate solution, the lower bound and the upper bound for the solution, computed at each iteration of the path-following algorithm, both converge to the solution of the LCP.Supported by Grant-in-Aids for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.     

Exceptional Families of Elements for Continuous Functions: Some Applications to Complementarity Theory

Using the topological degree and the concept of exceptional family of elements for a continuous function, we prove a very general existence theorem for the nonlinear complementarity problem. This result is an alternative theorem. A generalization of Karamardian's condition and the asymptotic monotonicity are also introduced. Several applications of the main results are presented.     

A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties

In this paper, we construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system. The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge, such properties have not appeared in the existing literature for smoothing-type algorithms. This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

The extended linear complementarity problem

In this paper we define the Extended Linear Complementarity Problem (ELCP), an extension of the well-known Linear Complementarity Problem (LCP). We show that the ELCP can be viewed as a kind of unifying framework for the LCP and its various generalizations. We study the general solution set of an ELCP and we develop an algorithm to find all its solutions. We also show that the general ELCP is an NP-hard problem.This paper presents research results of the Belgian programme on interuniversity attraction poles (IUAP-50) initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture. The scientific responsibility is assumed by its authors.Supported by the N.F.W.O. (Belgian National Fund for Scientific Research).     

Exceptional Families of Elements for Optimization Problems in Reflexive Banach Spaces with Applications

In this paper, we propose a new notion of ‘exceptional family of elements’ for convex optimization problems. By employing the notion of ‘exceptional family of elements’, we establish some existence results for convex optimization problem in reflexive Banach spaces. We show that the nonexistence of an exceptional family of elements is a sufficient and necessary condition for the solvability of the optimization problem. Furthermore, we establish several equivalent conditions for the solvability of convex optimization problems. As applications, the notion of ‘exceptional family of elements’ for convex optimization problems is applied to the constrained optimization problem and convex quadratic programming problem and some existence results for solutions of these problems are obtained.     

Existence results for solutions of mixed tensor variational inequalities

By employing the notion of exceptional family of elements, we establish existence results for the mixed tensor variational inequalities. We show that the nonexistence of an exceptional family of elements is a sufficient condition for the solvability of mixed tensor variational inequality. For positive semidefinite mixed tensor variational inequalities, the nonexistence of an exceptional family of elements is proved to be an equivalent characterization of the nonemptiness of the solution sets. We derive several sufficient conditions of the nonemptiness and compactness of the solution sets for the mixed tensor variational inequalities with some special structured tensors. Finally, we show that the mixed tensor variational inequalities can be defined as a class of convex optimization problems.

     

Exceptional Family of Elements for a Variational Inequality Problem and its Applications

This paper introduces a new concept of exceptional family of elements (abbreviated, exceptional family) for a finite-dimensional nonlinear variational inequality problem. By using this new concept, we establish a general sufficient condition for the existence of a solution to the problem. Such a condition is used to develop several new existence theorems. Among other things, a sufficient and necessary condition for the solvability of pseudo-monotone variational inequality problem is proved. The notion of coercivity of a function and related classical existence theorems for variational inequality are also generalized. Finally, a solution condition for a class of nonlinear complementarity problems with so-called P _* -mappings is also obtained.     

Exceptional family of elements for generalized variational inequalities

This paper introduces a new concept of exceptional family of elements for a finite-dimensional generalized variational inequality problem. Based on the topological degree theory of set-valued mappings, an alternative theorem is obtained which says that the generalized variational inequality has either a solution or an exceptional family of elements. As an application, we present a sufficient condition to ensure the existence of a solution to the variational inequality. The set-valued mapping is assumed to be upper semicontinuous with nonempty compact convex values.