Self-scaled barrier functions on symmetric cones and their classification

Raphael Hauser (rah48damtp.cam.ac.uk)
Osman Guler (gulermath.umbc.edu)

Abstract: Self-scaled barrier functions on self-scaled cones were introduced through a set of axioms in 1994 by Y.E. Nesterov and M.J. Todd as a tool for the construction of long-step interior point algorithms. This paper provides firm foundation for these objects by exhibiting their symmetry properties, their intimate ties with the symmetry groups of their domains of definition, and subsequently their decomposition into irreducible parts and algebraic classification theory. In a first part we recall the characterisation of the family of self-scaled cones as the set of symmetric cones and develop a primal-dual symmetric viewpoint on self-scaled barriers, results that were first discovered by the second author. We then show in a short, simple proof that any pointed, convex cone decomposes into a direct sum of irreducible components in a unique way, a result which can also be of independent interest. We then show that any self-scaled barrier function decomposes in an essentially unique way into a direct sum of self-scaled barriers defined on the irreducible components of the underlying symmetric cone. Finally, we present a complete algebraic classification of self-scaled barrier functions using the correspondence between symmetric cones and Euclidean Jordan algebras.

Keywords: Self-scaled barrier functions, symmetric cones, decomposition of convex cones, Jordan algebras, universal barrier function, interior-point methods.

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

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

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

Download: [Compressed Postscript]

Entry Submitted: 03/28/2001
Entry Accepted: 03/28/2001
Entry Last Modified: 03/28/2001

Modify/Update this entry