Méthodes de points intérieurs en programmation du cône du second ordre: une approche par algèbre de Jordan

  • Frank Russo

    Student thesis: Master typesMaster en sciences mathématiques

    Résumé

    L'objectif recherché dans ce mémoire est d'étudier la programmation du cône du second ordre et d'aboutir au développement de méthodes de points intérieurs pour la résolution de problèmes du cône du second ordre (problèmes SOCP). Un problème SOCP consiste à minimiser une fonction linéaire sur l'intersection d'un ensemble affine et d'un produit cartésien de cônes du second ordre. En premier lieu, nous donnons les définitions de base liées au cône du second ordre, pour ensuite présenter quelques exemples de problèmes de natures différentes pouvant se modéliser en problèmes SOCP. Après cela, nous introduisons une algèbre "taillée sur mesure" pour les problèmes SOCP en étudiant le concept d'algèbre de Jordan. La compréhension de cette algèbre est essentielle pour aborder, par la suite, les notions de dualité faible et forte, conditions de complémentarité, non-dégénérescence et complémentarité stricte. Nous terminerons par le développement de méthodes de points intérieurs utilisant des algorithmes de suivi de chemins de complexité polynomiale. Enfin, nous donnons en annexe la preuve de résultats techniques ainsi que la description complète de quelques exemples concrets de problèmes SOCP accompagnée de résultats numériques.
    la date de réponse27 juin 2003
    langue originaleFrançais
    SuperviseurJean-Jacques STRODIOT (Promoteur), Frank CALLIER (Jury) & Van Hien Nguyen (Jury)

    Contient cette citation

    '