×

On the convergence of conditional \(\varepsilon\)-subgradient methods for convex programs and convex-concave saddle-point problems. (English) Zbl 1053.90107

Summary: The paper provides two contributions. First, we present new convergence results for conditional \(\varepsilon\)-subgradient algorithms for general convex programs. The results obtained here extend the classical ones by B. T. Polyak [Sov. Math., Dokl. 8, 593–597 (1967; Zbl 0177.15102); U.S.S.R. Comput. Math. Math. Phys. 9(1969), No. 3, 14–29 (1971; Zbl 0229.65056); Introduction to Optimization, Optimization Software, New York (1987)] as well as the recent ones in [R. Correa and C. Lemaréchal, Math. Program., Ser. B 62, No. 2, 261–275 (1993; Zbl 0805.90083); T. Larsson, M. Patriksson and A.-B. Strömberg, Eur. J. Oper. Res. 88, No. 2, 382–403 (1996; Zbl 0913.90225); Math. Program. 81, 23 (1998)] to a broader framework. Secondly, we establish the application of this technique to solve non-strictly convex-concave saddle point problems, such as primal-dual formulations of linear programs. Contrary to several previous solution algorithms for such problems, a saddle-point is generated by a very simple scheme in which one component is constructed by means of a conditional \(\varepsilon\)-subgradient algorithm, while the other is constructed by means of a weighted average of the (inexact) subproblem solutions generated within the subgradient method. The convergence result extends those of N. Z. Shor [Minimization methods for non-differentiable functions, Berlin: Springer-Verlag (1985; Zbl 0561.90058)], H. D. Sherali and G. Choi [Oper. Res. Lett. 19, No. 3, 105–113 (1996; Zbl 0871.90054)] and T. Larsson, M. Patriksson and A.-B. Strömberg [Math. Program. 86A, No. 2, 283–312 (1999; Zbl 0946.90059)] for Lagrangian saddle-point problems in linear and convex programming, and of [Int. J. Numer. Meth. Eng. 40, 1295 (1997)] for a linear-quadratic saddle-point problem arising in topology optimization in contact mechanics.

MSC:

