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.
Entry Submitted: 05/14/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|