×

Dual gradient method for linearly constrained, strongly convex, separable mathematical programming problems. (English) Zbl 0595.90069

A new dual gradient method is given to solve linearly constrained, strongly convex, separable mathematical programming problems. The dual problem can be decomposed into one-dimensional problems whose solutions can be computed extremely easily. The dual objective function is shown to have a Lipschitz continuous gradient, and therefore a gradient-type algorithm can be used for solving the dual problem. The primal optimal solution can be obtained from the dual optimal solution in a straightforward way. Convergence proofs and computational results are given.

MSC:

90C25 Convex programming
65K05 Numerical mathematical programming methods
90C55 Methods of successive quadratic programming type
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Collins, M., Cooper, L., Helgason, R. V., Kennington, J. L., andLeBlanc, L. J.,Solving the Pipe Network Analysis Problem Using Optimization Techniques, Management Science, Vol. 24, pp. 747-760, 1978. · Zbl 0375.90069 · doi:10.1287/mnsc.24.7.747
[2] Cooper, L., andKennington, J. L.,Steady-State Analysis of Nonlinear Resistive Electrical Networks Using Optimization Techniques, Technical Report No. IEOR-7012, Southern Methodist University, Dallas, Texas 1977.
[3] Bachem, A., andKort, B.,An Algorithm for Quadratic Optimization over Transportation Polytopes, Zeitschrift für Angewandte Mathematik und Mechanik, Vol. 58, pp. 459-461, 1978. · Zbl 0396.90102 · doi:10.1002/zamm.19780581007
[4] Monma, C. L., andSegal, M.,A Primal Algorithm for Finding Minimum-Cost Flows in Capacitated Networks with Applications, Bell System Technical Journal, Vol. 61, pp. 949-968, 1982.
[5] Kamesam, P. V.,Convex Network Optimization, University of Wisconsin, Madison, Wisconsin, PhD Thesis, 1982.
[6] Dembo, R. S., andKlincewicz, J. G.,A Scaled Reduced Gradient Algorithm for Network Flow Problems with Convex Separable Costs, Mathematical Programming Studies, Vol. 15, pp. 125-147, 1981. · Zbl 0477.90025
[7] Klincewicz, J. G.,A Newton Method for Convex Separable Network Flow Problems, Networks, Vol. 13, pp. 427-442, 1983. · Zbl 0518.90016 · doi:10.1002/net.3230130310
[8] Geoffrion, A. M.,Duality in Nonlinear Programming: A Simplified Application-Oriented Development, SIAM Review, Vol. 13, pp. 1-37, 1971. · Zbl 0232.90049 · doi:10.1137/1013001
[9] Mangasarian, O. L.,Nonlinear Programming, McGraw-Hill, New York, New York, 1969.
[10] Cheng, Y. C.,Iterative Methods for Solving Linear Complementarity and Linear Programming Problems, University of Wisconsin, PhD Thesis, 1981.
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.