Skip to Main content Skip to Navigation
Lectures

Step by step design of an interior-point solver in self-dual conic optimization, with applications

Abstract : These notes present a project in numerical optimization dealing with the implementation of an interior-point method for solving a self-dual conic optimization (SDCO) problem. The cone is the Cartesian product of cones of positive semidefinite matrices of various dimensions (imposing to matrices to be positive semidefinite) and of a positive orthant. Therefore, the solved problem encompasses semidefinite and linear optimization. The project was given in a course entitled 'Advanced Continuous Optimization II' at the University Paris-Saclay, in 2016-2020. The solver is designed step by step during a series of 5 sessions of 4 hours each. Each session corresponds to a chapter of these notes (or a part of it). The correctness of the SDCO solver is verified during each session on small academic problems, having diverse properties. During the last session, the developed piece of software is used to minimize a univariate polynomial on an interval and to solve a few small size rank relaxations of QCQO (quadratically constrained quadratic optimization) problems, modeling various instances of the OPF (optimal power flow) problem. The student has to master not ony the implementation of the interior-point solver, but is also asked to understand the underliying theory by solving exercises consisting in proving some properties of the implemented algorithms. The goal of the project is not to design an SDCO solver that would beat the best existing solver but to help the students to understand and demystify what there is inside such a piece of software. As a side outcome, this course also shows that a rather performent SDCO solver can be realized in a relatively short time.
Document type :
Lectures
Complete list of metadata

Cited literature [54 references]  Display  Hide  Download

https://hal.inria.fr/cel-01252612
Contributor : Jean Charles Gilbert <>
Submitted on : Thursday, December 19, 2019 - 10:54:48 AM
Last modification on : Monday, January 13, 2020 - 1:19:07 AM

File

sbs-sdco-2019-12-19.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

Collections

Citation

Jean Charles Gilbert. Step by step design of an interior-point solver in self-dual conic optimization, with applications. Master. Advance Continuous Optimization II, France. 2019, pp.67. ⟨cel-01252612v3⟩

Share

Metrics

Record views

109

Files downloads

414