首页>
外文学位
>An algebraic perspective on homogeneous cone programming, and the primal-dual second-order cone approximations algorithm for symmetric cone programming.
【24h】
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.
展开▼
机译:本文为两类凸优化问题提供了新的结果-均匀锥规划和对称锥规划。我们探索均质锥的 T italic>-代数结构。使用Vinberg在1960年代早期发现的一类非缔合代数 T italic>-代数,我们证明了每个同质锥与正定锥的“切片”呈线性同构。我们进一步推导了每个同质锥的对数齐次自协调势垒族,并提供了另一种证明,即同质锥的通用势垒是对数齐次自协调势垒。我们提出了凸锥二次规划的二阶锥逼近的新概念。给定任何开放的凸锥 K italic>, K italic>的对数齐次自洽壁垒和任何正实数 r italic> <1,我们将其与每个方向 x italic>∈ K italic>,二阶圆锥 Kˆ r sub> italic>( x italic> )包含 K italic>。我们证明 K italic>是二阶圆锥体 Kˆ r sub> italic>( x italic>)的交点的内部,因为 x italic>的范围在 K italic>的所有方向上。使用这些二阶锥作为正定锥的近似,我们为半定规划开发了一种新的多项式时间原始对偶内点算法。通过对称锥和欧几里得约旦代数之间的关系,该算法进一步扩展到对称锥编程。
展开▼