The globally uniquely solvable (GUS) property of the linear transformation of the linear complementarity problems over symmetric cones has been studied recently by Gowda et al. via the approach of Euclidean Jordan algebra. In this paper, we contribute a new approach to characterizing the GUS property of the linear transformation of the second-order cone linear … Read more
The plain Newton-min algorithm to solve the linear complementarity problem (LCP for short) $0\leq x\perp(Mx+q)\geq0$ can be viewed as a nonsmooth Newton algorithm without globalization technique to solve the system of piecewise linear equations $\min(x,Mx+q)=0$, which is equivalent to the LCP. When $M$ is an $M$-matrix of order~$n$, the algorithm is known to converge in … Read more
In the Black-Scholes-Merton model, as well as in more general stochastic models in finance, the price of an American option solves a system of partial differential variational inequalities. When these inequalities are discretized, one obtains a linear complementarity problem that must be solved at each time step. This paper presents an algorithm for the solution … Read more
A new class of infeasible interior point methods for solving sufficient linear complementarity problems requiring one matrix factorization and $m$ backsolves at each iteration is proposed and analyzed. The algorithms from this class use a large $(\caln_\infty^-$) neighborhood of an infeasible central path associated with the complementarity problem and an initial positive, but not necessarily … Read more
This paper studies algorithms for the solution of mixed symmetric linear complementarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and American option pricing. The paper proposes an improvement of a method described by Kocvara and Zowe that combines … Read more
The linear complementarity problem (LCP) belongs to the class of NP-complete problems. Therefore we can not 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 … Read more
A first order affine scaling method and two $m$th order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has $O(nL^2(\log nL^2)(\log\log nL^2))$ iteration complexity. If the LCP admits a strict complementary solution then both … Read more
We extend the analysis of [27] to handling more general utility functions: piece-wise linear functions, which include Leontief’s utility. We show that the problem reduces to the general analytic center model discussed in [27]. Thus, the same linear programming complexity bound applies to approximating the Fisher equilibrium problem with these utilities. More importantly, we show … Read more
We correct an error in Algorithm 2 from the paper with the same name that was published in Mathematical Programming, Ser. A, 100, 2(2004), 317–337. Citationsubmitted to Mathematical ProgrammingArticleDownload View PDF
Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path CitationTechnical Report UMBC, TR2006-22, January 2005, Revised: March 2006.ArticleDownload View PDF