Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
9. Beyond First Order: \(\mathcal {V}\mathcal {U}\)-Decomposition Methods
verfasst von : Shuai Liu, Claudia Sagastizábal
Erschienen in: Numerical Nonsmooth Optimization
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
When minimizing a nonsmooth convex function bundle methods are well known by their robustness and reliability. While such features are related to global convergence properties of the algorithm, speed of convergence is a different matter, as fast rates cannot be expected if the objective function lacks smoothness.
In the typical bundle dichotomy that splits iterates between null and serious steps, the latter subsequence converges with R-linear speed. Moving from the first-order method realm to the world of superlinear speed is possible when realizing that nonsmoothness often appears in a structured manner. This is the basis of the \({\mathcal {V}\mathcal {U}}\)-decomposition approach presented in this chapter. Thanks to this decomposition, it is possible to make a Newton-like move in certain \({\mathcal {U}}\)-subspace, where all the function “smoothness” concentrates at least locally. On its orthogonal complement, the “sharp” \({\mathcal {V}}\)-subspace, an intermediate iterate is defined such that the overall convergence is driven by the \({\mathcal {U}}\)-step. As a result, the serious-step subsequence converges with superlinear speed.
By focusing on the proximal variants of bundle methods, this chapter introduces gradually the \({\mathcal {V}\mathcal {U}}\)-theory and the ingredients needed to build superlinearly convergent algorithms in nonsmooth optimization. For functions whose proximal points are easy to compute, as in machine learning, an implementable quasi-Newton \({\mathcal {V}\mathcal {U}}\)-algorithm is given. The bundle machinery is incorporated for functions whose proximal points are not readily available. In this case, superlinear speed can be achieved by solving two quadratic programming problems per iteration.