Operator-Splitting Methods for Monotone Affine Variational Inequalities, with a Parallel Application to Optimal Control
- 1 May 1998
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 10 (2), 218-235
- https://doi.org/10.1287/ijoc.10.2.218
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.Keywords
This publication has 36 references indexed in Scilit:
- Mcplib: a collection of nonlinear mixed complementarity problemsOptimization Methods and Software, 1995
- The path solver: a nommonotone stabilization scheme for mixed complementarity problemsOptimization Methods and Software, 1995
- Sequential quadratic programming algorithm for discrete optimal control problems with control inequality constraintsInternational Journal of Control, 1991
- A Lagrangian finite generation technique for solving linear-quadratic problems in stochastic programmingPublished by Springer Science and Business Media LLC ,1986
- Nonlinear mappings of monotone typePublished by Springer Science and Business Media LLC ,1978
- On the maximality of sums of nonlinear monotone operatorsTransactions of the American Mathematical Society, 1970
- Weak convergence of the sequence of successive approximations for nonexpansive mappingsBulletin of the American Mathematical Society, 1967
- Characterization of the subdifferentials of convex functionsPacific Journal of Mathematics, 1966
- Monotone (nonlinear) operators in Hilbert spaceDuke Mathematical Journal, 1962
- On the numerical solution of heat conduction problems in two and three space variablesTransactions of the American Mathematical Society, 1956