 NSFPAR ID:
 10326038
 Date Published:
 Journal Name:
 INFORMS Journal on Computing
 Volume:
 34
 Issue:
 1
 ISSN:
 10919856
 Page Range / eLocation ID:
 11 to 19
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract In recent work, we provide computational arguments for expanding the class of proper cones recognized by conic optimization solvers, to permit simpler, smaller, more natural conic formulations. We define an exotic cone as a proper cone for which we can implement a small set of tractable (i.e. fast, numerically stable, analytic) oracles for a logarithmically homogeneous selfconcordant barrier for the cone or for its dual cone. Our extensible, opensource conic interior point solver, Hypatia, allows modeling and solving any conic problem over a Cartesian product of exotic cones. In this paper, we introduce Hypatia’s interior point algorithm, which generalizes that of Skajaa and Ye (Math. Program. 150(2):391–422, 2015) by handling exotic cones without tractable primal oracles. To improve iteration count and solve time in practice, we propose four enhancements to the interior point stepping procedure of Skajaa and Ye: (1) loosening the central path proximity conditions, (2) adjusting the directions using a third order directional derivative barrier oracle, (3) performing a backtracking search on a curve, and (4) combining the prediction and centering directions. We implement 23 useful exotic cones in Hypatia. We summarize the complexity of computing oracles for these cones and show that our new third order oracle is not a bottleneck. From 37 applied examples, we generate a diverse benchmark set of 379 problems. Our computational testing shows that each stepping enhancement improves Hypatia’s iteration count and solve time. Altogether, the enhancements reduce the geometric means of iteration count and solve time by over 80% and 70% respectively.more » « less

Many convex optimization problems can be represented through conic extended formulations (EFs) using only the small number of standard cones recognized by advanced conic solvers such as MOSEK 9. However, EFs are often significantly larger and more complex than equivalent conic natural formulations (NFs) represented using the much broader class of exotic cones. We define an exotic cone as a proper cone for which we can implement easily computable logarithmically homogeneous selfconcordant barrier oracles for either the cone or its dual cone. Our goal is to establish whether a generic conic interior point solver supporting NFs can outperform an advanced conic solver specialized for EFs across a variety of applied problems. We introduce Hypatia, a highly configurable opensource conic primaldual interior point solver written in Julia and accessible through JuMP. Hypatia has a generic interface for exotic cones, some of which we define here. For seven applied problems, we introduce NFs using these cones and construct EFs that are necessarily larger and more complex. Our computational experiments demonstrate the advantages, especially in terms of solve time and memory usage, of solving the NFs with Hypatia compared with solving the EFs with either Hypatia or MOSEK 9.more » « less

Spectral functions on Euclidean Jordan algebras arise frequently in convex optimization models. Despite the success of primaldual conic interior point solvers, there has been little work on enabling direct support for spectral cones, that is, proper nonsymmetric cones defined from epigraphs and perspectives of spectral functions. We propose simple logarithmically homogeneous barriers for spectral cones and we derive efficient, numerically stable procedures for evaluating barrier oracles such as inverse Hessian operators. For two useful classes of spectral cones—the rootdeterminant cones and the matrix monotone derivative cones—we show that the barriers are selfconcordant, with nearly optimal parameters. We implement these cones and oracles in our opensource solver Hypatia, and we write simple, natural formulations for four applied problems. Our computational benchmarks demonstrate that Hypatia often solves the natural formulations more efficiently than advanced solvers such as MOSEK 9 solve equivalent extended formulations written using only the cones these solvers support. Funding: This work was supported by Office of Naval Research [Grant N000141812079] and the National Science Foundation [Grant OAC1835443].more » « less

Abstract We present a generalization of the notion of neighborliness to nonpolyhedral convex cones. Although a definition of neighborliness is available in the nonpolyhedral case in the literature, it is fairly restrictive as it requires all the lowdimensional faces to be polyhedral. Our approach is more flexible and includes, for example, the cone of positivesemidefinite matrices as a special case (this cone is not neighborly in general). We term our generalization Terracini convexity due to its conceptual similarity with the conclusion of Terracini’s lemma from algebraic geometry. Polyhedral cones are Terracini convex if and only if they are neighborly. More broadly, we derive many families of nonpolyhedral Terracini convex cones based on neighborly cones, linear images of cones of positivesemidefinite matrices, and derivative relaxations of Terracini convex hyperbolicity cones. As a demonstration of the utility of our framework in the nonpolyhedral case, we give a characterization based on Terracini convexity of the tightness of semidefinite relaxations for certain inverse problems.

Newly, there has been significant research interest in the exact solution of the AC optimal power flow (ACOPF) problem. A semideflnite relaxation solves many OPF problems globally. However, the real problem exists in which the semidefinite relaxation fails to yield the global solution. The appropriation of relaxation for ACOPF depends on the success or unfulflllment of the SDP relaxation. This paper demonstrates a quadratic ACOPF problem with a single negative eigenvalue in objective function subject to linear and conic constraints. The proposed solution method for ACOPF model covers the classical AC economic dispatch problem that is known to be NPhard. In this paper, by combining successive linear conic optimization (SLCO), convex relaxation and line search technique, we present a global algorithm for ACOPF which can locate a globally optimal solution to the underlying ACOPF within given tolerance of global optimum solution via solving linear conic optimization problems. The proposed algorithm is examined on modified IEEE 6bus test system. The promising numerical results are described.more » « less