Step by step design of an interior-point solver in self-dual conic optimization: Application to the Shor relaxation of some small OPF problems

Résumé : Ces notes présentent un projet d'optimisation numérique dans lequel on implémente une méthode de points intérieurs pour résoudre un problème d'optimisation conique auto-duale (OCAD). Le cône est le produit cartésien de cônes de matrices semi-définies positives de dimensions variables et d'un orthant positif. Dès lors, le problème contient l'optimisation semi-défiinie et l'optimisation linéaire. Ce projet a été proposé dans un cours intitulé "Advanced Continuous Optimization II" à l'université Paris-Saclay, en 2016-1017. Le solveur est conçu pas à pas durant une suite de 5 leçons de 4 heures chacune. Chaque session fait l'objet d'un chapitre de ces notes. La bonne marche du solveur OCAD est vérifiée à chaque session sur de petits problèmes académiques, ayant diverses propriétés. Durant la dernière session, le code développé est utilisé pour résoudre la relaxation de Shor de la formulation QCQP (quadratically constrained quadratic programming) de quelques problèmes d'optimisation de flux d'énergie (OPF) dans de petits réseaux de distribution d'électricité. Ces notes prolongent celles du cours donné en 2015-2016, en augmentant les capacités du code précédemment développé. L'ajout principal est de permettre la prise en compte de plusieurs matrices semi-définies positives (au lieu d'une), ainsi que d'un vecteur positif (inexistant précédemment). Le but de ce cours n'est pas de concevoir un solveur OCAD qui surpasserait le meilleur solveur existant, mais d'aider l'étudiant à comprendre et à démythifier ce que contient un tel solveur. Une conséquence secondaire de cet exercice est de montrer qu'un code OCAD assez performant peut être réalisé en très peu de temps.
Type de document :
Cours
Master. Advance Continuous Optimization II, France. 2016, pp.49
Liste complète des métadonnées

Littérature citée [42 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/cel-01252612
Contributeur : Jean Charles Gilbert <>
Soumis le : samedi 17 décembre 2016 - 13:04:54
Dernière modification le : jeudi 22 décembre 2016 - 10:31:34

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

Collections

Citation

Jean Charles Gilbert. Step by step design of an interior-point solver in self-dual conic optimization: Application to the Shor relaxation of some small OPF problems. Master. Advance Continuous Optimization II, France. 2016, pp.49. 〈cel-01252612v2〉

Partager

Métriques

Consultations de la notice

244

Téléchargements de fichiers

174