Self-scaled barriers for irreducible symmetric cones

Raphael Hauser (rah48damtp.cam.ac.uk)
Yongdo Lim (ylimknu.ac.kr)

Abstract: Self-scaled barrier functions are fundamental objects in the theory of interior-point methods for linear optimization over symmetric cones, of which linear and semidefinite programming are special cases. We are classifying all self-scaled barriers over irreducible symmetric cones and show that these functions are merely homothetic transformations of the universal barrier function. Together with a decomposition theorem for self-scaled barriers this concludes the algebraic classification theory of these functions. After introducing the reader to the concepts relevant to the problem and tracing the history of the subject, we start by deriving our result from first principles in the important special case of semidefinite programming. We then generalise these arguments to irreducible symmetric cones by invoking results from the theory of Euclidean Jordan algebras.

Keywords: Semidefinite programming, self-scaled barrier functions, interior-point methods, symmetric cones, Euclidean Jordan algebras.

Category 1: Linear, Cone and Semidefinite Programming (Other )

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

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Numerical Analysis Report DAMTP 2001/NA04, Department of Applied Mathematics and Theoretical Physics, Silver Street, Cambridge, England CB3 9EW. April 2001.

Download: [Compressed Postscript]

Entry Submitted: 04/10/2001
Entry Accepted: 04/10/2001
Entry Last Modified: 04/10/2001

Modify/Update this entry