Convex analysis and optimization

I. Introduction

Lection 1. Examples of optimization problems in engineering, economics, data mining, parameter estimation, signal and image processing, classification and pattern recognition, learning. Types of optimization problems and main tools for their analysis.

II. Linear algebra

Lection 2. Vector and matrix norms, convergence of iterations, positive matrices, stochastic matrices, nonnegative definite matrices, linear matrix inequalities.

III. Convex analysis

Lection 3. Convex sets and functions. Their properties, main theorems. Convexity criteria. Polyhedra and cones. Projections. Support function.
Lection 4. Separation theorems. Duality. Matrix games and minima[ theorem. Linear programming. Simplex method.

IV. Optimization

Lection 5. Smooth unconstrained minimization. Extremum conditions. Gradient method and its modifications. Newton method.
Lection 6. Nonsmooth convex unconstrained minimization. Subgradient and its calculation. Subgradient method. Cutting plane methods.
Lection 7. Equality constraints. Lagrange multipliers. Trust region methods.
Lection 8. Convex programming. Kuhn-Tucker theorem. Saddle point methods. Self-concordant functions. Barriers. Interior-point methods. Polynomial methods.

V. Applications

Lection 9. Matrix optimization. Semi-definite programming. Solution tools: Yalmip, LMI Toolbox, cvx.
Lection 10. Global optimization. Its complexity for Lipshitz functions. Random search. Multi-start methods. Heuristical approaches.
Lection 11. Regression. Least squares and least absolute value methods. Maximal likelihood method. Nonlinear regression. L1 optimization. Lasso. Sparse optimization.
Lection 12. Ranking problems. PageRank and its calculation. Classification and pattern recognition. SVM technique. Data mining. Cluster analysis.


B.T.Polyak, Introduction to optimization, NY, Optimization Software, 1987.
S.Boyd, L. Vanderberghe, Convex optimization, Cambridge, Cambridge Univ. Press, 2004.
Yu.Nesterov, Introductory lectures on convex optimization. A basic course,Boston, Kluwer, 2004.
A.Ben-Tal, A. Nemirovski, Lectures on modern convex optimization: analysis, algorithms and engineering applications, SIAM, Philadelphia, 2001.