
MAT932  Convex Optimization  Michel Baes  FS 16     Do  15.0017.00  Y35F32     Downloads: Archive Lecture 1: Introduction, Convex sets Lecture 2: The Semidefinite Cone, Separation theorems Lecture 3: Duality Lecture 4: Optimality conditions, Lagrangian Duality Lecture 5: Subgradients, conjugate functions Lecture 6: KKT Conditions and applications Lecture 7: Conic Optimization and applications Lecture 8: Selected applications of Semidefinite Optimization Lecture 9: Selected applications of convex optimizationLecture 10: BlackBox Methods 1Lecture 11: BlackBox Methods 2Lecture 12: Selfconcordant functions and interiorpoint methods Overview
Convexity plays a central role in the design and analysis of modern and highly successful algorithms for solving realworld 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.
Starting with basic results on convex sets and functions, with a particular emphasis on semidefinite sets, we develop a selfcontained duality theory for convex optimization problems. As instrumental tools in the theory of Lagrange multipliers and optimality conditions for convex optimization problems, we introduce the notions of subdifferential and conjugate functions. The course will be illustrated by many applications in accordance with the interests of the audience.
On the algorithmic part, we cover several classes of optimization methods, from the simple subgradient method to mirrordescent schemes and InteriorPoint Methods. Several exercise sessions will be devoted to the familiarization of software to solve efficiently some semidefinite 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)
Lecturebylecture references
These slides are designed to be selfcontained; I consider
them as an adequate substitute to a reference book.
Many thanks to all the students who spotted typos and inaccuracies
in earlier versions of those slides. Their questions and comments
also helped a lot.
You can find below a nonexhaustive list of references that inspired me,
and that can be used as further reading material. Do not hesitate to
contact me if you need further references in optimization, more related
to your field of primary interest.
Lecture 1
Sparse signal recovery
G. Pope, C. Studer, and M. Baes, "Coherencebased recovery guarantees for generalized basispursuit dequantizing", Proceedings of the 37th IEEE International Conference on Acoustics, Speech, and Signal Processing,
Kyoto.
Portfolio optimization
S. Boyd, L. Vandenberghe, "Convex Optimization", Section 4.4.1.
Positron Emission Tomography:
A. BenTal, T. Margalit, and A. Nemirovski, "The Ordered Subsets Mirror Descent Optimization Method with Applications to Tomography", SIAM Journal on Optimization, 12(2001), pp. 79108.
Lecture 2
Semidefinite Optimization
L. Vandenberghe and S. Boyd, "Semidefinite programming", SIAM Review, 38(1996), n. 1, pp. 4995.
Separation Theorems
Laurent Schwartz, "Analyse 1: Théorie des ensembles et topologie", Hermann, 1997.
Lectures 3, 4
J. Tind and L. Wolsey, "An elementary survey of general duality theory in Mathematical Programming", Mathematical Programming 21(1981), pp. 241261.
A. BenTal, A. Nemirovski, "Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications", MPS/SIAM Series on Optimization, n. 2, SIAM, 2001. Lecture 2.
Support vector machines
S. Boyd, L. Vandenberghe, "Convex Optimization", Section 8.6.
Lectures 5, 6
R. Rockafellar, "Convex Analysis", Princeton Mathematics Series, n. 28, Princeton University Press, 1970.
Y. Nesterov, "Introductory lectures on convex optimization: a basic course", Applied Optimization Series, n. 87, Kluwer Academic Publishers, 2003. Section 3.1.
Lecture 7
Introduction and applications: S. Boyd, L. Vandenberghe, "Convex Optimization", Chapter 1 and Section 4.4.2.
CQr and SDr: A. BenTal, A. Nemirovski, "Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications", MPS/SIAM Series on Optimization, n. 2, SIAM, 2001. Lectures 3 and 4.
References
A. Barvinok, A Course in Convexity. American Mathematical Society, 2003.
This
wellwritten book covers convex analysis, with a particular emphasis on
the interactions between convex analysis and combinatorial optimization
problems.
A. BenTal and A. Nemirovski,
Lectures on Modern Convex Optimization  Analysis, Algorithms, and
Engineering Applications, MPSSIAM Series on Optimization, MPSSIAM.
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, interiorpoint methods. Available upon request..
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985.
This wellknown book is an excellent reference on linear algebra. Its sequel "Topics in Matrix Analysis" is also a classic. Available upon request.
J. Renegar, A Mathematical View of InteriorPoint Methods in Convex Optimization, MPSSIAM Series on Optimization.
This
short book has been developed from a graduate course of Jim Renegar. It
contains an original analysis of interiorpoint 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
wellwritten 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 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
selfconcordance. It would be difficult to overestimate its importance
and its influence on Convex Optimization during the last 20 years.
Useful Links
 SeDuMi and SDPT3, two excellent SDP solvers.
 YALMIP, a parser for writing SDP programs in MATLAB.
Module: 14.07.2016 9:0012:30, Room:Y27H25, Typ: mündlich Repetition: 12.09.2016 10:0012:00, Room:Y27H26, Typ: mündlich http://www.vorlesungen.uzh.ch/ 