Please use this identifier to cite or link to this item:
Title: Inexact Interior-Point Methods for Large Scale Linear and Convex Quadratic Semidefinite Programming
Authors: LI LU
Keywords: Convex Optimization, Semidefinite Programming, Interior-Point Method, Inexact Search Direction, Covariance Selection
Issue Date: 27-Apr-2010
Citation: LI LU (2010-04-27). Inexact Interior-Point Methods for Large Scale Linear and Convex Quadratic Semidefinite Programming. ScholarBank@NUS Repository.
Abstract: Interior-point methods have been intensively studied during the last few decades. In theory, interior-point methods can solve a wide range of convex programming problems to high accuracy in polynomial time. In practice, the difficulty faced by interior-point methods is to compute the search direction from a linear system in each iteration. Classical interior-point methods use a direct solver such as Cholesky factorization to store and solve the linear system. Thus only small to medium scale problems are solvable due to limited computer memory and processing speed. A well-known alternative approach is the inexact interior-point method. As the name suggests, this method applies iterative solvers to the linear system to avoid storing and manipulating the large coefficient matrix explicitly. Its consequence is that the search direction in each iteration becomes inexact because the linear system is only solved approximately. To ensure that the inexact search directions do not jeopardize the polynomial convergence of the interior-point algorithm, the effect of the inexactness needs to be carefully reviewed and controlled. In this thesis, we developed an inexact primal-dual path-following interior-point method for convex quadratic symmetric cone programming problems and an inexact dual-scaling interior-point method for linear symmetric cone programming problems. Admissible conditions on the inexactness are thoroughly discussed and polynomial convergence is established. The motivation for studying inexact interior-point methods is to obtain high performance in numerical experiments. However, a naive implementation of the iterative solvers may not lead to better performance. The real bottleneck of inexact interior-point methods is to construct efficient preconditioners for the iterative solvers since the linear system in each iteration is generally ill-conditioned. The construction of preconditioners is heavily dependent on the particular structure of each problem class. As an example, we proposed a customized inexact primal-dual interior-point algorithm with specialized preconditioners for solving log-determinant semidefinite programming problems with L1-regularization. Extensive numerical experiments on covariance selection problems demonstrate that our customized inexact interior-point methods are efficient and robust in solving covariance selection problems, outperforming many existing algorithms.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
LiLu.pdf951.76 kBAdobe PDF



Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.