Plea for a semidefinite optimization solver in complex numbers - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2017

Plea for a semidefinite optimization solver in complex numbers

Plaidoyer pour un solveur d'optimisation semi-définie positive en nombres complexes

Résumé

Numerical optimization in complex numbers has drawn much less attention than in real numbers. A widespread opinion is that, since a complex number is a pair of real numbers, the best strategy to solve a complex optimization problem is to transform it into real numbers and to solve the latter by a real number solver. This paper defends another point of view and presents four arguments to convince the reader that skipping the transformation phase and using a complex number algorithm, if any, can sometimes have significant benefits. This is demonstrated for the particular case of a semidefinite optimization problem solved by a feasible corrector-predictor primal-dual interior-point method. In that case, the complex number formulation has the advantage (i) of having a smaller memory storage, (ii) of having a faster iteration, (iii) of requiring less iterations, and (iv) of having "smaller" feasible and solution sets. The computing time saving is rooted in the fact that some operations (like the matrix-matrix product) are much faster for complex operands than for their double size real counterparts, so that the conclusions of this paper could be valid for other problems in which these operations count a great deal in the computing time. The iteration number saving has its origin in the smaller (though complex) dimension of the problem in complex numbers. Numerical experiments show that all together these properties result in a code that can run up to four times faster. Finally, the feasible and solution sets are smaller since they are isometric to only a part of the feasible and solution sets of the problem in real numbers, which increases the chance of having a unique solution to the problem.
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.
Fichier principal
Vignette du fichier
p-2017-03-28.pdf (510.27 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01422932 , version 1 (27-12-2016)
hal-01422932 , version 2 (28-03-2017)

Licence

Paternité - Pas d'utilisation commerciale - Pas de modification

Identifiants

  • HAL Id : hal-01422932 , version 2

Citer

Jean Charles Gilbert, Cédric Josz. Plea for a semidefinite optimization solver in complex numbers. [Research Report] Inria Paris. 2017, pp.35. ⟨hal-01422932v2⟩
574 Consultations
1579 Téléchargements

Partager

Gmail Facebook X LinkedIn More