 Award ID(s):
 1835443
 NSFPAR ID:
 10387775
 Date Published:
 Journal Name:
 Mathematical Programming Computation
 ISSN:
 18672949
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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

We present alfonso, an opensource Matlab package for solving conic optimization problems over nonsymmetric convex cones. The implementation is based on the authors’ corrected analysis of a method of Skajaa and Ye. It enables optimization over any convex cone as long as a logarithmically homogeneous selfconcordant barrier is available for the cone or its dual. This includes many nonsymmetric cones, for example, hyperbolicity cones and their duals (such as sumofsquares cones), semidefinite and secondorder cone representable cones, power cones, and the exponential cone. Besides enabling the solution of problems that cannot be cast as optimization problems over a symmetric cone, algorithms for nonsymmetric conic optimization also offer performance advantages for problems whose symmetric cone programming representation requires a large number of auxiliary variables or has a special structure that can be exploited in the barrier computation. The worstcase iteration complexity of alfonso is the best known for nonsymmetric cone optimization: [Formula: see text] iterations to reach an εoptimal solution, where ν is the barrier parameter of the barrier function used in the optimization. Alfonso can be interfaced with a Matlab function (supplied by the user) that computes the Hessian of a barrier function for the cone. A simplified interface is also available to optimize over the direct product of cones for which a barrier function has already been built into the software. This interface can be easily extended to include new cones. Both interfaces are illustrated by solving linear programs. The oracle interface and the efficiency of alfonso are also demonstrated using an optimal design of experiments problem in which the tailored barrier computation greatly decreases the solution time compared with using stateoftheart, offtheshelf conic optimization software. Summary of Contribution: The paper describes an opensource Matlab package for optimization over nonsymmetric cones. A particularly important feature of this software is that, unlike other conic optimization software, it enables optimization over any convex cone as long as a suitable barrier function is available for the cone or its dual, not limiting the user to a small number of specific cones. Nonsymmetric cones for which such barriers are already known include, for example, hyperbolicity cones and their duals (such as sumofsquares cones), semidefinite and secondorder cone representable cones, power cones, and the exponential cone. Thus, the scope of this software is far larger than most current conic optimization software. This does not come at the price of efficiency, as the worstcase iteration complexity of our algorithm matches the iteration complexity of the most successful interiorpoint methods for symmetric cones. Besides enabling the solution of problems that cannot be cast as optimization problems over a symmetric cone, our software can also offer performance advantages for problems whose symmetric cone programming representation requires a large number of auxiliary variables or has a special structure that can be exploited in the barrier computation. This is also demonstrated in this paper via an example in which our code significantly outperforms Mosek 9 and SCS 2.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 Polynomial nonnegativity constraints can often be handled using the
sum of squares condition. This can be efficiently enforced using semidefinite programming formulations, or as more recently proposed by Papp and Yildiz (Papp D in SIAM J O 29: 822–851, 2019), using the sum of squares cone directly in an interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and norm cones) can also be modeled through structured sum of squares programs. We take a different approach and propose using more specialized cones instead. This can result in lower dimensional formulations, more efficient oracles for interior point methods, or selfconcordant barriers with smaller parameters.$$\ell _1$$ ${\ell}_{1}$ 
We present a GPU algorithm for deformable simulation. Our method offers good computational efficiency and penetrationfree guarantee at the same time, which are not common with existing techniques. The main idea is an algorithmic integration of projective dynamics (PD) and incremental potential contact (IPC). PD is a positionbased simulation framework, favored for its robust convergence and convenient implementation. We show that PD can be employed to handle the variational optimization with the interior point method e.g., IPC. While conceptually straightforward, this requires a dedicated rework over the collision resolution and the iteration modality to avoid incorrect collision projection with improved numerical convergence. IPC exploits a barrierbased formulation, which yields an infinitely large penalty when the constraint is on the verge of being violated. This mechanism guarantees intersectionfree trajectories of deformable bodies during the simulation, as long as they are apart at the rest configuration. On the downside, IPC brings a large amount of nonlinearity to the system, making PD slower to converge. To mitigate this issue, we propose a novel GPU algorithm named AJacobi for faster linear solve at the global step of PD. AJacobi is based on Jacobi iteration, but it better harvests the computation capacity on modern GPUs by lumping several Jacobi steps into a single iteration. In addition, we also redesign the CCD root finding procedure by using a new minimumgradient Newton algorithm. Those saved time budgets allow more iterations to accommodate stiff IPC barriers so that the result is both realistic and collisionfree. Putting together, our algorithm simulates complicated models of both solids and shells on the GPU at an interactive rate or even in real time.more » « less