×

Operator-splitting methods for monotone affine variational inequalities, with a parallel application to optimal control. (English) Zbl 1034.90531

Summary: 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.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49J40 Variational inequalities

Software:

CONOPT; MCPLIB
PDFBibTeX XMLCite
Full Text: DOI Link