Comparison of Two Reformulation-Linearization Technique Based Linear Programming Relaxations for Polynomial Programming Problems

In this paper, we compare two strategies for constructing linear programmingrelaxations for polynomial programming problems using aReformulation-Linearization Technique (RLT). RLT involves an automaticreformulation of the problem via the addition of certain nonlinear impliedconstraints that are generated by using the products of the simple boundingrestrictions (among other products), and a subsequent linearization based onvariable redefinitions. We prove that applying RLT directly to the originalpolynomial program produces a bound that dominates in the sense of being atleast as tight as the value obtained when RLT is applied to the jointcollection of all equivalent quadratic problems that could be constructed byrecursively defining additional variables as suggested by Shor.     

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

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

A Self-Adaptive Projection and Contraction Method for Linear Complementarity Problems

In this paper we develop a self-adaptive projection and contraction method for the linear complementarity problem (LCP). This method improves the practical performance of the modified projection and contraction method in [10] by adopting a self-adaptive technique. The global convergence of our new method is proved under mild assumptions. Our numerical tests clearly demonstrate the necessity and effectiveness of our proposed method.     

Multisplitting and Schwarz Methods for Solving Linear Complementarity Problems

In this paper we consider some synchronous and asynchronous multisplitting and Schwarz methods for solving the linear complementarity problems. We establish some convergence theorems of the methods by using the concept of M-splitting.     

A Projected Algebraic Multigrid Method for Linear Complementarity Problems

We present an algebraic version of an iterative multigrid method for obstacle problems, called projected algebraic multigrid (PAMG) here. We show that classical algebraic multigrid algorithms can easily be extended to deal with this kind of problem. This paves the way for efficient multigrid solution of obstacle problems with partial differential equations arising, for example, in financial engineering.     

多值单调算子的隐补问题

在Banach空间中引入了多值算子的隐补问题和相补问题的新概念，并证明了多值单调算子隐补问题和相补问题解的存在性定理。     

对称线性互补问题的乘性Schwarz算法

本文提出了求解对称性互补问题的乘性Schwarz算法,其中子问题用投影迭代方法求解.利用投影迭代算子的性质及投影迭代的收敛性,证明了算法产生的迭代点列的聚点为原互补问题的解,并在一定条件下,证明算法产生的迭代点列的聚点存在.     

Two-Step Modulus-Based Synchronous Multisplitting Iteration Methods for Linear Complementarity Problems

To reduce the communication among processors and improve the computing time for solving linear complementarity problems, we present a two-step modulus-based synchronous multisplitting iteration method and the corresponding symmetric modulus-based multisplitting relaxation methods. The convergence theorems are established when the system matrix is an $H_+$-matrix, which improve the existing convergence theory. Numerical results show that the symmetric modulus-based multisplitting relaxation methods are effective in actual implementation.     

A Null Space Approach for Solving Nonlinear Complementarity Problems

In this work, null space techniques are employed to tackle nonlinear complementarity problems （NCPs）. NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm.     

关于隐补问题的两个结果

本文在Banach空间中证明了隐补问题解的存在性定理．     

The Monotonicity of the Linear Complementarity Problem

The monotonicity of the linear complementarity problem (LCP) is discussed in this paper. Both the monotone property about the single element of the solution and the monotone property of the whole solution are presented. In order to illustrate the results, some corresponding numerical experiments are provided.     

Error Estimation for Nonlinear Complementarity Problems via Linear Systems with Interval Data

For the nonlinear complementarity problem, we derive norm bounds for the error of an approximate solution, generalizing the known results for the linear case. Furthermore, we present a linear system with interval data, whose solution set contains the error of an approximate solution. We perform extensive numerical tests and compare the different approaches.     

基于m进制隐枚举法的特殊约束指派问题最优解特点研究

给出了该类问题的数学模型,其约束的特殊性表现在被指派的资源数量必须在给定的范围内,因而不同于一般非平衡指派问题;运用m进制运算规则将二维解矩阵转化为一维解向量,减少解组合的数量,据此用隐枚举法求得问题的最优解。通过对多个算例的求解,找出了该问题最优解的两个特点。这些特点可为求解大规模该问题的智能算法提供有益的帮助。     

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.     

Computation of Error Bounds for P-matrix Linear Complementarity Problems

We give new error bounds for the linear complementarity problem where the involved matrix is a P-matrix. Computation of rigorous error bounds can be turned into a P-matrix linear interval system. Moreover, for the involved matrix being an H-matrix with positive diagonals, an error bound can be found by solving a linear system of equations, which is sharper than the Mathias-Pang error bound. Preliminary numerical results show that the proposed error bound is efficient for verifying accuracy of approximate solutions. This work is partly supported by a Grant-in-Aid from Japan Society for the Promotion of Science.     

Existence Theorems for Linear Complementarity Problems on Solid Closed Convex Cones

In this paper, we establish some existence results for linear complementarity problems on closed convex cones under generalized monotonicity assumptionsThe authors are grateful to the referees for detailed comments and suggestions on an early version of the paper     

二阶锥线性互补问题内点法的复杂性

本文提出一个二阶锥线性互补问题的长步原始对偶内点法,搜索方向由一个一般的核函数来定义.如果给出初始的严格内点,可以得到本算法的复杂性为O((1+2k)llog(lμ0/ε)).     

一类非单调互补问题的Canonical对偶问题研究

对于一类具有广泛应用背景的非单调互补问题,我们构建了这类问题的Canonical对偶问题。其对偶问题可以写成和原问题类似的互补问题。我们给出了对偶问题和原问题解之间的对偶关系,并且将对偶问题转化成一个一维优化问题,这不但可以方便的求解这类问题,也为研究这类问题性质提供了一个非常直观的研究工具。最后,本文给出了几个算例来演示对偶问题的性质。     

EP Theorem for Dual Linear Complementarity Problems

The linear complementarity problem (LCP) belongs to the class of -hard problems. Therefore, we cannot expect a polynomial time solution method for LCPs without requiring some special property of the matrix of the problem. We show that the dual LCP can be solved in polynomial time if the matrix is row sufficient; moreover, in this case, all feasible solutions are complementary. Furthermore, we present an existentially polytime (EP) theorem for the dual LCP with arbitrary matrix. The research of Tibor Illés and Marianna Nagy has been supported by the Hungarian National Research Fund OTKA T 049789 and by the Hungarian Science and Technology Foundation TéT SLO-4/2005. Tamàs Terlaky has been supported by an NSERC Discovery grant, MITACS and the Canada Research Chair program.     

Solvability of Implicit Complementarity Problems

In this paper, a new notion of exceptional family of elements (EFE) for a pair of functions involved in the implicit complementarity problem (ICP) is introduced. Based upon this notion and the Leray–Schauder Alternative, a general alternative is obtained which gives more general existence theorems for the implicit complementarity problem. Finally, via the techniques of continuous selections, these existence theorems are extended to the multi-valued implicit complementarity problems (MIPS).