Minimizing condition number via convex programming

Zhaosong Lu, Ting Kei Pong

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

In this paper we consider minimizing the spec tral condition number of a positive semidefinite matrix over a nonempty closed convex set Ω. We show that it can be solved as a convex programming problem, and moreover, the optimal value of the latter problem is achievable. As a consequence, when Ω is positive semidefinite representable, it can be cast into a semidefinite programming problem. We then propose a first-order method to solve the convex programming problem. The computational results show that our method is usually faster than the standard interior point solver SeDuMi [J. F. Sturm, Optim. Methods Softw., 11/12 (1999), pp. 625-653] while producing a comparable solution. We also study a closely related problem, that is, finding an optimal preconditioner for a positive definite matrix. This problem is not convex in general. We propose a convex relaxation for finding positive definite preconditioners. This relaxation turns out to be exact when finding optimal diagonal preconditioners.

Original languageEnglish (US)
Pages (from-to)1193-1211
Number of pages19
JournalSIAM Journal on Matrix Analysis and Applications
Volume32
Issue number4
DOIs
StatePublished - Dec 1 2011
Externally publishedYes

Keywords

  • Condition number
  • Convex programming
  • Diagonal preconditioner
  • Semidefinite programming

Fingerprint Dive into the research topics of 'Minimizing condition number via convex programming'. Together they form a unique fingerprint.

Cite this