Convex Optimization

Overview

Convexity plays a central role in the design and analysis of modern and highly successful algorithms for solving real-world optimization problems. The lecture (in English) on convex optimization will treat in a balanced manner theory (convex analysis, optimality conditions) and algorithms for convex optimization. Beginning with basic concepts and results about the structure of convex sets, continuity and differentiability of convex functions (including conjugate functions), the lecture will cover systems of inequalities, the minimum (or maximum) of a convex function over a convex set, Lagrange multipliers, duality theory and mini-max theorems. The course will be illustrated by many applications.

On the algorithmic part, we will cover several efficient classes of optimization methods. We will study Interior-Point Methods, and apply them to the fastly growing field of semidefinite optimization. We will show how to use one of the most powerful software to solve efficiently some semidefinite optimization problems. We will also study several sugradient-type methods, which are particularly well-designed for very large convex optimization problems.

The lecture will follow mostly albeit loosely the textbook by S. Boyd and L. Vandenberghe, Convex Optimization, made available on the net (download).

Contents

• Review of linear and convex quadratic programming.
• Convexity of sets and functions.
• Duality: weak and strong, complementary slackness. Certification of solutions.
• Second-order cones and semidefinite programming, geometric programming.
• Algorithms: Penalty and barrier functions, ellipsoid method, outer approximations and cutting planes, interior point, subgradient-type methods.
• Applications: Control system analysis and design, signal processing, circuit design, classification and support vector machines, quantum mechanics, portfolio optimization, experiment design,...

References

• A. Barvinok, A Course in Convexity. American Mathematical Society, 2003.

This well-written book covers convex analysis, with a particular emphasis on the interactions between convex analysis and combinatorial optimization problems. 

• A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization - Analysis, Algorithms, and Engineering Applications, MPS-SIAM Series on Optimization, MPS-SIAM.

This authoritative work displays a great variety of applications of convex optimization. It constitutes an ideal complement to the book of Boyd and Vandenberghe. Available upon request.

• D. P. Bertsekas, A. Nedic and A. E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, 2003.

• D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.

• S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

This thick book serves as one of the main references for the course. The authors deal with a number of applications of convex optimization in an impressive variety of fields. Click on the link to download.

• S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory. SIAM, 1994.

• E. de Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Book Series: APPLIED OPTIMIZATION, Vol. 65. Kluwer Academic Publishers.

• Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Book Series: APPLIED OPTIMIZATION, Vol. 87. Kluwer Academic Publishers.

This important book emerged from the lecture notes of Pr. Yurii Nesterov. It focuses on the study of algorithms for convex optimization, and, among others, interior-point methods. Available upon request.

• R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985.

This well-known book is an excellent reference on linear algebras.

• J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, MPS-SIAM Series on Optimization.

This short book has been developed from a graduate course of Jim Renegar. It contains an original analysis of interior-point methods, which complements beautifully the book of Nesterov. Available upon request.

• R.T. Rockafellar, Convex Analysis, Princeton University Press, 1997.

This is a classical and rather complete reference on convexity. Available upon request.

• H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Kluwer Academic Publishers.

This book is a collection of well-written reviews on a variety of aspects of semidefinite programming, including a discussion on its numerical behavior and the development of a robustness analysis.

• A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization, John Wiley, 1983.

This quite dense work focuses on the question "How efficient can optimization algorithms be ?". Available upon request.

• Y.  Nesterov and A. Nemirovski, Interior Point Polynomial Algorithms in Convex Programming, Studies in Applied Mathematics Vol. 13, SIAM, 1993.

This authoritative but hard book was the first to introduce the concept of self-concordance. It would be difficult to overestimate its importance and its influence on Convex Optimization during the last 15 years.

Requirements

For Bachelor and Master Students : At least 50% of the marks on the exercises qualifies you for the exam.

For PhD Students : Getting at least 50% of the marks on the exercises and passing the exam. The exam can be replaced by a term project on a topic chosen by the student in agreement with the instructors. If you are interested by a term project, please contact us by March 20. The due date for your report is August 15th, 2012.

Slides and exercises

Weekly exercises are downloadable every Thursday morning (click on the links at the left of this page). They are due for the next Tuesday at 17h00. You are allowed (and kindly advised) to group in pairs.

Useful Links

• SeDuMi and SDPT3, two excellent SDP solvers.
• YALMIP, a parser for writing SDP programs in MATLAB.