Performance enhancements for a generic conic interior point algorithm
From MaRDI portal
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 self-concordant barrier for the cone or for its dual cone. Our extensible, open source conic interior point solver, Hypatia, allows modeling and solving any conic optimization problem over a Cartesian product of exotic cones. In this paper, we introduce Hypatia's interior point algorithm. Our algorithm is based on that of Skajaa and Ye [2015], which we generalize by handling exotic cones without tractable primal oracles. With the goal of improving iteration count and solve time in practice, we propose a sequence of four enhancements to the interior point stepping procedure of Skajaa and Ye [2015]: (1) loosening the central path proximity condition, (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, showing that our new third order oracle is not a bottleneck, and we derive efficient and numerically stable oracle implementations for several cones. We generate a diverse benchmark set of 379 conic problems from 37 different applied examples. Our computational testing shows that each stepping enhancement improves Hypatia's iteration count and solve time. Altogether, the enhancements reduce the shifted geometric means of iteration count and solve time by over 80% and 70% respectively.
Recommendations
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization
- A Geodesic Interior-Point Method for Linear Optimization over Symmetric Cones
- Towards non-symmetric conic optimization
- A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations
Cites work
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A Computational Framework for Multivariate Convex Regression and Its Variants
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- A mathematical view of interior-point methods in convex optimization
- A note on performance profiles for benchmarking software
- A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization
- A simplified homogeneous and self-dual linear programming algorithm and its implementation
- Alfonso: Matlab Package for Nonsymmetric Conic Optimization
- Barrier Functions in Interior Point Methods
- Benchmarking optimization software with performance profiles.
- CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization
- CSDP, A C library for semidefinite programming
- Characterization of the barrier parameter of homogeneous convex cones
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Controller design and value function approximation for nonlinear dynamical systems
- Convex Computation of the Region of Attraction of Polynomial Control Systems
- Decomposition methods for sparse matrix nearness problems
- Disciplined geometric programming
- Efficient optimization of the quantum relative entropy
- Geometry of homogeneous convex cones, duality mapping, and optimal self-concordant barriers
- Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
- Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
- JuMP: a modeling language for mathematical optimization
- Julia: a fresh approach to numerical computing
- Lectures on convex optimization
- Linear Matrix Inequalities in System and Control Theory
- Logarithmic barriers for sparse matrix cones
- On implementing a primal-dual interior-point method for conic quadratic optimization
- On self-concordant barriers for generalized power cones
- On the Implementation of a Primal-Dual Interior Point Method
- Primal-Dual Interior-Point Methods for Self-Scaled Cones
- Primal-dual interior-point methods for domain-driven formulations
- Relative entropy optimization and its applications
- Relative entropy relaxations for signomial optimization
- Self-Scaled Barriers and Interior-Point Methods for Convex Programming
- Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
- Semidefinite approximations of the matrix logarithm
- Signomial and polynomial optimization via relative entropy and partial dualization
- Solving Natural Conic Formulations with Hypatia.jl
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Stability and robustness analysis of nonlinear systems via contraction metrics and SOS programming
- Sum of squares generalizations for conic sets
- Sum-of-squares optimization without semidefinite programming
- Towards non-symmetric conic optimization
Cited in
(4)- Tight error bounds for log-determinant cones without constraint qualifications
- An efficient implementation of interior-point methods for a class of nonsymmetric cones
- Optimal Self-Concordant Barriers for Quantum Relative Entropies
- Interior-point algorithms with full Newton steps for nonsymmetric convex conic optimization
This page was built for publication: Performance enhancements for a generic conic interior point algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102857)
