Target following algorithms for semidefinite programming

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.


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



View Target following algorithms for semidefinite programming