Minimizing condition number via convex programming

Zhaosong Lu, Ting Kei Pong

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)

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
Pages (from-to)1193-1211
Number of pages19
JournalSIAM Journal on Matrix Analysis and Applications
Volume32
Issue number4
DOIs
Publication statusPublished - 1 Dec 2011
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Analysis

Cite this