zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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 * X, s.t. <f(x * ),x-x * >0, xX, '' where X is a nonempty closed convex set in n and f:X n is a monotone continuous map. The algorithm is as follows: (iter. 0) Start with any x 0 X. (iter. r+1) Given an x r X, compute the new iterate x r+1 X satisfying <D(x r+1 -x r )+f(x r ), x-x r+1 >0, xX, where D is an (asymmetric) n×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= + 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:
90C25Convex programming
49J40Variational methods including variational inequalities
65K05Mathematical programming (numerical methods)
90C33Complementarity and equilibrium problems; variational inequalities (finite dimensions)
90-08Computational methods (optimization)
68W15Distributed algorithms
49M27Decomposition methods in calculus of variations
49N10Linear-quadratic optimal control problems
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).
[5]D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation: Numerical Methods (Prentice-Hall, Englewood Cliffs, NJ, 1989).
[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).
[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).
[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.
[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.
[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).
[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).
[33]R.T. Rockafellar, ”On the maximality of sums of nonlinear monotone operators,”Transactions of the American Mathematical Society 149 (1970) 75–88. · 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).
[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.