Optimization in Relative Scale

Yurii Nesterov
Additional contact information
Yurii Nesterov: Catholic University of Louvain

Chapter Chapter 7 in Lectures on Convex Optimization, 2018, pp 489-570 from Springer

Abstract: Abstract In many applications, it is difficult to relate the number of iterations in an optimization scheme with the desired accuracy of the solution since the corresponding inequality contains unknown parameters (Lipschitz constant, distance to the optimum). However, in many cases the required level of relative accuracy is quite understandable. To develop methods which compute solutions with relative accuracy, we need to employ internal structure of the problem. In this chapter, we start from problems of minimizing homogeneous objective functions over a convex set separated from the origin. The availability of the subdifferential of this function at zero provides us with a good metric, which can be used in optimization schemes and in the smoothing technique. If this subdifferential is polyhedral, then the metric can be computed by a cheap preliminary rounding process. We also present a barrier subgradient method, which computes an approximate maximum of a positive convex function with certain relative accuracy. We show how to apply this method to solve problems of fractional covering, maximal concurrent flow, semidefinite relaxation, online optimization, portfolio management, and others. Finally, we consider a class of strictly positive functions, for which a kind of quasi-Newton method is developed.

Date: 2018
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:spochp:978-3-319-91578-4_7

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

DOI: 10.1007/978-3-319-91578-4_7

Access Statistics for this chapter

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