Eigenvalue Multiplicity Estimate in Semidefinite Programming

M. K. H. Fan and Y. Gong
Additional contact information
M. K. H. Fan: School of Electrical and Computer Engineering, Georgia Institute of Technology
Y. Gong: School of Electrical and Computer Engineering, Georgia Institute of Technology

Journal of Optimization Theory and Applications, 1997, vol. 94, issue 1, No 4, 55-72

Abstract: Abstract A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable, but convex. It covers several standard problems (such as linear and quadratic programming) and has many applications in engineering. Typically, the optimal eigenvalue multiplicity associated with a linear matrix inequality is larger than one. Algorithms based on prior knowledge of the optimal eigenvalue multiplicity for solving the underlying problem have been shown to be efficient. In this paper, we propose a scheme to estimate the optimal eigenvalue multiplicity from points close to the solution. With some mild assumptions, it is shown that there exists an open neighborhood around the minimizer so that our scheme applied to any point in the neighborhood will always give the correct optimal eigenvalue multiplicity. We then show how to incorporate this result into a generalization of an existing local method for solving the semidefinite programming problem. Finally, a numerical example is included to illustrate the results.

Keywords: Convex programming; semidefinite programming; linear matrix inequality; eigenvalue multiplicity estimate; quadratic rate of convergence; Newton method (search for similar items in EconPapers)
Date: 1997
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1022603518289 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:94:y:1997:i:1:d:10.1023_a:1022603518289

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1022603518289

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().