An inexact primal-dual path following algorithm for convex quadratic SDP

• 成果类型: Article; Proceedings Paper
• 署名作者: Toh, Kim-Chuan
• 署名单位: National University of Singapore; Massachusetts Institute of Technology (MIT); Nanyang Technological University; Singapore-MIT Alliance for Research & Technology Centre (SMART)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0088-y
• 发表日期: 2008
• 页码: 221-254
• 关键词: interior-point methods; semidefinite; COMPLEMENTARITY; preconditioner; CONVERGENCE; matrix

摘要

We propose primal - dual path- following Mehrotra- type predictor corrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: min(X){1/2X center dot Q(X) + C center dot X : A( X) = b, X >= 0}, where Q is a self- adjoint positive semidefinite linear operator on S (n), b is an element of R-m, and A is a linear map from S n to Rm. At each interior- point iteration, the search direction is computed from a dense symmetric indefinite linear system ( called the augmented equation) of dimension m+ n( n+ 1)/ 2. Such linear systems are typically very large and can only be solved by iterative methods. We propose three classes of preconditioners for the augmented equation, and show that the corresponding preconditioned matrices have favorable asymptotic eigenvalue distributions for fast convergence under suitable nondegeneracy assumptions. Numerical experiments on a variety of QSDPs with n up to 1600 are performed and the computational results show that our methods are efficient and robust.