Relaxation methods for problems with strictly convex separable costs and linear constraints.(English)Zbl 0636.90072
We consider the minimization problem with strictly convex, possibly nondifferentiable, separable cost and linear constraints. The dual of this problem is an unconstrained minimization problem with differentiable cost which is well suited for solution by parallel methods based on Gauss-Seidel relaxation. We show that these methods yield the optimal primal solution and, under additional assumptions, an optimal dual solution. To do this it is necessary to extend the classical Gauss-Seidel convergence results because the dual cost may not be strictly convex, and may have unbounded level sets.
MSC:
| 90C25 | Convex programming |
| 65K05 | Numerical mathematical programming methods |
| 90C55 | Methods of successive quadratic programming type |
Keywords:
Fenchel duality;strictly convex, possibly nondifferentiable, separable cost;linear constraints;unconstrained minimization;parallel methods;Gauss-Seidel relaxationCite
References:
| [1] | D.P. Bertsekas and D. Elbaz, ”Distributed asynchronous relaxation methods for convex network flow problems,”SIAM Journal on Control and Optimization 25 (1987) 74–85. ·Zbl 0624.90028 ·doi:10.1137/0325006 |
| [2] | D.P. Bertsekas, P.A. Hosein and P. Tseng, ”Relaxation methods for network flow problems with convex arc costs,” LIDS Report P-1523, Mass. Institute of Technology, December 1985,SIAM Journal on Control and Optimization, to appear. ·Zbl 0641.90036 |
| [3] | D.P. Bertsekas and P. Tseng, ”Relaxation Methods for Linear Programs,” LIDS Report P-1553, Mass. Institute of Technology, April 1986, to appear inMathematics of Operations Research. ·Zbl 0642.90068 |
| [4] | R.W. Cottle and J.S. Pang, ”On the convergence of a block successive over-relaxation method for a class of linear complementary problems,”Mathematical Programming Study 17 (1982) 126–138. ·Zbl 0478.90069 |
| [5] | G.H. Golub and C.F. Van Loan,Matrix Computations (Johns Hopkins Univ. Press, Baltimore, MD, 1985). ·Zbl 0592.65011 |
| [6] | D.G. Luenberger,Introduction to Linear and Nonlinear Programming (Addison-Wesley, Reading, MA, 2nd ed., 1984). ·Zbl 0571.90051 |
| [7] | J.S. Pang, ”On the convergence of dual ascent methods for large-scale linearly constrained optimization problems,” Unpublished manuscript, The University of Texas at Dallas, 1984. |
| [8] | E. Polak,Computational Methods in Optimization: A Unified Approach (Academic Press, New York, 1971). ·Zbl 0257.90055 |
| [9] | M.J.D. Powell, ”On search directions for minimization algorithms,”Mathematical Programming 4 (1973) 193–201. ·Zbl 0258.90043 ·doi:10.1007/BF01584660 |
| [10] | R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, New Jersey, 1970). ·Zbl 0193.18401 |
| [11] | R.T. Rockafellar,Network Flows and Monotropic Programming (Wiley-Interscience, New York, 1983). ·Zbl 0596.90055 |
| [12] | R. W. H. Sargent and D.J. Sebastian, ”On the Convergence of Sequential Minimization Algorithms,”Journal of Optimization Theory and Applications 12 (1973) 567–575. ·Zbl 0253.65037 ·doi:10.1007/BF00934779 |
| [13] | P. Tseng, ”Relaxation methods for monotropic programming problems,” Ph.D. Thesis, Dept. of Electrical Engineering and Computer Science, Operations Research Center, Mass. Institute of Technology (1986). |
| [14] | N. Zadeh, ”A note on the cyclic coordinate ascent method,”Management Science 16 (1970) 642–644. ·Zbl 0194.20403 ·doi:10.1287/mnsc.16.9.642 |
| [15] | W.I. Zangwill,Nonlinear Programming: A Unified Approach (Prentice-Hall, Englewood Cliffs, New Jersey, 1969). |
| [16] | S.A. Zenios and J.M. Mulvey, ”Simulating a distributed synchronous relaxation method for convex network problems,” Working Paper, Department of Civil Engineering, Princeton University, Princeton, New Jersey, January 1985. |
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.
