HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074800
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:27:06 PM
Last modification on : Thursday, February 3, 2022 - 11:17:23 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:24:48 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

76

Files downloads

50