Groupe d’études et de recherche en analyse des décisions

G-2020-37

A symmetric formulation of the linear system arising in interior methods for convex optimization with bounded condition number

, et

Nous développons des bornes sur les valeurs propres d’une nouvelle formulation des équations de Newton dans les méthodes de points intérieurs pour l’optimisation convexe. La matrice de notre formulation, nommée \(K_{2.5}\), a un nombre de conditionnement borné, converge vers une limite bien définie sous l’hypothèse de complémentarité stricte, et est de la même taille que la formulation de point de selle mal conditionnée traditionnelle. Nous évaluons sa performance dans le contexte d’une nouvelle implémentation Matlab orientée objet de PDCO, un logiciel de points intérieurs pour la minimisation de fonctions convexes lisses sous contraintes linéaires. L’avantage principal de notre implémentation, nommée PDCOO, est de séparer la logique de la méthode de points intérieurs de la formulation du système utilisé pour calculer un pas à chaque itération et de la méthode utilisée pour résoudre ce système. Ainsi, PDCOO permet d’ajouter facilement une nouvelle formulation et/ou une nouvelle méthode de résolution pour effectuer des essais. Nos résultats numériques indiquent que la formulation \(K_{2.5}\) requiert la même quantité de mémoire que la formulation mal conditionnée traditionnelle et que son nombre de conditionnement est significativement meilleur que celui de la formulation non symétrique \(3 \times 3\).

, 26 pages