Title

An Interior Point Method for Approximate Positive Semidefinite Completions

Department/School

Mathematics

Date

1-1-1998

Document Type

Article

Keywords

positive definite completions, best nonnegative approximation, semidefinite programming, primal-dual interior-point methods, complementarity problems

DOI

https://doi.org/10.1023/A:1018363021404

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, Hij = 0 corresponds to the element Aij being unspecified (free), while Hij large in absolute value corresponds to the element Aij 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.

Published in

Computational Optimization and Applications

Citation/Other Information

Johnson, C. R., Kroschel, B. K., & Wolkowicz, H. (1998). An Interior-Point Method for Approximate Positive Semidefinite Completions. Computational Optimization and Applications, 9(2), 175–190. https://doi.org/10.1023/A:1018363021404

Share

COinS