Analyticity of weighted central path and error bound for semidefinite programming

Chek Beng Chua (cbchuamath.uwaterloo.ca)

Abstract: The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary solutions. Secondly, we consider a sequence of primal-dual solutions that lies within a prescribed neighborhood of the central path of a pair of primal-dual semidefinite programming problems, and converges to the respective optimal faces. Under the additional assumption of strict complementarity, we derive two necessary and sufficient conditions for the sequence of primal-dual solutions to converge linearly with their duality gaps.

Keywords: semidefinite programming, homogeneous cone programming, weighted analytic center, error bound

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

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

Citation: Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, CORR 2005-15

Download: [PDF]

Entry Submitted: 07/02/2005
Entry Accepted: 07/02/2005
Entry Last Modified: 03/23/2006

Modify/Update this entry