An algebraic perspective on homogeneous cone programming, and the primal-dual second-order cone approximations algorithm for symmetric cone programming | Posted on:2004-01-29 | Degree:Ph.D | Type:Dissertation | University:Cornell University | Candidate:Chua, Chek Beng | Full Text:PDF | GTID:1460390011962322 | Subject:Operations Research | Abstract/Summary: | | 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. | Keywords/Search Tags: | Cone, Algorithm, Approximations | | Related items |
| |
|