Target following algorithms for semidefinite programming

Chek Beng Chua (cbchuamath.uwaterloo.ca)

Abstract: We present a target-following framework for semidefinite programming, which generalizes the target-following framework for linear programming. We use this framework to build weighted path-following interior-point algorithms of three distinct flavors: short-step, predictor-corrector, and large-update. These algorithms have worse-case iteration bounds that parallel their counterparts in linear programming. We further consider the problem of finding analytic centers given a pair of primal-dual strictly feasible solutions. An algorithm that moves towards the analytic center prior to reducing the duality gap has a better iteration bound than the weighted path-following algorithms. In the case of linear programming, this bound is also an improvement over existing similar algorithms.

Keywords: Semidefinite programming; Weighted analytic centers; Weighted central path; Target-following algorithm; Weighted path-following algorithm; Target space; Cholesky search directions; Efficient centering; Local Lipschitz constant of Cholesky factorization.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Research Report CORR 2006-10, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, May 2006.

Download: [PDF]

Entry Submitted: 05/14/2006
Entry Accepted: 05/14/2006
Entry Last Modified: 05/14/2006

Modify/Update this entry