An algebraic perspective on homogeneous cone programming, and the primal-dual second-order cone approximations algorithm for symmetric cone programming.

摘要

This dissertation presents new results for two classes of convex optimization problems—homogeneous cone programming and symmetric cone programming.; We explore the T-algebraic structure of homogeneous cones. Using T-algebras, a class of non-associative algebras discovered by Vinberg in the early 1960's, we show that every homogeneous cone is linearly isomorphic to a “slice” of a positive definite cone. We further derive a family of logarithmically homogenous self-concordant barriers for each homogeneous cone, and provide an alternative proof that the universal barriers of homogeneous cones are logarithmically homogeneous self-concordant barriers.; We present the new concept of second-order cone approximations for convex conic programming. Given any open convex cone K, a logarithmically homogeneous self-concordant barrier for K and any positive real number r 1, we associate, with each direction x ∈ K, a second-order cone Kˆ _r(x) containing K. We show that K is the interior of the intersection of the second-order cones Kˆ_r(x), as x ranges over all directions in K. Using these second-order cones as approximations to positive definite cones, we develop a new polynomial-time primal-dual interior-point algorithm for semi-definite programming. This algorithm is further extended to symmetric cone programming via the relation between symmetric cones and Euclidean Jordan algebras.