A NEW BARRIER FOR A CLASS OF SEMIDEFINITE PROBLEMS

Erik Papa Quiroz (erikcos.ufrj.br)
Paulo Roberto Oliveira (poliveircos.ufrj.br)

Abstract: We introduce a new barrier function to solve a class of Semidefinite Optimization Problems (SOP) with bounded variables. That class is motivated by some (SOP) as the minimization of the sum of the first few eigenvalues of symmetric matrices and graph partitioning problems. We study the primal-dual central path defined by the new barrier and we show that this path is analytic, bounded and that all cluster points are optimal solutions of the primal-dual pair of problems. Then, using some ideas from semi-analytic geometry we prove its full convergence. Finally, we introduce a new proximal point type Bregman algorithm for that class of problems and prove its convergence.

Keywords: interior point methods, barrier function, central path, semidefinite optimization

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

Citation: RAIRO-Operations Research,, 40, 3, 303-323, 2006

Download:

Entry Submitted: 04/08/2005
Entry Accepted: 04/08/2005
Entry Last Modified: 11/09/2006

Modify/Update this entry