Operator-splitting methods for monotone affine variational inequalities, with a parallel application to optimal control

Jonathan Eckstein, Michael C. Ferris

Research output: Contribution to journalArticlepeer-review

64 Scopus citations

Abstract

This article applies splitting techniques developed for set-valued maximal monotone operators to monotone affine variational inequalities, including, as a special case, the classical linear complementarity problem. We give a unified presentation of several splitting algorithms for monotone operators, and then apply these results to obtain two classes of algorithms for affine variational inequalities. The second class resembles classical matrix splitting, but has a novel "under-relaxation" step, and converges under more general conditions. In particular, the convergence proofs do not require the affine operator to be symmetric. We specialize our matrix-splitting-like method to discrete-time optimal control problems formulated as extended linear-quadratic programs In the manner advocated by Rockafellar and Wets. The result Is a highly parallel algorithm, which we Implement and test on the Connection Machine CM-5 computer family.

Original languageEnglish (US)
Pages (from-to)218-235
Number of pages18
JournalINFORMS Journal on Computing
Volume10
Issue number2
DOIs
StatePublished - 1998

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Complementarity
  • Parallel computing
  • Programming

Fingerprint

Dive into the research topics of 'Operator-splitting methods for monotone affine variational inequalities, with a parallel application to optimal control'. Together they form a unique fingerprint.

Cite this