Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming

Variational inequalities (49J40) Decomposition methods (49M27) Linear-quadratic optimal control problems (49N10) Numerical mathematical programming methods (65K05) Distributed algorithms (68W15) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Convex programming (90C25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Review text

This paper considers an asymmetric projection (AP) algorithm to the following variational inequality problem: ``find \(x^*\in X\), s.t. \(<f(x^*),x-x^*>\geq 0\), \(\forall x\in X,\) where X is a nonempty closed convex set in \({\mathbb{R}}^ n\) and \(f:X\to {\mathbb{R}}^ n\) is a monotone continuous map. The algorithm is as follows: (iter. 0) Start with any \(x^ 0\in X\). (iter. \(r+1)\) Given an \(x^ r\in X\), compute the new iterate \(x^{r+1}\in X\) satisfying \(<D(x^{r+1}-x^ r)+f(x^ r)\), \(x-x^{r+1}>\geq 0\), \(\forall x\in X\), where D is an (asymmetric) \(n\times n\) positive definite matrix. The goal of this paper is two-fold: Firstly, the existing convergence conditions for the AP algorithm are showed as a corollary of a general convergence condition given by \textit{D. Gabay} [Math. Program. Study 16, 18-44 (1982; Zbl 0477.90065)] for a forward-backward splitting algorithm. Secondly, the convergence condition for the AP algorithm can be weakened such that it is applicable to any monotone affine variational inequality problem. In particular, this algorithm is applicable to linear complementarity problems (for \(X={\mathbb{R}}^ n_+)\) to obtain a matrix splitting algorithm that is simple and, for linear/quadratic programs, massively parallelizable. This method has the important advantage that it requires no additional assumption on the problem data for convergence and that it can simultaneously dualize any subset of the constraints and diagonalize the cost function. It also gives rise to highly parallelizable algorithms for solving a problem of deterministic control in discrete time and for computing the orthogonal projection onto the intersection of convex sets.

Recommendations

Cites work

Cited in

(77)

This page was built for publication: Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277367)