Past lectures

Abstract

The main goal of this course is a development of a correct understanding of complexity of nonlinear optimization problems. We provide different problem classes (general nonlinear optimization, smooth and non-smooth convex optimization) with lower complexity bounds. We present the numerical schemes with provable efficiency estimates, which are optimal for corresponding problem classes. We compare these results with efficiency of numerical methods based on explicit treatment of the structure of optimization problems (polynomial-time interior-point methods). In the last three lectures of the course we discuss different directions for further developments in nonlinear optimization.

The course is self-contained. We assume that the participants have a standard undergraduate background in analysis and linear algebra.

This course is based on the following recent publications of the author:

1. Yu.Nesterov. "Introductory lectures on convex optimization. Basic course", Kluwer 2003.

2. Yu.Nesterov. Smooth minimization of non-smooth functions. CORE DP, 2003/12.

3. Yu.Nesterov. Excessive gap technique in non-smooth convex minimization. CORE DP, 2003/35.

4. Yu.Nesterov, B.Polyak. Cubic regularization of a Newton scheme and its global performance. CORE DP, 2003/41.

5. Yu.Nesterov. Primal-dual subgradient methods. CORE DP (in preparation).

The monograph [1] is available starting from August 2003. Papers [2-5] can be downloaded from CORE web page.