  


Target following algorithms for semidefinite programming
Chek Beng Chua (cbchuamath.uwaterloo.ca) Abstract: We present a targetfollowing framework for semidefinite programming, which generalizes the targetfollowing framework for linear programming. We use this framework to build weighted pathfollowing interiorpoint algorithms of three distinct flavors: shortstep, predictorcorrector, and largeupdate. These algorithms have worsecase iteration bounds that parallel their counterparts in linear programming. We further consider the problem of finding analytic centers given a pair of primaldual 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 pathfollowing 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; Targetfollowing algorithm; Weighted pathfollowing algorithm; Target space; Cholesky search directions; Efficient centering; Local Lipschitz constant of Cholesky factorization. Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Research Report CORR 200610, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, May 2006. Download: [PDF] Entry Submitted: 05/14/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  