Abstract
For solving nonsmooth convex constrained optimization problems, we propose an algorithm which combines the ideas of the proximal bundle methods with the filter strategy for evaluating candidate points. The resulting algorithm inherits some attractive features from both approaches. On the one hand, it allows effective control of the size of quadratic programming subproblems via the compression and aggregation techniques of proximal bundle methods. On the other hand, the filter criterion for accepting a candidate point as the new iterate is sometimes easier to satisfy than the usual descent condition in bundle methods. Some encouraging preliminary computational results are also reported.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Auslender A. (1987). Numerical methods for nondifferentiable convex optimization. Math. Program. Study 30: 102–126
Auslender A. (1997). How to deal with the unbounded in optimization: theory and algorithms. Math. Program. 79: 3–18
Bonnans J.F., Gilbert J.-Ch., Lemaréchal C. and Sagastizábal C. (2003). Numerical Optimization. Theoretical and Practical Aspects. Universitext. Springer, Berlin
Fletcher R., Gould N., Leyffer S., Toint P. and Wächter A. (2002). Global convergence of trust-region and SQP-filter algorithms for general nonlinear programming. SIAM J. Optim. 13: 635–659
Fletcher, R., Leyffer, S.: A bundle filter method for nonsmooth nonlinear optimization. Numerical Analysis Report NA/195. Department of Mathematics, The University of Dundee, Scotland (1999)
Fletcher R. and Leyffer S. (2002). Nonlinear programming without a penalty function. Math. Program 91: 239–269
Fletcher R., Leyffer S. and Toint P.L. (2002). On the global convergence of a filter-SQP algorithm. SIAM J. Optim. 13: 44–59
Frangioni A. (1996). Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 23: 1099–1118
Frangioni A. (2002). Generalized bundle methods. SIAM J. Optim. 13: 117–156
Gonzaga C.C., Karas E.W. and Vanti M. (2003). A globally convergent filter method for nonlinear programming. SIAM J. Optim. 14: 646–669
Hiriart-Urruty J.-B. and Lemaréchal C. (1993). Convex Analysis and Minimization Algorithms. Number 305–306 in Grund. der Math. Wiss. Springer, Heidelberg
Hock W. and Schittkowski K. (1981). Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer, Berlin
Kiwiel K.C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics, vol. 1133. Springer, Berlin
Kiwiel K.C. (1985). An exact penalty function algorithm for nonsmooth convex constrained minimization problems. IMA J. Numer. Anal. 5: 111–119
Kiwiel K.C. (1986). A method for solving certain quadratic programming problems arising in nonsmooth optimization. IMA J. Numer. Anal. 6: 137–152
Kiwiel K.C. (1987). A constraint linearization method for nondifferentiable convex minimization. Numer. Math. 51: 395–414
Kiwiel K.C. (1991). Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization. Math. Program. 52: 285–302
Lemaréchal C., Nemirovskii A. and Nesterov Yu. (1995). New variants of bundle methods. Math. Program. 69: 111–148
Lemaréchal C. and Sagastizábal C. (1997). Variable metric bundle methods: from conceptual to implementable forms. Math Program 76: 393–410
Lukšan L (1984). Dual method for solving a special problem of quadratic programming as a subproblem at linearly constrained nonlinear minimax approximation. Kybernetika 20: 445–457
Lukšan, L., Vlček, J.: A bundle-Newton method for nonsmooth unconstrained minimization. Math. Program. 83(3, Ser. A):373–391 (1998)
Lukšan L. and Vlček J. (1999). Globally convergent variable metric method for convex nonsmooth unconstrained minimization. J. Optim. Theory Appl. 102(3): 593–613
Lukšan, L., Vlček, J.: NDA: Algorithms for nondifferentiable optimization. Research Report V-797. Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague (2000)
Lukšan L. and Vlček J. (2001). Algorithm 811, NDA, http://www.netlib.org/toms/811. ACM Trans. Math. Softw. 27(2): 193–213
Mangasarian O.L. (1969). Nonlinear Programming. McGraw-Hill, New York
Mifflin R. (1977). An algorithm for constrained optimization with semismooth functions. Math. Oper. Res. 2: 191–207
Mifflin R. (1982). A modification and extension of Lemarechal’s algorithm for nonsmooth minimization. Math. Program. Study 17: 77–90
Powell M.J.D. (1985). On the quadratic programming algorithm of Goldfarb and Idnani. Math. Program. Study 25: 46–61
Rey P.A. and Sagastizábal C. (2002). Dynamical adjustment of the prox-parameter in variable metric bundle methods. Optimization 51: 423–447
Sagastizábal C. and Solodov M. (2005). An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter. SIAM J. Optim. 16: 146–169
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Alfred Auslender on the occasion of his 65th birthday.
This work has been supported by CNPq-PROSUL program. Claudia Sagastizábal was also supported by CNPq, by PRONEX–Optimization, and by FAPERJ. Mikhail Solodov was supported in part by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX-Optimization, and by FAPERJ.
Claudia Sagastizábal is on leave from INRIA-Rocquencourt, BP 105, 78153 Le Chesnay, France.
Rights and permissions
About this article
Cite this article
Karas, E., Ribeiro, A., Sagastizábal, C. et al. A bundle-filter method for nonsmooth convex constrained optimization. Math. Program. 116, 297–320 (2009). https://doi.org/10.1007/s10107-007-0123-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0123-7