Equivalence of the Generalized Vertical Block Linear Complementarity Problems and Linear Complementarity Problems

In this paper, generalization of a vertical block linear complementarity problem associated with two different types of matrices, one of which is a square matrix and the other is a vertical block matrix, is proposed. The necessary and sufficient conditions for the existence of the solution of the generalized vertical block linear complementarity problem is derived and the relationship between the solution set of the generalized vertical block linear complementarity problem and the linear complementarity problem is established. It is proved that the generalized vertical block linear complementarity problem has the P-property if and only if the vertical block linear complementarity problem has the P-property.     

一类随机线性互补问题的求法

考虑一类随机互线性补问题的求解方法,目的是通过定义NCP函数来使正则化期望残差最小化.通过拟蒙洛包洛方法产生一系列观察值并且证得离散近似问题最小值解的聚点就是相应随机线性互补问题的期望残差最小值ERM,同时得到利用ERM到解为有界的充分条件.进一步证明ERM法能够得到具有稳定性和最小灵敏度的稳健解.     

求解线性互补问题的同伦方法

It is well known that a linear complementarity problem (LCP) can be formulated as a system of nonsmooth equations F(x) = 0, where F is a map from Rninto itself. Using the aggregate function, we construct a smooth Newton homotopy H(x,t) = 0. Under certain assumptions, we prove the existence of a smooth path defined by the Newton homotopy which leads to a solution of the original problem, and study limiting properties of the homotopy path.     

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.     

一个解决线性互补问题的新型神经网络

本文构造了一个新型的解决线性互补问题的神经网络,不同于那些运用罚函数和拉格朗日函数的神经网络,它的结构简单,易于计算,我们证明了该神经网络的全局收敛性和稳定性,并给出数值实验检验其有效性。     

Projected Splitting Methods for Vertical Linear Complementarity Problems

Journal of Optimization Theory and Applications - In this paper, we generalize the projected Jacobi and the projected Gauss–Seidel methods to vertical linear complementarity problems (VLCPs)...     

Linear Complementarity Problems on Extended Second Order Cones

In this paper, we study the linear complementarity problems on extended second order cones. We convert a linear complementarity problem on an extended second order cone into a mixed complementarity problem on the non-negative orthant. We state necessary and sufficient conditions for a point to be a solution of the converted problem. We also present solution strategies for this problem, such as the Newton method and Levenberg–Marquardt algorithm. Finally, we present some numerical examples.     

A Finite Algorithm for Almost Linear Complementarity Problems

We present an algorithm for solving a class of nonlinear complementarity problems called the almost linear complementarity problem (ALCP), which can be used to simulate free boundary problems. The algorithm makes use of a procedure for identifying an active index subset of an ALCP by bounding its solution with an interval vector. It is shown that an acceptable solution of the given ALCP can be obtained by solving at most n systems of equations. Numerical results are reported to illustrate the efficiency of the algorithm for large-scale problems.     

Modulus-Based GSTS Iteration Method for Linear Complementarity Problems

In this paper, a modulus-based generalized skew-Hermitian triangular splitting (MGSTS) iteration method is present for solving a class of linear complementarity problems with the system matrix either being an $H_+$-matrix with non-positive off-diagonal entries or a symmetric positive definite matrix. The convergence of the MGSTS iteration method is studied in detail. By choosing different parameters, a series of existing and new iterative methods are derived, including the modulus-based Jacobi (MJ) and the modulus-based Gauss-Seidel (MGS) iteration methods and so on. Experimental results are given to show the effectiveness and feasibility of the new method when it is employed for solving this class of linear complementarity problems.     

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.     

Toeplitz方程组极小范数最小二乘解的快速算法

给出了求以m×n阶Toeplitz矩阵为系数阵的线性方程组极小范数最小二乘解的快速算法.     

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

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

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.     

High Order Long-Step Methods for Solving Linear Complementarity Problems

The paper is concerned with methods for solving linear complementarity problems (LCP) that are monotone or at least sufficient in the sense of Cottle, Pang and Venkateswaran (1989). A basic concept of interior-point-methods is the concept of (perhaps weighted) feasible or infeasible interior-point paths. They converge to a solution of the LCP if a natural path parameter, usually the current duality gap, tends to 0.After reviewing some basic analyticity properties of these paths it is shown how these properties can be used to devise also long-step path-following methods (and not only predictor–corrector type methods) for which the duality gap converges Q-superlinearly to 0 with an arbitrarily high order.     

A Polynomial Interior-Point Algorithm for Monotone Linear Complementarity Problems

In this paper, we propose an interior-point algorithm for monotone linear complementarity problems. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full-Newton steps. Moreover, it is proven that the number of iterations of the algorithm coincides with the well-known best iteration bound for monotone linear complementarity problems.     

基于凝聚函数的互补问题的光滑化算法

对于不可微的"极大值"形式的函数,可以利用凝聚函数对其进行光滑逼近.借助这个技术,给出了求解线性互补问题的光滑方程组算法.首先是将互补问题转化为等价的非光滑方程组,再利用凝聚函数进行光滑逼近,从而转化为光滑方程组的求解问题.通过一些考题对这个算法进行了数值试验,结果显示了该算法的有效性和稳定性.     

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.     

单调线性互补问题的Mehrotra型预估-校正算法的迭代复杂性

Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(n log((x0)T s0/ε)),同时,初步的数值实验证明了新算法是有效的.     

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

利用严格对角占优M-矩阵的逆矩阵的无穷大范数的范围,给出了B-矩阵线性互补问题误差界新的估计式.相应数值算例表明了结果的有效性.