×

Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming. (English) Zbl 0725.90079

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 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.
Reviewer: S.Shih (Tianjin)

MSC:

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

Citations:

Zbl 0477.90065
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B.H. Ahn and W.W. Hogan, ”On convergence of the PIES algorithm for computing equilibria,”Operations Research 30 (1982) 281–300. · Zbl 0481.90011 · doi:10.1287/opre.30.2.281
[2] A. Auslender,Optimization: Méthodes Numériques (Masson, Paris, 1976).
[3] M.L. Balinksi and R.W. Cottle, eds.,Mathematical Programming Study 7: Complementarity and Fixed Point Problems (North-Holland, Amsterdam, 1978).
[4] D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982). · Zbl 0572.90067
[5] D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation: Numerical Methods (Prentice-Hall, Englewood Cliffs, NJ, 1989). · Zbl 0743.65107
[6] H. Brézis,Opérateurs Maximaux Monotones (North-Holland, Amsterdam, 1973).
[7] R.E. Bruck Jr., ”An iterative solution of a variational inequality for certain monotone operators in Hilbert space,”Bulletin of the American Mathematical Society 81 (1975) 890–892. · Zbl 0332.49005 · doi:10.1090/S0002-9904-1975-13874-2
[8] R.W. Cottle, F. Giannessi and J.-L. Lions, eds.,Variational Inequalities and Complementarity Problems: Theory and Applications (Wiley, New York, 1980).
[9] S. Dafermos, ”An iterative scheme for variational inequalities,”Mathematical Programming 26 (1983) 40–47. · Zbl 0506.65026 · doi:10.1007/BF02591891
[10] K. Deimling,Nonlinear Functional Analysis (Springer, Berlin, 1985). · Zbl 0559.47040
[11] B. Feijoo and R.R. Meyer, ”Piecewise-linear approximation methods for nonseparable convex optimization,”Management Science 34 (1988) 411–419. · Zbl 0648.90059 · doi:10.1287/mnsc.34.3.411
[12] D. Gabay, ”Applications of the method of multipliers to variational inequalities,” in: M. Fortin and R. Glowinski, eds.,Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems (North-Holland, Amsterdam, 1983).
[13] R. Glowinski, J.-L. Lions and R. Trémoliéres,Numerical Analysis of Variational Inequalities (North-Holland, Amsterdam, 1981).
[14] A.A. Goldstein, ”Convex programming in Hilbert spaces,”Bulletin of the American Mathematical Society 70 (1964) 709–710. · Zbl 0142.17101 · doi:10.1090/S0002-9904-1964-11178-2
[15] L.G. Gubin, B.T. Polyak E.V. Raik, ”The method of projections for finding the common point of convex sets,”Ž. Vyčhisl. Mat. i Mat. Fiz. 7 (1967) 1211–1228;USSR Computational Mathematics and Mathematical Physics 6 (1967) 1–24.
[16] S.P. Han, ”A successive projection method,”Mathematical Programming 40 (1988) 1–14. · Zbl 0685.90074 · doi:10.1007/BF01580719
[17] S.P. Han and G. Lou, ”A parallel algorithm for a class of convex programs,”SIAM Journal on Control and Optimization 26 (1988) 345–355. · Zbl 0644.90068 · doi:10.1137/0326019
[18] D. Kinderlehrer and G. Stampacchia,An Introduction to Variational Inequalities and their Applications (Academic Press, New York, 1980). · Zbl 0457.35001
[19] B. Lemaire, ”Coupling optimization methods and variational convergence,” in: K.-H. Hoffman, J.-B. Hiriart-Urruty, J. Zowe and C. Lemarechal, eds.,Trends in Mathematical Optimization (Birkhäuser, Basel, 1988) pp. 163–179. · Zbl 0633.49010
[20] Y.Y. Lin and J.-S. Pang, ”Iterative methods for large convex quadratic programs: A survey,”SIAM Journal on Control and Optimization 25 (1987) 383–411. · Zbl 0624.90083 · doi:10.1137/0325023
[21] P.L. Lions and B. Mercier, ”Splitting algorithms for the sum of two nonlinear operators,”SIAM Journal on Numerical Analysis 16 (1979) 964–979. · Zbl 0426.65050 · doi:10.1137/0716071
[22] Z.-Q. Luo and P. Tseng, ”On the convergence of a matrix-splitting algorithm for the symmetric linear complementarity problem,” LIDS Report P-1884, M.I.T. (Cambridge, MA, 1989).
[23] O.L. Mangasarian, ”Solution of symmetric linear complementarity problems by iterative methods,”Journal of Optimization Theory and Applications 22 (1977) 465–485. · Zbl 0341.65049 · doi:10.1007/BF01268170
[24] G.J. Minty, ”Monotone (nonlinear) operators in Hilbert space,”Duke Mathematical Journal 29 (1962) 341–346. · Zbl 0111.31202 · doi:10.1215/S0012-7094-62-02933-2
[25] G.J. Minty, ”On the monotonicity of the gradient of a convex function,”Pacific Journal of Mathematics 14 (1964) 243–247. · Zbl 0123.10601
[26] J.J. Moreau, ”Proximité et dualité dans un espace Hilbertien,”Bulletin de Société Mathématique de France 93 (1965) 273–299.
[27] K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Heldermann, Berlin, 1988). · Zbl 0634.90037
[28] J.-S. Pang, ”Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem,”Journal of Optimization Theory and Applications 42 (1984) 1–17. · Zbl 0506.90082 · doi:10.1007/BF00934130
[29] J.-S. Pang, ”Asymmetric variational inequality problems over product sets: Applications and iterative methods,”Mathematical Programming 31 (1985) 206–219. · Zbl 0578.49006 · doi:10.1007/BF02591749
[30] J.-S. Pang and D. Chan, ”Iterative methods for inequality and complementarity problems,”Mathematical Programming 24 (1982) 284–313. · Zbl 0499.90074 · doi:10.1007/BF01585112
[31] G.B. Passty, ”Ergodic convergence to a zero of the sum of monotone operators in Hilbert space,”Journal of Mathematical Analysis and Applications 72 (1979) 383–390. · Zbl 0428.47039 · doi:10.1016/0022-247X(79)90234-8
[32] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ., 1970). · Zbl 0193.18401
[33] R.T. Rockafellar, ”On the maximality of sums of nonlinear monotone operators,”Transactions of the American Mathematical Society 149 (1970) 75–88. · Zbl 0222.47017 · doi:10.1090/S0002-9947-1970-0282272-5
[34] R.T. Rockafellar, ”Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898. · Zbl 0358.90053 · doi:10.1137/0314056
[35] R.T. Rockafellar,Network Flows and Monotropic Optimization (Wiley, New York, 1984). · Zbl 0596.90055
[36] R.T. Rockafellar, ”Generalized linear-quadratic programming and optimal control,”SIAM Journal on Control and Optimization 25 (1987) 781–814. · Zbl 0617.49010 · doi:10.1137/0325045
[37] R.T. Rockafellar and R.J.-B. Wets, ”Generalized linear-quadratic problems of deterministics and stochastic optimal control in discrete time,” Technical Report, Department of Mathematics, University of Washington (Seattle, WA, 1987).
[38] M. Sibony, ”Méthodes itératives pour les équations et inéquations aux dérivées partielles nonlinéaires de type monotone,”Calcolo 7 (1970) 65–183. · Zbl 0225.35010 · doi:10.1007/BF02575559
[39] P. Tseng, ”Applications of a splitting algorithm to decomposition in convex programming and variational inequalities,” to appear in:SIAM Journal on Control and Optimization. · Zbl 0725.90079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.