M2 course at the "Institut Polytechnique de Paris"
Advanced Continuous Optimization
This page describes the 60 hour course given at "Institut Polytechnique de Paris" in the
M2 Optimization,
during the academic year 20202021, entitled Advanced
Continuous Optimization. It contains
 the teacher internet pages,
 a short presentation of its contents,
 the detailed program of part I, part II, and part III.
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 selfdual 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 semismoothNewtonlike algorithm to minimize a convex quadratic function on a convex polyhedron with
application to the case when the polyhedron is the Birkhoff polytope.
The third part of the module is a 10 hour lecture given by ...
From an academic point of view, the second and third parts are considered to form a same teaching unit, so that they are
evaluated together and give rise to a single note. Furthermore, to follow the second and third parts, one must have followed the
first part, because the algorithms implemented in the second part are presented and anaylzed in the first part.
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.

The course is given at ENSTA, room ...
You must contact Anne Richard (anne.richard@enstaparis.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.
Postlecture notes, slides, and exercises (the access to these notes requires the username "Student" and the given password):
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'ENSTAParisTech.
[internet].

J.Ch. Gilbert (2019).
Selected topics on Optimization (Lecture Notes of the M2 course Advanced Continuous Optimization at IPP in 20192020).
[hal].

J.B. HiriartUrruty, C. Lemaréchal (1996).
Convex Analysis and Minimization Algorithms (second edition).
Grundlehren der mathematischen Wissenschaften, 305306.
SpringerVerlag.

A.F. Izmailov, M.V. Solodov (2014).
NewtonType Methods for Optimization and Variational Problems.
Springer Series in Operations Research and Financial Engineering,
Springer.

Y.E. Nesterov, A.S. Nemirovskii (1994).
InteriorPoint Polynomial Algorithms in Convex Programming.
SIAM Studies in Applied Mathematics, 13.
SIAM, Philadelphia, PA, USA.

J. Renegar (2001).
A Mathematical View of InteriorPoint Methods in Convex Optimization.
MPSSIAM 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).
PrimalDual InteriorPoint Methods.
SIAM Publication, Philadelphia.
Actual program on a daily basis
Date 
Themes of the lectures 
Actual details of the contents of the lectures 
  
Monday November 16 2020 
Presentation and recalls 
Presentation of the course
Background
 Convex analysis: relative interior, absorbing point, dual cone and Farkas lemma, tangent and normal cones
 Nonlinear analysis: multifunction
 Optimization: tangent cone and PeanoKantorovich necessary optimality condition of the first order for $(P_X)$,
sufficient optimality condition of the first order for a convex problem $(P_X)$, KKT conditions for $(P_{EI})$,
sufficient conditions for contraint qualification

  
Monday November 23 2020 
  
Monday November 30 2020 
  
Monday December 7 2020 
  
Monday December 14 2020 
  
Monday January 4 2020 
  
Monday January 11 2020 
  
Monday January 18 2021 
Examination 
It is composed of 5 sessions of 4h each (on Monday 14h18h), which makes it 20h long.
Examination: ...
The goal of this course is to guide the student in the implementation of some well known optimization algorithms and in its use
to solve a concrete problem. The student will choose among the following two projects.
 Project SQP+HC. Implementation of an SQP algorithm (a solver of nonlinear optimization) and its use to solve
the hanging chain problem.
 Project SDCO+OPF. Implementation of an interior point algorithm to solve a selfdual conic optimization problem in
real numbers (which includes linear semidefinite optimization and linear optimization) and its use to solve the rank relaxation
of a smallsize OPF problem (expressed as a QCQP problem) and global minimization of univariate polynomials on a finite union of
intervals.
 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 Newtonlike 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.
Ensta students having already realized the SQP+HC project must choose another one.
Presentation of the projects ...
Actual program on a daily basis
...
Pieces of code useful for the SQP+HC project:
...
Pieces of code useful for the SDCO+OPF project:
...
A 10 hour lecture by ...
A short report on these lectures (a PDF file) should be sent before ... at the address
JeanCharles.Gilbert@inria.fr.