 |
A Globally--Interior Point Method in a Cutting-Planes context
1 : Centre d'études et de recherche en informatique et communications
Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise : EA4629, Conservatoire National des Arts et Métiers [CNAM] : EA4629, Ecole Nationale Supérieure d\'Informatique pour l\'Industrie et l\'Entreprise : EA4629
Il existe déjà des algorithmes de plans coupants qui déterminent l'optimum à
l'itération courante grâce à une méthode de points intérieurs. J'essaye de
surmonter l'inconvénient suivant: les points intérieurs générés par une telle
méthode sont intérieurs par rapport au polytope courant et non pas par rapport au polytope
global (avec toutes les contraintes). L'outil principal pour s'assurer de garder ces
points à l'intérieur du polytope global est le sous-problème de projection:
étant donné un point x et une direction d, quelle est la longueur de pas
maximale t tel que x+td reste dans le polytope global, comme proposée dans le
papier [Daniel Porumbel. Projective Cutting-Planes. SIAM Journal on
Optimization, 30(1): 1007-1032, 2020.]
