Acceleration of the path-following method for optimization over the cone of positive semidefinite matrices

Abstract : The paper is devoted to acceleration of the path-following interior point polynomial time method for optimization over the cone of positive semidefinite matrices, with applications to quadratically constrained problems and extensions onto the general self-concordant case. In particular, we demonstrate that in a problem involving m of general type m x m linear matrix inequalities with n 3 m scalar control variables the conjugate-gradient-based acceleration allows to reduce the arithmetic cost of an e-solution by a factor of order of max {n1/3 m-1/6, n1/5}, for the Karmarkar-type acceleration this factor is of order of min {n, m1/2}. The conjugate-gradient-based acceleration turns out to be efficient also in the case of several specific "structured" problems coming from applications in control and graph theory.
Type de document :
Rapport
[Research Report] RR-1873, INRIA. 1993
Liste complète des métadonnées

https://hal.inria.fr/inria-00074800
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:27:06
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:24:48

Fichiers

Identifiants

  • HAL Id : inria-00074800, version 1

Collections

Citation

Yurii E. Nesterov, Arkadii S. Nemirovskii. Acceleration of the path-following method for optimization over the cone of positive semidefinite matrices. [Research Report] RR-1873, INRIA. 1993. 〈inria-00074800〉

Partager

Métriques

Consultations de la notice

134

Téléchargements de fichiers

75