Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

12. Bundle Methods for Inexact Data

verfasst von : Welington de Oliveira, Mikhail Solodov

Erschienen in: Numerical Nonsmooth Optimization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Many applications of optimization to real-life problems lead to nonsmooth objective and/or constraint functions that are assessed through “noisy” oracles. In particular, only some approximations to the function and/or subgradient values are available, while exact values are not. For example, this is the typical case in Lagrangian relaxation of large-scale (possibly mixed-integer) optimization problems, in stochastic programming, and in robust optimization, where the oracles perform some numerical procedure to evaluate functions and subgradients, such as solving one or more optimization subproblems, multidimensional integration, or simulation. As a consequence, one cannot expect such oracles to provide exact data on the function values and/or subgradients. We review algorithms based on the bundle methodology, mostly developed quite recently, that have the ability to handle inexact data. We adopt an approach which, although not exaustive, covers various classes of bundle methods and various types of inexact oracles, for unconstrained and convexly constrained problems (with both convex and nonconvex objective functions), as well as nonsmooth mixed-integer optimization.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Numerical Solution of Generalized Minimax Problems
Nächstes Kapitel New Multiobjective Proximal Bundle Method with Scaled Improvement Function
Literatur
1.
Apkarian, P., Noll, D., Prot, O.: A proximity control algorithm to minimize nonsmooth and nonconvex semi-infinite maximum eigenvalue functions. J. Convex Anal. 16(3–4), 641–666 (2009)MathSciNetMATH
2.
Arnold, T., Henrion, R., Möller, A., Vigerske, S.: A mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraints. Pac. J. Optim. 10(1), 5–20 (2014)MathSciNetMATH
3.
Astorino, A., Frangioni, A., Fuduli, A., Gorgone, E.: A nonmonotone proximal bundle method with (potentially) continuous step decisions. SIAM J. Optim. 23(3), 1784–1809 (2013)CrossRefMathSciNetMATH
4.
Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer, Cham (2017)
5.
Bagirov, A.M., Karasözen, B., Sezer, M.: Discrete gradient method: derivative-free method for nonsmooth optimization. J. Optim. Theory Appl. 137(2), 317–334 (2008)CrossRefMathSciNetMATH
6.
Ben-Tal, A., Nemirovski, A.: Non-Euclidean restricted memory level method for large-scale convex optimization. Math. Program. 102, 407–456 (2005)CrossRefMathSciNetMATH
7.
Bonnans, J., Gilbert, J., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization. Theoretical and Practical Aspects. Universitext, 2nd edn., xiv+490 pp. Springer, Berlin (2006)
8.
Borghetti, A., Frangioni, A., Lacalandra, F., Nucci, C.: Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment. IEEE Trans. Power Syst. 18, 313–323 (2003)CrossRef
9.
10.
Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-free Optimization. MPS/SIAM Series on Optimization, vol. 8. Society for Industrial and Applied Mathematics (SIAM)/Mathematical Programming Society (MPS), Philadelphia (2009)
11.
12.
13.
14.
de Oliveira, W., Eckstein, J.: A bundle method for exploiting additive structure in difficult optimization problems. Technical report (2015)
15.
de Oliveira, W., Sagastizábal, C.: Bundle methods in the XXI century: a birds’-eye view. Pesquisa Operacional 34(3), 647–670 (2014)CrossRef
16.
de Oliveira, W., Sagastizábal, C.: Level bundle methods for oracles with on demand accuracy. Optim. Methods Softw. 29(6), 1180–1209 (2014)CrossRefMathSciNetMATH
17.
de Oliveira, W., Sagastizábal, C., Scheimberg, S.: Inexact bundle methods for two-stage stochastic programming. SIAM J. Optim. 21(2), 517–544 (2011)CrossRefMathSciNetMATH
18.
de Oliveira, W., Solodov, M.: A doubly stabilized bundle method for nonsmooth convex optimization. Math. Program. 156(1), 125–159 (2016)CrossRefMathSciNetMATH
19.
20.
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)CrossRefMathSciNetMATH
21.
Emiel, G., Sagastizábal, C.: Incremental-like bundle methods with application to energy planning. Comput. Optim. Appl. 46, 305–332 (2010)CrossRefMathSciNetMATH
22.
Fábián, C.I.: Bundle-type methods for inexact data. Central Eur. J. Oper. Res. 8, 35–55 (2000)MathSciNetMATH
23.
Fábián, C.I., Wolf, C., Koberstein, A., Suhl, L.: Risk-averse optimization in two-stage stochastic models: computational aspects and a study. SIAM J. Optim. 25(1), 28–52 (2015)CrossRefMathSciNetMATH
24.
Fischer, I., Gruber, G., Rendl, F., Sotirov, R.: Computational experience with a bundle approach for semidefinite cutting plane relaxations of max-cut and equipartition. Math. Program. 105(2), 451–469 (2006)CrossRefMathSciNetMATH
25.
Floudas, C.A.: Generalized Benders Decomposition, 2nd edn. Springer, Berlin (2009)
26.
27.
Fuduli, A., Gaudioso, M., Giallombardo, G.: Minimizing nonconvex nonsmooth functions via cutting planes and proximity control. SIAM J. Optim. 14(3), 743–756 (2004)CrossRefMathSciNetMATH
28.
Gaudioso, M., Giallombardo, G., Miglionico, G., Bagirov, A.M.: Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations. J. Global Optim. 71, 37–55 (2018)CrossRefMathSciNetMATH
29.
Genz, A., Bretz, F.: Computation of multivariate normal and t probabilities. No. 195 in Lecture Notes in Statistics. Springer, Dordrecht (2009)
30.
Gupal, A.M.: A method for the minimization of almost differentiable functions. Cybernetics 13(1), 115–117 (1977)MathSciNet
31.
Hare, W., Macklem, M.: Derivative-free optimization methods for finite minimax problems. Optim. Methods Softw. 28(2), 300–312 (2013)CrossRefMathSciNetMATH
32.
Hare, W., Nutini, J.: A derivative-free approximate gradient sampling algorithm for finite minimax problems. Comput. Optim. Appl. 56(1), 1–38 (2013)CrossRefMathSciNetMATH
33.
Hare, W., Sagastizábal, C.: A redistributed proximal bundle method for nonconvex optimization. SIAM J. Optim. 20(5), 2442–2473 (2010)CrossRefMathSciNetMATH
34.
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)CrossRefMathSciNetMATH
35.
36.
37.
Hiriart-Urruty, J., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I, 2nd edn., No. 305 in Grundlehren der mathematischen Wissenschaften. Springer, Berlin (1996)
38.
Hiriart-Urruty, J., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II, 2nd edn., No. 306 in Grundlehren der mathematischen Wissenschaften. Springer, Berlin (1996)
39.
40.
Joki, K., Bagirov, A.M., Karmitsa, N., Mäkelä, M.M.: A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes. J. Global Optim. 68(3), 501–535 (2017)CrossRefMathSciNetMATH
41.
Karmitsa, N., Gaudioso, M., Joki, K.: Diagonal bundle method with convex and concave updates for large-scale nonconvex and nonsmooth optimization. Optim. Methods Softw. 34(2), 363–382 (2019)CrossRefMathSciNetMATH
42.
43.
44.
Kiwiel, K.: Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization. Math. Program. 52(2), 285–302 (1991)CrossRefMathSciNetMATH
45.
Kiwiel, K.C.: Approximations in proximal bundle methods and decomposition of convex programs. J. Optim. Theory Appl. 84, 529–548 (1995)CrossRefMathSciNetMATH
46.
Kiwiel, K.C.: Restricted step and Levenberg-Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization. SIAM J. Optim. 6(1), 227–249 (1996)CrossRefMathSciNetMATH
47.
48.
Kiwiel, K.C.: A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 20(4), 1983–1994 (2010)CrossRefMathSciNetMATH
49.
Lemaréchal, C.: An extension of Davidon methods to nondifferentiable problems. Math. Program. Study 3, 95–109 (1975)CrossRefMATH
50.
Lemaréchal, C.: Lagrangian relaxation. In: Computational combinatorial optimization (Schloß Dagstuhl, 2000). Lecture Notes in Computer Science, vol. 2241, pp. 112–156. Springer, Berlin (2001)
51.
52.
Lukšan, L., Vlček, J.: A bundle-Newton method for nonsmooth unconstrained minimization. Math. Program. 83(3), 373–391 (1998)MathSciNetMATH
53.
Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization. Analysis and Algorithms with Applications to Optimal Control. World Scientific, River Edge (1992)
54.
Malick, J., de Oliveira, W., Zaourar, S.: Uncontrolled inexact information within bundle methods. EURO J. Comput. Optim. 5(1), 5–29 (2017)CrossRefMathSciNetMATH
55.
56.
Mifflin, R.: A modification and extension of Lemarechal’s algorithm for nonsmooth minimization. In: Sorensen D.C., Wets R.J.B. (eds) Nondifferential and Variational Techniques in Optimization. Mathematical Programming Studies, vol. 17, pp. 77–90. Springer, Berlin (1982)CrossRef
57.
58.
59.
Miller, S.: Inexact bundle method for solving large structured linear matrix inequalities. Ph.D. Thesis, University of California, Santa Barbara (2001)
60.
Montonen, O., Karmitsa, N., Mäkelä, M.M.: Multiple subgradient descent bundle method for convex nonsmooth multiobjective optimization. Optimization 67(1), 139–158 (2018)CrossRefMathSciNetMATH
61.
Nasri, A., Kazempour, S.J., Conejo, A.J., Ghandhari, M.: Network-constrained AC unit commitment under uncertainty: a Benders’ decomposition approach. IEEE Trans. Power Syst. 31(1), 412–422 (2016)CrossRef
62.
Noll, D.: Bundle method for non-convex minimization with inexact subgradients and function values. In: Computational and Analytical Mathematics. Springer Proceedings in Mathematics and Statistics, vol. 50, pp. 555–592. Springer, New York (2013)
63.
Noll, D., Apkarian, P.: Spectral bundle methods for non-convex maximum eigenvalue functions: first-order methods. Math. Program. 104(2), 701–727 (2005)CrossRefMathSciNetMATH
64.
Ouorou, A.: A proximal cutting plane method using Chebychev center for nonsmooth convex optimization. Math. Program. 119(2), 239–271 (2009)CrossRefMathSciNetMATH
65.
Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317. Springer, Berlin (1998)
66.
Ruszczyński, A.: Decomposition Methods. Handbooks in Operations Research and Management Science, vol. 10. Elsevier, Amsterdam (2003)
67.
68.
Sagastizábal, C.: On Lagrangian decomposition for energy optimization. In: Proceedings of the 8th International Congress on Industrial and Applied Mathematics, pp. 289–310. Higher Ed. Press, Beijing (2015)
69.
Sagastizábal, C., Solodov, M.: An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter. SIAM J. Optim. 16(1), 146–169 (2005)CrossRefMathSciNetMATH
70.
Solodov, M.V.: On approximations with finite precision in bundle methods for nonsmooth optimization. J. Optim. Theory Appl. 119(1), 151–165 (2003)CrossRefMathSciNetMATH
71.
Solodov, M.V.: A bundle method for a class of bilevel nonsmooth convex minimization problems. SIAM J. Optim. 18(1), 242–259 (2007)CrossRefMathSciNetMATH
72.
73.
Solodov, M.V., Zavriev, S.K.: Error stability properties of generalized gradient-type algorithms. J. Optim. Theory Appl. 98(3), 663–680 (1998)CrossRefMathSciNetMATH
74.
75.
van Ackooij, W., de Oliveira, W.: Level bundle methods for constrained convex optimization with various oracles. Comput. Optim. Appl. 57(3), 555–597 (2014)CrossRefMathSciNetMATH
76.
77.
78.
van Ackooij, W., Sagastizábal, C.: Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems. SIAM J. Optim. 24(2), 733–765 (2014)CrossRefMathSciNetMATH
79.
van Ackooij, W., Henrion, R., Möller, A., Zorgati, R.: Joint chance constrained programming for hydro reservoir management. Optim. Eng. 15, 509–531 (2014)MathSciNetMATH
80.
van Ackooij, W., Cruz, J.B., de Oliveira, W.: A strongly convergent proximal bundle method for convex minimization in Hilbert spaces. Optimization 65(1), 145–167 (2016)CrossRefMathSciNetMATH
81.
van Ackooij, W., Frangioni, A., de Oliveira, W.: Inexact stabilized Benders’ decomposition approaches with application to chance-constrained problems with finite support. Comput. Optim. Appl. 65(3), 637–669 (2016)CrossRefMathSciNetMATH
82.
Wolfe, P.: A method of conjugate subgradients for minimizing nondifferentiable functions. Math. Program. Stud. 3, 145–173 (1975)CrossRefMathSciNetMATH
Metadaten
Titel
Bundle Methods for Inexact Data
verfasst von
Welington de Oliveira
Mikhail Solodov
Copyright-Jahr
2020
Buch
Numerical Nonsmooth Optimization

Print ISBN: 978-3-030-34909-7

Electronic ISBN: 978-3-030-34910-3

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-34910-3_12