A Poximal-Projection Bundle Method for Convex Nonsmooth Optimization with On-Demand Accuracy Oracles

  • Xiaoxia Dong Guangxi University
  • Chunming Tang Guangxi University
  • Haiyan Zheng Guangxi University
Keywords: Nonsmooth optimization, Proximal-projection bundle method, On-demand accuracy, Global convergence


For some practical problems, the exact computation of the function and (sub)gradient values may be difficult. In this paper, a proximal-projection bundle method for minimizing convex nonsmooth optimization problems with on-demand accuracy oracles is proposed. Our method essentially generalizes the work of Kiwiel (SIAM J Optim, 17: 1015-1034, 2006) from exact and inexact oracles to various oracles, including exact, inexact, partially inexact, asymptotically exact and partially asymptotically exact oracles. At each iteration, a proximal subproblem is solved to generate a linear model of the objective function, and then a projection subproblem is solved to obtain a trial point. Finally, global convergence of the algorithm is established under different types of inexactness.


F. Bonnans, J. C. Gilbert, C. Lemaréchal, C. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects. Second ed. Springer-Verlag, Berlin Heidelberg New York (2006).

. B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms, Springer science & business media, vol. 305, 2013.

W. Oliveira and C. Sagastizábal, Level bundle methods for oracles with on demand accuracy, Optimization Methods and Software, vol. 29, pp. 1180-1209, 2014.

K.C. Kiwiel, Bundle methods for convex minimization with partially inexact oracles, Tech. Rep., Systems Research Institute, Polish Academy of Sciences,Warsaw, 2009.

W. Oliveira, C. Sagastizábal and S. Scheimberg, Inexact bundle methods for two-stage stochastic programming, SIAM Journal on Optimization, vol. 21, pp. 517-544, 2011.

C. I. Fábián, Bundle-type methods for inexact data, Central European Journal of Operations Research, vol.8, pp. 35-55, 2000.

K. C. Kiwiel, A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming, SIAM Journal on Optimization, vol. 17, pp. 1015-1034, 2006.

W. Ackooij and W. Oliveira, Level bundle methods for constrained convex optimization with various oracles, Computational Optimization and Applications, vol. 57, pp. 555-597, 2014.

K. C. Kiwiel, An algorithm for nonsmooth convex minimization with errors, Mathematics of Computation, vol. 45(171), pp. 173-180, 1985.

K. C. Kiwiel, A proximal bundle method with approximate subgradient linearizations, SIAM Journal on Optimization, vol. 16, pp. 1007-1023, 2006.

W. Oliveira, C. Sagastizbal and C. Lemarchal, Convex proximal bundle methods in depth: a unified analysis for inexact oracles, Mathematical Programming, vol. 148, pp. 241-277, 2014.

. Malick, W. Oliveira and S. Zaourar-Michel, Uncontrolled inexact information within bundle methods,EURO Journal on Computational Optimization, Springer, vol. 5, pp. 5-29, 2017.

G. Zakeri, A. B. Philpott and D. M. Ryan, Inexact cuts in benders decomposition, SIAM Journal on Optimization, vol. 10, pp. 643-657, 2000.

K. C. Kiwiel, Bundle methods for convex minimization with partially inexact oracles, Technical report, 2009.

C. Lemaréchal, A. S. Nemirovskii and Y. E. Nesterov, New variants of bundle methods, Mathematical Programming, vol. 69, pp. 111-147, 1995.

C. Wolf, C. I. Fábián, A. Koberstein, et al. Applying oracles of on-demand accuracy in two-stage stochastic programming - A computational study, European Journal of Operational Research, vol.239, pp. 437-448,2014.

A. Shapiro, D. Dentcheva and A. Ruszczy´ nski, Lectures on Stochastic Programming: Modeling and Theory, Society for Industrial and Applied Mathematics, 2009.

K. C. Kiwiel, C. H. Rosa and A. Ruszczy´ nski, Proximaldecomposition via alternating linearization, SIAM Journal on Optimization, vol. 9, pp. 668-689, 1999.

How to Cite
Dong, X., Tang, C., & Zheng, H. (2019). A Poximal-Projection Bundle Method for Convex Nonsmooth Optimization with On-Demand Accuracy Oracles. Statistics, Optimization & Information Computing, 7(1), 254-263. https://doi.org/10.19139/soic.v7i1.680
Research Articles