Subspace accelerated matrix splitting algorithms for asymmetric and symmetric linear complementarity problems

Daniel P. Robinson, Liming Feng, Jorge M. Nocedal, Jong Shi Pang

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies the solution of both asymmetric and symmetric linear complementarity problems by two-phase methods that consist of an active set prediction phase and an acceleration phase. The prediction phase employs matrix splitting iterations that re tailored to the structure of the linear complementarity problems studied in this aper. In the asymmetric case, the task of pairing an acceleration phase with matrix splitting iterations is achieved by xploiting a contraction property associated with certain matrix splittings. For symmetric roblems, a similar task is achieved by utilizing decent properties of specific matrix splitting iterations and rojected searches. The superior optimal active set identification property of matrix plitting iterations is illustrated with numerical experiments, which also demonstrate the general efficiency of the proposed methods.

Original languageEnglish (US)
Pages (from-to)1371-1397
Number of pages27
JournalSIAM Journal on Optimization
Volume23
Issue number3
DOIs
StatePublished - 2013

Keywords

  • American options pricing
  • Gauss-Seidel iteration
  • Iterative methods
  • Jacobi iteration
  • Linear complementarity
  • Quadratic programming
  • Splitting methods
  • Two-phase methods

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Subspace accelerated matrix splitting algorithms for asymmetric and symmetric linear complementarity problems'. Together they form a unique fingerprint.

Cite this