An Interior-Point Method for Approximate Positive Semidefinite Completions |
| |
Authors: | Charles R Johnson Brenda Kroschel Henry Wolkowicz |
| |
Institution: | (1) Department of Mathematics, College of William & Mary, Williamsburg, Virginia, 23187-8795;(2) Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada |
| |
Abstract: | Given a nonnegative, symmetric matrix of weights, H, we study the problem of finding an Hermitian, positive semidefinite matrix which is closest to a given Hermitian matrix, A, with respect to the weighting H. This extends the notion of exact matrix completion problems in that, H
ij
=0 corresponds to the element A
ij
being unspecified (free), while H
ij
large in absolute value corresponds to the element A
ij
being approximately specified (fixed).We present optimality conditions, duality theory, and two primal-dual interior-point algorithms. Because of sparsity considerations, the dual-step-first algorithm is more efficient for a large number of free elements, while the primal-step-first algorithm is more efficient for a large number of fixed elements.Included are numerical tests that illustrate the efficiency and robustness of the algorithms |
| |
Keywords: | positive definite completions best nonnegative approximation semidefinite programming primal-dual interior-point methods complementarity problems |
本文献已被 SpringerLink 等数据库收录! |
|