×

zbMATH — the first resource for mathematics

A multi-step doubly stabilized bundle method for nonsmooth convex optimization. (English) Zbl 07197527
Summary: In this paper, by incorporating a multi-step scheme into the doubly stabilized bundle method (DSBM) recently developed by W. de Oliveira and M. Solodov [Math. Program. 156, No. 1–2 (A), 125–159 (2016; Zbl 1346.90675)], we propose a multi-step doubly stabilized bundle method (MDSBM) for solving nonsmooth convex optimization problems. In contrast to a single sequence generated by DSBM, the MDSBM generates three related iteration sequences. One is used to build the cutting-planes model of the objective function, another is served as the stability centers, and the third is the sequence of solutions to our new doubly stabilized subproblems. In addition, we present a new descent test criterion, aiming to take advantage of the multi-step scheme. We establish global convergence of the proposed method, and finally present some promising numerical results.
MSC:
90C25 Convex programming
49J52 Nonsmooth analysis
Software:
Mosek; PLCP; SQPlab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Shor, N. Z., Minimization Methods for Non-Differentiable Functions (1985), Springer-Verlag, Berlin · Zbl 0561.90058
[2] Cheney, E. W.; Goldstein, A. A., Newton’s method for convex programming and Tchebycheff approximations, Numerische Mathematik, 1, 253-268 (1959) · Zbl 0113.10703
[3] Kelley, J. E., The cutting-plane method for solving convex programs, J. SIAM, 8, 703-712 (1960) · Zbl 0098.12104
[4] Lemaréchal, C., An extension of Davidon methods to nondifferentiable problems, Math. Programm. Study, 3, 95-109 (1975) · Zbl 0358.90051
[5] Wolfe, P., A method of conjugate subgradients for minimizing nondifferentiable functions, Math. Programm. Study, 3, 145-173 (1975)
[6] Mäkelä, M., Survey of bundle methods for nonsmooth optimization, Optim. Methods Softw., 17, 1, 1-29 (2002) · Zbl 1050.90027
[7] Bonnans, J.-F.; Gilbert, J. C.; Lemaréchal, C.; Sagastizábal, C. A., Numerical Optimization: Theoretical and Practical Aspects (2006), Springer Science & Business Media · Zbl 1108.65060
[8] Kiwiel, K. C., Proximity control in bundle methods for convex nondifferentiable minimization, Math. Program, 46, 1-3, 105-122 (1990) · Zbl 0697.90060
[9] Frangioni, A., Generalized bundle methods, SIAM J. Optim., 13, 1, 117-156 (2002) · Zbl 1041.90037
[10] de Oliveira, W.; Sagastizábal, C.; Lemaréchal, C., Convex proximal bundle methods in depth: a unified analysis for inexact oracles, Math. Program, 148, 241-277 (2014) · Zbl 1327.90321
[11] Hare, W.; Sagastizábal, C.; Solodov, M., A proximal bundle method for nonsmooth nonconvex functions with inexact information, Comput. Optim. Appl., 63, 1, 1-28 (2016) · Zbl 1343.90069
[12] Tang, C. M.; Jian, J. B., Strongly sub-feasible direction method for constrained optimization problems with nonsmooth objective functions, Eur. J. Oper. Res., 218, 1, 28-37 (2012) · Zbl 1244.90225
[13] Tang, C. M.; Jian, J. B.; Li, G. Y., A proximal-projection partial bundle method for convex constrained minimax problems, J. Ind. Manag. Optim., 15, 2, 757-774 (2019) · Zbl 1438.90387
[14] Pang, L.; Lv, J.; Wang, J., Constrained incremental bundle method with partial inexact oracle for nonsmooth convex semi-infinite programming problems, Comput. Optim. Appl., 64, 2, 433-465 (2016) · Zbl 1370.90278
[15] Lv, J.; Pang, L.; Meng, F., A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information, J. Global Optim., 70, 3, 517-549 (2018) · Zbl 1390.90448
[16] Lv, J.; Pang, L.; Xu, N.; Xiao, Z., An infeasible bundle method for nonconvex constrained optimization with application to semi-infinite programming problems, Numer. Algorithms, 80, 2, 397-427 (2019) · Zbl 1410.90169
[17] Schramm, H.; Zowe, J., A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM J. Optim., 2, 1, 121-152 (1992) · Zbl 0761.90090
[18] Apkarian, P.; Noll, D.; Prot, O., A trust region spectral bundle method for nonconvex eigenvalue optimization, SIAM J. Optim., 19, 1, 281-306 (2008) · Zbl 1167.90015
[19] Liu, S., A simple version of bundle method with linear programming, Comput. Optim. Appl., 72, 2, 391-412 (2019) · Zbl 1414.90268
[20] Lemaréchal, C.; Nesterov, Y.; Nemirovskii, A., New variants of bundle methods, Math. Program, 69, 1-3, 111-147 (1995) · Zbl 0857.90102
[21] de Oliveira, W.; Sagastizábal, C., Level bundle methods for oracles with on-demand accuracy, Optim. Methods Softw., 29, 6, 1180-1209 (2014) · Zbl 1306.90121
[22] Lan, G., Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization, Math. Program, 149, 1-45 (2015) · Zbl 1321.90104
[23] Lemaréchal, C.; Sagastizábal, C., Variable metric bundle methods: from conceptual to implementable forms, Math. Program, 76, 3, 393-410 (1997) · Zbl 0872.90072
[24] de Oliveira, W.; Solodov, M. V., A doubly stabilized bundle method for nonsmooth convex optimization, Math. Program, 156, 125-159 (2016) · Zbl 1346.90675
[25] Nesterov, Y. E., A method for unconstrained convex minimization problem with rate of convergence O(1/k^2), Doklady AN SSSR, 269, 543-547 (1983)
[26] G. Lan, Y. Ouyang, Accelerated gradient sliding for structured convex optimization, 2016. arXiv preprint arXiv:1609.04905.
[27] Ouyang, Y.; Chen, Y.; Lan, G.; Pasiliao, E., An accelerated linearized alternating direction method of multipliers, SIAM J. Imaging Sci., 8, 1, 644-681 (2015) · Zbl 1321.90105
[28] Lan, G.; Lu, Z.; Monteiro, R. D.C., Primal-dual first-order methods with O(1/ϵ) iteration-complexity for cone programming, Math. Program., 126, 1, 1-29 (2011) · Zbl 1208.90113
[29] Lan, G., An optimal method for stochastic composite optimization, Math. Program., 133, 1, 365-397 (2012) · Zbl 1273.90136
[30] Ghadimi, S.; Lan, G., Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program., 156, 1, 59-99 (2016) · Zbl 1335.62121
[31] Chen, Y.; Lan, G.; Ouyang, Y., Accelerated schemes for a class of variational inequalities, Math Program., 165, 1, 113-149 (2017) · Zbl 1386.90102
[32] Lan, G., Gradient sliding for composite optimization, Math. Program. Ser. A, 159, 1-2, 201-235 (2016) · Zbl 1346.90667
[33] Chen, Y.; Lan, G.; Ouyang, Y.; Zhang, W., Fast bundle-level type methods for unconstrained and ball-constrained convex optimization, Comput. Optim. Appl., 73, 1, 159-219 (2019) · Zbl 1414.90263
[34] Kiwiel, K. C., Efficiency of proximal bundle methods, J. Optim. Theory Appl., 104, 3, 589-603 (2000) · Zbl 0985.90072
[35] MOSEK, MOSEK Optimization Toolbox for MATLAB, Release 9.1.5, 2016. MOSEK ApS, http://www.mosek.com.
[36] Karmitsa, N., Test problems for large-scale nonsmooth minimization, Technical Report (2007), Department of Mathematical Information Technology, University of Jyväskylä, Finland
[37] Dolan, E. D.; More, J. J., Benchmarking optimization software with performance profiles., Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.