Introductory lectures on convex optimization : a basic course / Yurii Nesterov

The book is written as a course, where the most efficient optimization schemes are discussed and for them efficiency bounds have been established. The course is self contained, with all necessary proofs inside, which should not be a problem even for graduate students. The book consists of four independent chapters, each of them including three sections, corresponding approximately to a two-hour lecture. So, the book can be directly used for a standard one-semester course. Chapter 1 is devoted to general optimization problems. The author introduces the notions of oracle, black box, functional model of an optimization problem and the complexity of general iterative scheme. The gradient and the Newton methods have been discussed, together with their local rates of convergence. Chapter 2 considers the optimal schemes for smooth convex optimization minimization problems, starting with unconstrained and then with more complicated problems, which involve several smooth convex functions, namely, the minimax problem and the constrained minimization problems. For both problems the notion of gradient mapping has been introduced and the optimal schemes are presented. Chapter 3 is devoted to the theory of nonsmooth convex optimization. After presenting some necessary facts of convex analysis the author starts from the lower complexity bounds for nonsmooth optimization problems and then presents a general scheme for complexity analysis of the corresponding methods. This scheme is used to establish the convergence rate of the subgradient method, the center-of-gravity method, the ellipsoid method and some cutting plane schemes. In the last section minimization schemes, which employ a piece-wise linear model of convex function are presented. Convex minimization problems with explicit structure are considered in the last Chapter. The author introduces barrier model of an optimization problem, which is based on the notion of self-concordant function, and studies the properties of these functions. The subclass of these functions, self-concordant barriers, has been investigated and applied to sequential unconstrained minimization schemes, as well. In the last section of the chapter, there are several examples of optimization problems, for which can be constructed a self-concordant barrier, and, consequently these problems can be solved by a path-following scheme. The book concludes by a comparison of an interior-point method scheme with a nonsmooth optimization method as applied to a particular prob lem instance. (zbMath)

Bibliogr. p. 233-234. Index