  


An inexact primaldual path following algorithm for convex quadratic SDP
KimChuan Toh (mattohkcnus.edu.sg) Abstract: We propose primaldual pathfollowing Mehrotratype predictorcorrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: $\min_{X} \{ \frac{1}{2} X\bullet {\cal Q}(X) + C\bullet X : {\cal A} (X) = b, X\succeq 0\}$, where ${\cal Q}$ is a selfadjoint positive semidefinite linear operator on ${\cal S}^n$, $b\in R^m$, and ${\cal A}$ is a linear map from ${\cal S}^n$ to $R^m$. At each interiorpoint iteration, the search direction is computed from a dense symmetric indefinite linear system (called the augmented equation) with dimension $m + n(n+1)/2$. Such linear systems are very large when $n$ is larger than a few hundreds 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. We are able to solve the augmented equation efficiently via the preconditioned symmetric quasiminimal residual iterative method with the preconditioners constructed. Numerical experiments on a variety of QSDPs with matrices of dimensions up to $1600$ are performed and the computational results show that our methods are efficient and robust. Keywords: semidefinite programming, semidefinite least squares, pathfollowing methods, iterative solvers, preconditioners Category 1: Linear, Cone and Semidefinite Programming Citation: Technical Report, Department of Mathematics, National University of Singapore, May 2006. Download: [PDF] Entry Submitted: 05/24/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  