A class of convergent primal-dual subgradient algorithms for decomposable convex programs.(English)Zbl 0594.90074
Summary: We develop a primal-dual subgradient algorithm for preferably decomposable, generally nondifferentiable, convex programming problems, under usual regularity conditions. The algorithm employs a Lagrangian dual function along with a suitable penalty function which satisfies a specified set of properties, in order to generate a sequence of primal and dual iterates for which some subsequence converges to a pair of primal-dual optimal solutions. Several classical types of penalty functions are shown to satisfy these specified properties. A geometric convergence rate is established for the algorithm under some additional assumptions. This approach has three principal advantages. Firstly, both primal and dual solutions are available which prove to be useful in several contexts. Secondly, the choice of step sizes, which plays an important role in subgradient optimization, is guided more determinably in this method via primal and dual information. Thirdly, typical subgradient algorithms suffer from the lack of an appropriate stopping criterion, and so the quality of the solution obtained after a finite number of steps is usually unknown. In contrast, by using the primal-dual gap, the proposed algorithm possesses a natural stopping criterion.
Keywords:
primal-dual subgradient algorithm;nondifferentiable;convex programming;Lagrangian dual function;penalty function;stopping criterionCite
Full Text:DOI
References:
| [1] | S. Agmon, ”The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 382–392. ·Zbl 0055.35001 ·doi:10.4153/CJM-1954-037-2 |
| [2] | M.S. Bazaraa and H.D. Sherali, ”On the choice of step size in subgradient optimization”,European Journal of Operational Research 7 (1981) 380–388. ·Zbl 0454.90056 ·doi:10.1016/0377-2217(81)90096-5 |
| [3] | M.S. Bazaraa and C.M. Shetty,Nonlinear Programming: Theory and Applications (John Wiley and Sons, New York, New York, 1979). |
| [4] | D.P. Bertsekas, ”Combined primal-dual and penalty methods for constrained minimization”,SIAM Journal of Control 13 (1975) 521–544. ·doi:10.1137/0313030 |
| [5] | G. Bitran and A. Hax, ”On the solution of convex knapsack problems with bounded variables”,Proceedings of the IX International Symposium on Mathematical Programiming, Budapest (1976) 357–367. ·Zbl 0428.90062 |
| [6] | J.D. Buys, ”Dual algorithms for constrained optimization problems”, Unpublished Ph.D. Thesis, University of Leiden (The Netherlands, 1972). |
| [7] | G. Cohen and D.L. Zhu, ”Decomposition coordination methods in large scale optimization problems: The nondifferentiable case and the use of augmented lagrangians”, in: J.B. Cruz, ed.,Advances in Large Scale Systems 1 (JAI Press Inc., 1984) pp. 203–266. |
| [8] | M.L. Fisher, ”Lagrangian relaxation methods for combinatorial optimization”,Management Science 27 (1981) 1–18. ·Zbl 0466.90054 ·doi:10.1287/mnsc.27.1.1 |
| [9] | M. Fukushima, ”A descent algorithm for nonsmooth convex optimization”,Mathematical Programming 30 (2) (1984) 163–175. ·Zbl 0545.90082 ·doi:10.1007/BF02591883 |
| [10] | A.M. Geoffrion, ”Generalized Benders’ decomposition”,Journal of Optimization Theory and Applications 10 (4) (1972) 237–260. ·Zbl 0229.90024 ·doi:10.1007/BF00934810 |
| [11] | P.E. Gill, W. Murray and M.H. Wright,Practical optimization (Academic Press, New York, New York, 1981). |
| [12] | J.L. Goffin, ”Convergence results on a class of variable metric subgradient methods, in: O. Mangasarian, R. Meyer and S. Robinson, eds.,Nonlinear Programming 4 (1981) pp. 283–325. ·Zbl 0545.65045 |
| [13] | E.G. Gol’shtein, ”A generalized gradient method for finding saddlepoints,”Matekon 10 (3) (1974) 36–52. |
| [14] | M. Held and R.M. Karp, ”The traveling-salesman problem and minimum spanning trees: Part II”,Mathematical Programming 1 (1971) 6–26. ·Zbl 0232.90038 ·doi:10.1007/BF01584070 |
| [15] | M. Held, P. Wolfe and H.P. Crowder, ”Validation of subgradient optimization”,Mathematical Programming 6 (1974) 62–88. ·Zbl 0284.90057 ·doi:10.1007/BF01580223 |
| [16] | L.G. Khacijan, ”A polynomial algorithm in linear programming”,Doklady Akademiia Nauk SSSR, 224 (1979) 1093–1096, Translated inSoviet Mathematics Doklady 20 191–194. ·Zbl 0414.90086 |
| [17] | K. Kiwiel, ”An aggregate subgradient method for nonsmooth convex minimization”,Mathematical Programming 27 (1983) 320–341. ·Zbl 0525.90074 ·doi:10.1007/BF02591907 |
| [18] | G.M. Korpelevich, ”The extragradient method for finding saddle points and other problems”,Makedon 13 (4) (1977) 35–49. |
| [19] | C. Lemarechal, J. Strodiot and A. Bihain, ”On a bundle algorithm for nonsmooth optimization”,Nonlinear Programming Study No. 4 (Academic Press, New York, 1981) pp. 245–282. ·Zbl 0533.49023 |
| [20] | D. Maistroskii, ”Gradient methods for finding saddlepoints”,Matekon 13 (1977) 3–22. |
| [21] | T. Motzkin and I.J. Schoenberg, ”The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 393–404. ·Zbl 0055.35002 ·doi:10.4153/CJM-1954-038-x |
| [22] | B.T. Poljak, ”A general method of solving extremum problems”,Soviet Mathematics Doklady 8(3) (1967) 593–597. ·Zbl 0177.15102 |
| [23] | B.T. Poljak, ”Minimization of unsmooth functionals”,USSR Computational Mathematics and Mathematical Physics 9 (1969) 14–29. ·Zbl 0229.65056 ·doi:10.1016/0041-5553(69)90061-5 |
| [24] | R.T. Rockafellar, ”A dual approach to solving nonlinear programming problems by unconstrained optimization”,Mathematical Programming 5 (1973a) 354–373. ·Zbl 0279.90035 ·doi:10.1007/BF01580138 |
| [25] | R.T. Rockafellar, ”The multiplier method of Hestenes and Powell applied to convex programming”,Journal of Optimization Theory and Applications 12 (1973b) 555–562. ·Zbl 0254.90045 ·doi:10.1007/BF00934777 |
| [26] | R.T. Rockafellar, ”Augmented Lagrange multiplier functions and duality in nonconvex programming”,SIAM Journal on Control and Optimization 12 (1974) 268–285. ·doi:10.1137/0312021 |
| [27] | S. Sen and D.S. Yakowitz, ”A primal-dual subgradient algorithm for time staged capacity expansion planning”, SIE Working Paper Series, 84-002, Department of Systems and Industrial Engineering, The University of Arizona (Tucson, Arizona, 1984). |
| [28] | H.D. Sherali and D.C. Myers, ”Algorithmic strategies for using subgradient optimization with Lagrangian relaxation in solving mixed-integer programming problems”, Working Paper, Department of Industrial Engineering and Operations Research, Virginia Polytechnic Institute and State University (Blacksburg, Virginia, 1984). |
| [29] | N.Z. Shor, ”Generalized gradient methods of non-differentiable optimization employing space dilatation operators”, in: A. Bachem, M. Grotschel and B. Korte, eds.Mathematical Programming: The State of the Art (Bonn, W. Germany, 1983) pp. 501–529. ·Zbl 0558.49013 |
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.
