M2 course at the "Institut Polytechnique de Paris"Advanced Continuous Optimization

This page describes the 48 hour course given at "Institut Polytechnique de Paris" in the M2 Optimization, during the academic year 2020-2021, entitled Advanced Continuous Optimization. It contains
- the teacher internet pages,
- a short presentation of its contents,
- the detailed program of part I and part II.

The timetable of the other courses of the M2 is given here.

Teachers

Jean Charles Gilbert (Inria Paris),

Presentation

The first part of the module (30 hours) starts with the presentation of the optimality conditions of an optimization problem described in a rather general manner, so that these can be useful for dealing with a large variety of problems: the constraints are expressed by $c(x)\in G$, where $c:\mathbb{E}\to\mathbb{F}$ is a nonlinear map between two Euclidean spaces $\mathbb{E}$ and $\mathbb{F}$, and $G$ is a closed convex part of $\mathbb{F}$. Next, the course describes and analyzes various advanced algorithms to solve functional inclusions (of the kind $F(x)+N(x)\ni0$, where $F$ is a function and $N$ is a multifunction) and optimization problems (nonsmooth methods, linearization methods, proximal and augmented Lagrangian methods, interior point methods) and shows how they can be used to solve a few classical optimization problems (linear optimization, convex quadratic optimization, semidefinite optimization (SDO), nonlinear optimization). Along the way, various tools from convex and nonsmooth analysis will be presented. Everything is conceptualized in finite dimension. The goal of the lectures is therefore to consolidate basic knowledge in optimization, on both theoretical and algorithmic aspects.

The second part of the module (20 hours) focuses on the implementation of some of the previously seen algorithms in Matlab and allows the designer to understand its behavior and to evaluate its efficiency on a concrete problem. A choice will have to be made between the following three projects:

• the implementation of an SQP solver to solve the hanging chain problem (viewed as a nonlinear optimization problem);
• the implementation of a self-dual conic optimization (SDCO) solver in real numbers to solve various academic/concrete problems, such as the global minimization of a univariate polynomial or a few small size OPF problems (more precisely the rank relaxation of a QCQP version of this problem);
• the implementation of a semismooth-Newton-like algorithm to minimize a convex quadratic function on a convex polyhedron with application to the case when the polyhedron is the Birkhoff polytope.

To follow the second part, the student must have followed the first part, because the algorithms implemented in the second part are presented and anaylzed in the first part.

Detailed program

First part

• The course is composed of 7 lectures of 4h15 each, which makes it approximately 30h long. It is always given on Monday from 2:00 pm to 6:30 pm.
• Due to the corona virus pandemic, this year, the course is given online. You must contact Anne Richard (anne.richard@ensta-paris.fr) for having the authorization to enter ENSTA (this is automatically ensured for those who are registered to the M2).
• See below for the schedule.

Bibliography

• J.F. Bonnans, J.Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006). Numerical Optimization - Theoretical and Practical Aspects (second edition). Universitext, Springer Verlag, Berlin. [authors] [editor]
• J.F. Bonnans, A. Shapiro (2000). Perturbation Analysis of Optimization Problems. Springer Verlag, New York.
• A.L. Dontchev, R.T. Rockafellar (2009). Implicit Functions and Solution Mappings - A View from Variational Analysis. Springer Monographs in Mathematics. Springer.
• J.Ch. Gilbert (2015). Fragments d'Optimisation Différentiable - Théorie et Algorithmes. Syllabus de cours à l'ENSTA-ParisTech. [internet].
• J.-B. Hiriart-Urruty, C. Lemaréchal (1996). Convex Analysis and Minimization Algorithms (second edition). Grundlehren der mathematischen Wissenschaften, 305-306. Springer-Verlag.
• A.F. Izmailov, M.V. Solodov (2014). Newton-Type Methods for Optimization and Variational Problems. Springer Series in Operations Research and Financial Engineering, Springer.
• Y.E. Nesterov, A.S. Nemirovskii (1994). Interior-Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics, 13. SIAM, Philadelphia, PA, USA.
• J. Renegar (2001). A Mathematical View of Interior-Point Methods in Convex Optimization. MPS-SIAM Series on Optimization 3, SIAM.
• R.T. Rockafellar (1970). Convex Analysis. Princeton Mathematics Ser., 28. Princeton University Press, Princeton, New Jersey.
• R.T. Rockafellar, R. Wets (1998). Variational Analysis. Grundlehren der mathematischen Wissenschaften, 317. Springer.
• C. Roos, T. Terlaky, J.-Ph. Vial (2006). Interior Point Methods for Linear Optimization (second edition). Springer.
• S.J. Wright (1997). Primal-Dual Interior-Point Methods. SIAM Publication, Philadelphia.

