Plea for a semidefinite optimization solver in complex numbers – The full report

Résumé : L'optimisation numérique en nombres complexes a attiré beaucoup moins l'attention qu'en nombres réels. Une opinion répandue est que, puisqu'un nombre complexe est un couple de nombres réels, la meilleure stratégie pour résoudre un problème d'optimisation en nombres complexes est de le transformer en nombres réels et de résoudre ce dernier par un solveur réel. Cet article défend un autre point de vue et présente quatre arguments pour convaincre le lecteur que se passer de la transformation et d'utiliser un algorithme en nombres complexes, lorsqu'un tel algorithme est disponible, peut parfois être beaucoup plus efficace. Ceci est mis en évidence pour le cas particulier des problèmes d'optimisation semi-définie positive résolus par une méthode de points-intérieurs primale-duale réalisable utilisant la technique des prédictions-corrections. Dans ce cas, la formulation en nombres complexes a l'avantage (i) de requérir moins d'espace-mémoire, (ii) d'avoir une itération plus rapide, (iii) de nécessiter moins d'itérations et (iv) d'avoir des ensembles admissible et de solutions plus petits. Le gain en temps de calcul vient du fait que certaines opérations (comme le produit de deux matrices) sont beaucoup plus rapides pour des opérandes complexes que pour leurs contreparties réelles de taille double, si bien que les conclusions de cet article pourraient aussi être valables pour d'autres problèmes dans lesquels ces opérations interviennent pour une bonne part dans le temps de calcul. Le gain en nombre d'itérations provient de la dimension plus petite (bien que complexe) du problème en nombres complexes. Une expérimentation numérique montre que toutes ces propriétés conduisent a un code qui s'exécute jusqu'à quatre fois plus rapidement. Finalement, les ensembles admissible et de solutions sont plus petits parce qu'ils sont isomorphes à une partie seulement des ensembles admissible et de solutions du problème en nombres réels, ce qui accroît la possibilité d'avoir une solution unique du problème.
Type de document :
Rapport
[Research Report] INRIA Paris; LAAS. 2017, pp.46
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01497173
Contributeur : Jean Charles Gilbert <>
Soumis le : mardi 28 mars 2017 - 13:35:52
Dernière modification le : vendredi 26 octobre 2018 - 10:42:01
Document(s) archivé(s) le : jeudi 29 juin 2017 - 16:24:18

Fichier

gilbert-josz-2017-03-28.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

  • HAL Id : hal-01497173, version 1

Citation

Jean Charles Gilbert, Cédric Josz. Plea for a semidefinite optimization solver in complex numbers – The full report. [Research Report] INRIA Paris; LAAS. 2017, pp.46. 〈hal-01497173〉

Partager

Métriques

Consultations de la notice

390

Téléchargements de fichiers

183