Beyond First Order: V U $$\mathcal {V}\mathcal {U}$$ -Decomposition Methods

Shuai Liu () and Claudia Sagastizábal ()
Additional contact information
Shuai Liu: IMECC-UNICAMP
Claudia Sagastizábal: IMECC-UNICAMP

Chapter Chapter 9 in Numerical Nonsmooth Optimization, 2020, pp 297-329 from Springer

Abstract: 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 V U $${\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 U $${\mathcal {U}}$$ -subspace, where all the function “smoothness” concentrates at least locally. On its orthogonal complement, the “sharp” V $${\mathcal {V}}$$ -subspace, an intermediate iterate is defined such that the overall convergence is driven by the U $${\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 V U $${\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 V U $${\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.

Date: 2020
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-030-34910-3_9

Ordering information: This item can be ordered from
http://www.springer.com/9783030349103

DOI: 10.1007/978-3-030-34910-3_9

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().