Faculté des sciences économiques et sociales

The homogeneous analytic center cutting plane method

Péton, Olivier ; Vial, Jean-Philippe (Dir.)

Thèse de doctorat : Université de Genève, 2002 ; SES 532.

La méthode homogène des centres analytiques est une méthode de plans coupants pour l'optimisation convexe, combinant les propriétés des fonctions self-concordantes et la robustesse de la méthode des centres analytiques. A chaque itération, un centre analytique est défini comme le point minimisant une fonction potentielle self-concordante. Un oracle de premier ordre renvoie un plan coupant... Plus

Ajouter à la liste personnelle
    Résumé
    La méthode homogène des centres analytiques est une méthode de plans coupants pour l'optimisation convexe, combinant les propriétés des fonctions self-concordantes et la robustesse de la méthode des centres analytiques. A chaque itération, un centre analytique est défini comme le point minimisant une fonction potentielle self-concordante. Un oracle de premier ordre renvoie un plan coupant enrichissant la définition de l'ensemble de localisation courant. Durant tout le processus, le problème est plongé dans un espace homogène tandis que l'oracle reste dans l'espace d'origine. Nous étudions tout d'abord la convergence de l'algorithme avec des centres analytiques approchés. Puis nous considérons le cas où l'oracle renvoie simultanément plusieurs coupes : la preuve de complexité fait appel à des résultats récents sur les barrières self-concordantes augmentées. Finalement, nous appliquons la méthode homogène à des problèmes d'inégalités variationnelles et de séparation.