Second part

It is recommended to register to this course, by contacting "Jean-Charles.Gilbert@inria.fr". Indeed, some technical issues depend on the participants (like having an account at Ensta and establishing access to Matlab through a VPN connection to Ensta, as explained on the page https://cascad.ensta.fr/BYOD).

The course is made up of 5 sessions of 3h45 each (given on Thursday, 2pm-6pm), which makes it 18h long, approximately.

The goal of the course is to guide the student in the implementation of one of some well known optimization/nonsmooth-system algorithms and in its use to solve a concrete problem. The student will choose one project among the following ones.

• Project SQP+HC. Implementation of an SQP algorithm (a solver of nonlinear optimization) and its use to solve the hanging chain problem. This project is recommended to those who have never implemented an optimization solver, since it is instructive on many aspects. The project is well organized and guided.
• Project SDCO+OPF. Implementation of an interior point algorithm to solve a self-dual conic optimization problem in real numbers (which concatenates several linear semidefinite optimization problems and one linear optimization problem) and its use to solve the rank relaxation of a small-size OPF problem (expressed as a QCQP problem) and global minimization of univariate polynomials on a finite union of intervals. The project is well organized and guided.
• Project SN+Proj. This last project is more exploratory with a large part dedicated to the understanding of all the aspects of a version of a semismooth Newton-like method for making the projection on a convex polyhedron. This is then applied abstractly and numerically to make the projection on the Birkhoff polytope and, more generally, to minimize a convex quadratic function (defined on the space of matrices) subject to the Birkhoff constraint. For the while (it may change during the course of the project), the project is completely left to the responsibility of the student, which makes this project closer to a research subject. The role of the teacher is therefore to discuss with the student during the realization of the project.
Students having already realized (part of) the SQP+HC project must choose another one.

Presentation of the projects (2021-01-19, 19:06). It is recommended to make your choice before the first session (and send it to "Jean-Charles.Gilbert@inria.fr"), although more information on the projects could be obtained at the beginning of the first session.

The material/concrete aspects of the course are still not determined, due to the pandemic (20-1-2021). Clearly, the course will be given online. Since it aims at realizing an optimization solver, the student must have the possibility to implement it on his/her machine, preferably in Matlab (or Octave?). If an access to Matlab is not furnished through Ensta (this has not been determined yet), there might be possible to use other free languages (preferably interpreters), like Python, Julia,..., but the teacher may not have the skill to guide the student with all these languages. The access to Matlab should be possible through a VPN channel to Ensta.

 Date Project SQP+HC Project SDCO+OPF Project SN+Proj ThursdayJanuary 282021 (2pm-6pm) Problem modeling and simulator design Oracle verification Notes Directions of displacement Notes Projection on the Birkhoff polytope ThursdayFebruary 42021 (2pm-6pm) The local SQP algorithm Notes (7-2-2021) Short report and code to submit before Sunday 7th of February, 10 pm Moving along the central path Notes Short report and code to submit before Sunday 7th of February, 10 pm ThursdayFebruary 112021 (2pm-6pm) Globalization by linesearch Short report and code to submit before Sunday 14th of February, 10 pm Finding an appropriate starting point Short report and code to submit before Sunday 14th of February, 10 pm ThursdayFebruary 182021 (2pm-6pm) Quasi-Newton version (Last session statement) Starting from an infeasible point ThursdayFebruary 252021 (2pm-6pm) A few applications ThursdayMarch 42021 Timetable Oral examination(discussion in front of the screen) Examination m2optim_2020_2021_a.m m2optim_2020_2021_b.m m2optim_2020_2021_c.m m2optim_2020_2021_d.m m2optim_2020_2021_e.m Oral examination(discussion in front of the screen) Oral examination(discussion in front of the screen)

Documents useful for the SQP+HC project:

Documents useful for the SDCO+OPF project:

Documents useful for the SN+Proj project: