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
DOI: https://doi.org/10.19139/soic.v7i1.680
Keywords: Nonsmooth optimization, Proximal-projection bundle method, On-demand accuracy, Global convergence

Abstract

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.

References

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.

Published
2019-01-21
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
Issue
Vol 7 No 1 (2019)
Section
Research Articles
Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).