Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming (Q2277367): Difference between revisions

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.