Accueil des participants

Résolution des programmes quadratiques par reformulation

Sourour Elloumi

ENSIIE - SAMOVAR

Transparents de la présentation

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.

Pause déjeuner

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, conique. 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.

Pause café

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.

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.