JFRO Journées Franciliennes de Recherche Opérationnelle
Prochaine JFRO Précédentes JFRO
LE JEUDI 23 JUIN 2016 Sur le thème PROGRAMMATION QUADRATIQUE Au Conservatoire National des Arts et Métiers (Amphi Friedmann, accès 33, 2ème étage, 33.2.20) 2, rue Conté, 75003 Paris S'y rendre Inscription : Merci de remplir le formulaire d'inscription 9h30 - 10h00 :
Accueil des participants 10h00 - 12h00 :
Résolution des programmes quadratiques par reformulation Sourour Elloumi
Les programmes quadratiques en variables binaires, ou en variables mixtes-entières ont un très vaste champ d'application mais leur résolution reste difficile. Nous passons en revue les types de méthodes utilisées. Ensuite, nous focalisons sur la résolution par reformulation, linéaire ou quadratique convexe. Nous considérons en particulier le cas de la linéarisation compacte pour la programmation quadratique en variables binaires. Nous montrons que différentes linéarisations sont possibles et qu'une linéarisation "optimale" dans un certain sens peut être obtenue. Nous présentons ensuite l'approche par reformulation quadratique convexe et montrons, de façon analogue, comment obtenir une reformulation quadratique convexe optimale dans le même sens. Enfin, nous mettons en avant la généralisation de cette approche vers la programmation quadratique en variables entières ou en variables continues. 12h00 - 14h00 :
Pause déjeuner 14h00 - 14h40 :
Comment l'algorithme du lagrangien augmenté peut traiter un problème
d'optimisation quadratique convexe non réalisable - motivation, analyse,
implémentation Jean-Charles Gilbert INRIA - Paris Transparents de la présentation La méthode du lagrangien augmenté (LA) ou méthode des multiplicateurs
est utilisée depuis longtemps pour résoudre des problèmes d'optimisation
non linéaire. Elle continue à faire l'objet de nouvelles implémentations
et d'amélioration.
Plus récemment, divers auteurs se sont intéressés à son utilisation dans
des problèmes plus structurés: optimisation linéaire, quadratique, SDP,
Dans cet exposé, nous analyserons le comportement de l'algorithme
lorsqu'il cherche à résoudre un problème quadratique convexe non
réalisable (contraintes incompatibles) ou non borné. Ce comportement est
important à maîtriser lorsque le problème quadratique est généré par un
algorithme newtonien (SQP) pour résoudre un problème d'optimisation non
linéaire. Nous montrerons que, lorsque le problème quadratique n'est pas
réalisable, l'algorithme du LA trouve la solution du problème réalisable
le plus proche (qui sera défini), avec une convergence linéaire globale
vers une telle solution et un taux inversement proportionnel au
paramètre d'augmentation. Ce résultat permet de concevoir une règle de
mise à jour du paramètre d'augmentation. Nous donnerons également des
résultats numériques préliminaires permettant de comparer l'efficacité
de l'approche par rapport à d'autres codes d'activation de contrainte et
de points intérieurs.
Ce travail a été réalisé en collaboration avec Alice Chiche et Émilie
Joannopoulos.
Inexact stabilized Benders’ decomposition approaches with applications to MIQCQP problems Wim Van Ackooij EDF Joint work with A. Frangioni and W. de Oliveira Transparents de la présentation In this talk we will discuss modifications of standard cutting-plane approaches for minimizing a convex nondifferentiable function, given by an oracle, over a combinatorial set, which is the basis of the celebrated (generalized) Benders’ decomposition approach. Specifically, we combine stabilization—in two ways: via a trust region in the L1 norm, or via a level constraint—and inexact function computation (solution of the subproblems). Managing both feature s simultaneously requires a nontrivial convergence analysis; we provide it under very weak assumptions on the handling of the two parameters (target and accuracy) controlling the informative on-demand inexact oracle corresponding to the subproblem, strengthening earlier know results. This yields new versions of Benders’ decomposition, whose numerical performance is illustrated on specific MIQCQP problems. Several other aspects of the relation of these methods to quadratic programming will also be discussed. 15h20 - 15h40 :
Pause café 15h40 - 16h20 :
Application of Dantzig-Wolfe Reformulation to Binary Quadratic Problems Emiliano Traversi AOC - LIPN Transparents de la présentation In this work we investigate the behaviour of Dantzig Wolfe Decomposition when applied to Binary Quadratic Programming.
Several decomposition are compared from a theoretical and experimental point of view. As test case we use the 0-1 k-item Quadratic Knapsack Problem.
We show that with a proper reformulation we are able to close in the majority of the cases the whole integrality gap in a reasonable amount of time, solving to proven optimality more instances than a generic solver can do. 16h20 - 1700 :
Optimisation de portefeuille par programmation quadratique Sylvain Mouret Artelys This talk is focused on a practical application of quadratic programming to an application in Finance. The problem is to determine an asset portfolio composition, so as to minimize the Conditional Value-at-Risk (CVar) while maintaining a reasonable Tracking Error with respect to a benchmark portfolio. The CVaR is used instead of the Value-at-Risk as it is a coherent risk measure. We will present the underlined quadratically constrained model, solved with Knitro (general nonlinear solver), and some results obtained in an industrial setup.