×

A parallel descent algorithm for convex programming. (English) Zbl 0844.90065

Summary: We propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5.

MSC:

90C25 Convex programming
65Y05 Parallel numerical computation

Software:

NETGEN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.Auslender, R.Cominetti, and J.-P.Crouzeix, ?Convex functions with unbounded level sets and applications to duality theory,? SIAM Journal on Optimization, vol. 3, pp. 669-687, 1993. · Zbl 0808.90102 · doi:10.1137/0803034
[2] D.P.Bertsekas, ?On the Goldstein-Levitin-Polyak gradient projection method,? IEEE Transactions on Automatic Control, vol. AC-21, pp. 174-184, 1976. · Zbl 0326.49025 · doi:10.1109/TAC.1976.1101194
[3] D.P.Bertsekas and J.N.Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall: Englewood Cliffs, N.J., 1989. · Zbl 0743.65107
[4] G.Cohen, ?Auxiliary problem principle and decomposition of optimization problems,? Journal of Optimization Theory and Applications, vol. 32, pp. 277-305, 1980. · Zbl 0417.49046 · doi:10.1007/BF00934554
[5] J.Eckstein, ?The alternating step method for monotropic programming on the connection machine CM-2,? ORSA Journal on Computing, vol. 5, pp. 84-96, 1993. · Zbl 0773.90055
[6] J.Eckstein and D.P.Bertsekas, ?On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators,? Mathematical Programming, vol. 55, pp. 293-318, 1992. · Zbl 0765.90073 · doi:10.1007/BF01581204
[7] J. Eckstein and M. Fukushima, ?Some reformulations and applications of the alternating direction method of multipliers,? in Large Scale Optimization: State of the Art, W.W. Hager, D.W. Hearn, and P.M. Pardalos (Eds.), Kluwer Academic Publishers B.V., pp. 115-134, 1994. · Zbl 0816.90109
[8] R.Fletcher, Practical Methods of Optimization, Second Edition, John Wiley: Chichester, 1987. · Zbl 0905.65002
[9] M.Fukushima and H.Mine, ?A generalized proximal point algorithm for certain non-convex minimization problems,? International Journal of Systems Science, vol. 12, pp. 989-1000, 1981. · Zbl 0467.65028 · doi:10.1080/00207728108963798
[10] M.Fukushima, K.Takazawa, S.Ohsaki, and T.Ibaraki, ?Successive linearization methods for large-scale nonlinear programming problems,? Japan Journal of Industrial and Applied Mathematics, vol. 9, pp. 117-132, 1992. · Zbl 0773.90067 · doi:10.1007/BF03167197
[11] S.-P.Han, ?A decomposition method and its application to convex programming,? Mathematics of Operations Research, vol. 14, pp. 237-248, 1989. · Zbl 0671.90062 · doi:10.1287/moor.14.2.237
[12] S.-P.Han and G.Lou, ?Some parallel decomposition algorithms for convex programming,? Technical Report, Department of Mathematics, University of Illinois, Urbana, Illinois, 1987.
[13] S.-P.Han and G.Lou, ?A parallel algorithm for a class of convex programs,? SIAM Journal on Control and Optimization, vol. 26, pp. 345-355, 1988. · Zbl 0644.90068 · doi:10.1137/0326019
[14] K.C.Kiwiel, ?A method for minimizing the sum of a convex function and a continuously differentiable function,? Journal of Optimization Theory and Applications, vol. 48, pp. 437-449, 1986. · Zbl 0562.90073 · doi:10.1007/BF00940570
[15] D.Klingman, A.Napier, and J.Stutz, ?NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems,? Management Science, vol. 20, pp. 814-821, 1974. · Zbl 0303.90042 · doi:10.1287/mnsc.20.5.814
[16] H.Mine and M.Fukushima, ?A minimization method for the sum of a convex function and a continuously differentiable function,? Journal of Optimization Theory and Applications, vol. 33, pp. 9-23, 1981. · Zbl 0422.90070 · doi:10.1007/BF00935173
[17] K.Mouallif, V.H.Nguyen, and J.-J.Strodiot, ?A perturbed parallel decomposition method for a class of nonsmooth convex minimization problems,? SIAM Journal on Control and Optimization, vol. 29, pp. 829-847, 1991. · Zbl 0733.65038 · doi:10.1137/0329045
[18] S.S.Nielsen and S.A.Zenios, ?Massively parallel algorithm for singly constrained convex programs,? ORSA Journal on Computing, vol. 4, pp. 166-181, 1992. · Zbl 0771.90079
[19] R.T.Rockafellar, Convex Analysis, Princeton University Press: Princeton, N.J., 1970. · Zbl 0193.18401
[20] R.T.Rockafellar, ?Monotone operators and the proximal point algorithm,? SIAM Journal on Control and Optimization, vol. 14, pp. 877-898, 1976. · Zbl 0358.90053 · doi:10.1137/0314056
[21] Thinking Machines Corporation, CM Fortran Libraries Reference Manual, Version 2.1, Cambridge, Massachusetts, 1994.
[22] Thinking Machines Corporation, CM Fortran Programming Guide, Version 2.1, Cambridge, Massachusetts, 1994.
[23] Thinking Machines Corporation, CM-5 CM Fortran Performance Guide, Version 2.1, Cambridge, Massachusetts, 1994.
[24] Thinking Machines Corporation, CMSSL for CM Fortran, Volume I, Version 3.2, Cambridge, Massachusetts, 1994.
[25] Thinking Machines Corporation, CMSSL for CM Fortran, Volume II, Version 3.2, Cambridge, Massachusetts, 1994.
[26] P.Tseng, ?Dual ascent methods for problems with strictly convex costs and linear constraints: a unified approach,? SIAM Journal on Control and Optimization, vol. 28, pp. 214-242, 1990. · Zbl 0692.49025 · doi:10.1137/0328011
[27] P.Tseng, ?Application of a splitting algorithm to decomposition in convex programming and variational inequalities,? SIAM Journal on Control and Optimization, vol. 29, pp. 119-138, 1991. · Zbl 0737.90048 · doi:10.1137/0329006
[28] P.Tseng, ?Dual coordinate ascent methods for non-strictly convex minimization,? Mathematical Programming, vol. 59, pp. 231-247, 1993. · Zbl 0782.90073 · doi:10.1007/BF01581245
[29] S.A.Zenios, ?Parallel numerical optimization: Current status and an annotated bibliography,? ORSA Journal on Computing, vol. 1, pp. 20-43, 1989. · Zbl 0825.65049
[30] S.A.Zenios and Y.Censor, ?Massively parallel row-action algorithms for some nonlinear transportation problems,? SIAM Journal of Optimization, vol. 1, pp. 373-400, 1991. · Zbl 0754.90057 · doi:10.1137/0801024
[31] S.A.Zenios and R.A.Lasken, ?Nonlinear network optimization on a massively parallel connection machine,? Annals of Operations Research, vol. 14, pp. 147-165, 1988. · doi:10.1007/BF02186478
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.