90C25 Convex programming
90C52 Methods of reduced gradient type
90C06 Large-scale problems in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alber, Ya. I., Recurrence relations and variational inequalities, Soviet Mathematics Doklady, 27, 511-517 (1983) · Zbl 0533.49026
[2] Alber, Ya. I.; Iusem, A. N.; Solodov, M. V., On the projected subgradient method for nonsmooth convex optimization in a Hilbert space, Mathematical Programming, 81, 23-35 (1998) · Zbl 0919.90122
[3] Barahona, F.; Anbil, R., The volume algorithm: Producing primal solutions with a subgradient method, Mathematical Programming, 87, 385-399 (2000) · Zbl 0961.90058
[4] Bazaraa, M. S.; Sherali, H. D.; Shetty, C. M., Nonlinear Programming: Theory and Algorithms (1993), John Wiley & Sons: John Wiley & Sons New York, NY · Zbl 0774.90075
[5] Bertsekas, D. P., Nonlinear Programming (1999), Athena Scientific: Athena Scientific Belmont, MA · Zbl 0935.90037
[6] Correa, R.; Lemaréchal, C., Convergence of some algorithms for convex minimization, Mathematical Programming, 62, 261-275 (1993) · Zbl 0805.90083
[7] Danskin, J. M., The Theory of Max-Min (1967), Springer-Verlag: Springer-Verlag Berlin · Zbl 0154.20009
[8] Demyanov, V. F.; Malozemov, V. N., Introduction to Minimax (1974), John Wiley & Sons: John Wiley & Sons New York, NY
[9] Dem’janov, V. F.; Šomesova, V. K., Conditional subdifferentials of convex functions, Soviet Mathematics Doklady, 19, 1181-1185 (1980) · Zbl 0461.49005
[10] Ermol’ev, Yu. M., Methods for solving nonlinear extremal problems, Cybernetics, 2, 1-17 (1966)
[11] Hearn, D. W.; Lawphongpanich, S., Operations Research Letters, 8, 189-196 (1989)
[12] Hiriart-Urruty, J.-B.; Lemaréchal, C., Convex Analysis and Minimization Algorithms, I: Fundamentals (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0795.49001
[13] Kallio, M.; Rosa, C. H., Large-scale convex optimization via saddle point computation, Operations Research, 47, 93-101 (1999) · Zbl 0979.90097
[14] M. Kallio, A. Ruszczyński, Perturbation methods for saddle point computation, Working paper WP-94-38, IIASA, Laxenburg, Austria; M. Kallio, A. Ruszczyński, Perturbation methods for saddle point computation, Working paper WP-94-38, IIASA, Laxenburg, Austria
[15] Kiwiel, K. C., Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities, Mathematical Programming, 69, 89-109 (1995) · Zbl 0857.90101
[16] Larsson, T.; Liu, Z., A Lagrangian relaxation scheme for structured linear programs with application to multicommodity network flows, Optimization, 40, 247-284 (1997) · Zbl 0880.90101
[17] Larsson, T.; Liu, Z.; Patriksson, M., A dual scheme for traffic assignment problems, Optimization, 42, 323-358 (1997) · Zbl 0893.90055
[18] T. Larsson, M. Patriksson, Global optimality conditions and Lagrangian heuristics for nonconvex optimization, report, Department of Mathematics, Chalmers University of Technology, Gothenburg, in preparation; T. Larsson, M. Patriksson, Global optimality conditions and Lagrangian heuristics for nonconvex optimization, report, Department of Mathematics, Chalmers University of Technology, Gothenburg, in preparation · Zbl 1167.90633
[19] Larsson, T.; Patriksson, M.; Strömberg, A.-B., Conditional subgradient optimization-theory and applications, European Journal of Operational Research, 88, 382-403 (1996) · Zbl 0913.90225
[20] Larsson, T.; Patriksson, M.; Strömberg, A.-B., Ergodic convergence in subgradient optimization, Optimization Methods & Software, 9, 93-120 (1998) · Zbl 0904.90131
[21] Larsson, T.; Patriksson, M.; Strömberg, A.-B., Ergodic, primal convergence in dual subgradient schemes for convex programming, Mathematical Programming, 86, 283-312 (1999) · Zbl 0946.90059
[22] Lasdon, L. S., Optimization Theory for Large Systems (1970), Macmillan: Macmillan New York · Zbl 0224.90038
[23] Ouorou, A., A primal-dual algorithm for monotropic programming and its application to network optimization, Computational Optimization and Applications, 15, 125-143 (2000) · Zbl 0947.90089
[24] Petersson, J.; Patriksson, M., Topology optimization of sheets in contact by a subgradient method, International Journal of Numerical Methods in Engineering, 40, 1295-1321 (1997) · Zbl 0890.73046
[25] Polyak, B. T., A general method of solving extremum problems, Soviet Mathematics Doklady, 8, 593-597 (1967) · Zbl 0177.15102
[26] Polyak, B. T., Minimization of unsmooth functionals, USSR Computational Mathematics and Mathematical Physics, 9, 14-29 (1969) · Zbl 0229.65056
[27] B.T. Polyak, Introduction to Optimization, Optimization Software New York, 1987; B.T. Polyak, Introduction to Optimization, Optimization Software New York, 1987 · Zbl 0708.90083
[28] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0229.90020
[29] Rockafellar, R. T., The Theory of Subgradients and its Applications to Problems of Optimization: Convex and Nonconvex Functions (1981), Heldermann Verlag: Heldermann Verlag Berlin · Zbl 0462.90052
[30] Sherali, H. D.; Choi, G., Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs, Operations Research Letters, 19, 105-113 (1996) · Zbl 0871.90054
[31] Shor, N. Z., Minimization Methods for Non-Differentiable Functions (1985), Springer-Verlag: Springer-Verlag Berlin · Zbl 0561.90058
[32] Solodov, M. V.; Zavriev, S. K., Error stability properties of generalized gradient-type algorithms, Journal of Optimization Theory and Applications, 98, 663-680 (1998) · Zbl 0913.90245
[33] Wolsey, L. A., Integer Programming (1998), John Wiley & Sons: John Wiley & Sons New York · Zbl 0299.90012
[34] Zhao, X.; Luh, P. B.; Wang, J., New bundle methods for solving Lagrangian relaxation dual problems, Journal of Optimization Theory and Applications, 113, 373-397 (2002) · Zbl 1015.90089
[35] Zhao, X.; Luh, P. B.; Wang, J., Surrogate gradient algorithm for Lagrangian relaxation, Journal of Optimization Theory and Applications, 100, 699-712 (1999) · Zbl 0949.90065
[36] Zhu, C.; Rockafellar, R. T., Primal-dual projected gradient algorithms for extended linear-quadratic programming, SIAM Journal on Optimization, 3, 751-783 (1993) · Zbl 0788.65069
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.