Juan Pablo Vielma
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
Performance enhancements for a generic conic interior point algorithm
Chris Coey
Lea Kapelevich
Mathematical Programming Computation, vol. 15 (2023), pp. 53-101
Preview 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.
View details
Preview abstract
Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear representable (MILP-R) sets. First, we provide an example of an MICP-R set which is the countably infinite union of convex sets with countably infinitely many different recession cones. This is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that share the same recession cone. Second, we provide an example of an MICP-R set which is the countably infinite union of polytopes all of which have different shapes (no pair is combinatorially equivalent, which implies they are not affine transformations of each other). Again, this is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that are all translations of a finite subset of themselves.
View details
Preview abstract
In polynomial optimization problems, nonnegativity constraints are typically 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 2019, using the sum of squares cone directly in a nonsymmetric interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and l1-norm cones) can also be modeled through structured sum of squares programs. We take a different approach and propose using more specialized polynomial cones instead. This can result in lower dimensional formulations, more efficient oracles for interior point methods, or self-concordant barriers with lower parameters. In most cases, these algorithmic advantages also translate to faster solving times in practice.
View details
Preview abstract
Spectral functions on Euclidean Jordan algebras arise frequently in convex models. Despite the success of primal-dual conic interior point solvers, there has been little work on enabling direct support for spectral cones, i.e. 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 root-determinant cones and the matrix monotone derivative cones - we show that the barriers are self-concordant, with nearly optimal parameters. We implement these cones and oracles in our open source 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.
View details
Solving natural conic formulations with Hypatia.jl
Chris Coey
Lea Kapelevich
INFORMS Journal on Computing, vol. 34 (2022), pp. 2686-2699
Preview abstract
Many convex optimization problems can be represented through conic extended formulations with auxiliary variables and constraints using only the small number of standard cones recognized by advanced conic solvers such as MOSEK 9. Such extended formulations are often significantly larger and more complex than equivalent conic natural formulations, which can use a much broader class of exotic cones. We define an exotic cone as a proper cone for which we can implement tractable logarithmically homogeneous self-concordant barrier oracles for either the cone or its dual cone. In this paper we introduce Hypatia, a highly-configurable open-source conic primal-dual interior point solver with a generic interface for exotic cones. Hypatia is written in Julia and accessible through JuMP, and currently implements around two dozen useful predefined cones (some with multiple variants). We define some of Hypatia's exotic cones, and for conic constraints over these cones, we analyze techniques for constructing equivalent representations using the standard cones. For optimization problems from a variety of applications, we introduce natural formulations using these exotic cones, and we show that the natural formulations are simpler and lower-dimensional than the equivalent extended formulations. Our computational experiments demonstrate the potential advantages, especially in terms of solve time and memory usage, of solving the natural formulations with Hypatia compared to solving the extended formulations with either Hypatia or MOSEK 9.
View details
Computing conjugate barrier information for nonsymmetric cones
Erling D. Andersen
Lea Kapelevich
Journal of Optimization Theory and Applications (2022)
Preview abstract
The recent interior point algorithm by Dahl and Andersen [10] for nonsymmetric cones as well as earlier works [16,19] require derivative information from the conjugate of the barrier function of the cones in the problem. Besides a few special cases, there is no indication of when this information is efficient to evaluate. We show how to compute the gradient of the conjugate barrier function for seven useful nonsymmetric cones. In some cases this is helpful for deriving closed-form expressions for the inverse Hessian operator for the primal barrier.
View details
Mixed-integer convex representability
Miles Lubin
Ilias Zadik
Mathematics of Operations Research, vol. 47 (2021), pp. 720-749
Preview abstract
Motivated by recent advances in solution methods for mixed-integer convex optimization (MICP), we study the fundamental and open question of which sets can be represented exactly as feasible regions of MICP problems. We establish several results in this direction, including the first complete characterization for the mixed-binary case and a simple necessary condition for the general case. We use the latter to derive the first non-representability results for various non-convex sets such as the set of rank-1 matrices and the set of prime numbers. Finally, in correspondence with the seminal work on mixed-integer linear representability by Jeroslow and Lowe, we study the representability question under rationality assumptions. Under these rationality assumptions, we establish that representable sets obey strong regularity properties such as periodicity, and we provide a complete characterization of representable subsets of the natural numbers and of representable compact sets. Interestingly, in the case of subsets of natural numbers, our results provide a clear separation between the mathematical modeling power of mixed-integer linear and mixed-integer convex optimization. In the case of compact sets, our results imply that using unbounded integer variables is necessary only for modeling unbounded sets.
View details
The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
Joey Huchette
Krunal K Patel
Will Ma
Advances in Neural Information Processing Systems (2020), pp. 21675-21686
Preview abstract
We improve the effectiveness of propagation- and linear-optimization-based neural network verification algorithms with a new tightened convex relaxation for ReLU neurons. Unlike previous single-neuron relaxations which focus only on the univariate input space of the ReLU, our method considers the multivariate input space of the affine pre-activation function preceding the ReLU. Using results from submodularity and convex geometry, we derive an explicit description of the tightest possible convex relaxation when this multivariate input is over a box domain. We show that our convex relaxation is significantly stronger than the commonly used univariate-input relaxation which has been proposed as a natural convex relaxation barrier for verification. While our description of the relaxation may require an exponential number of inequalities, we show that they can be separated in linear time and hence can be efficiently incorporated into optimization algorithms on an as-needed basis. Based on this novel relaxation, we design two polynomial-time algorithms for neural network verification: a linear-programming-based algorithm that leverages the full power of our relaxation, and a fast propagation algorithm that generalizes existing approaches. In both cases, we show that for a modest increase in computational effort, our strengthened relaxation enables us to verify a significantly larger number of instances compared to similar algorithms.
View details
Strong mixed-integer programming formulations for trained neural networks
Will Ma
Mathematical Programming, vol. 183 (2020), pp. 3-39
Preview abstract
We present strong mixed-integer programming (MIP) formulations for high-dimensional piecewise linear functions that correspond to trained neural networks. These formulations can be used for a number of important tasks, such as verifying that an image classification network is robust to adversarial inputs, or solving decision problems where the objective function is a machine learning model. We present a generic framework, which may be of independent interest, that provides a way to construct sharp or ideal formulations for the maximum of d affine functions over arbitrary polyhedral input domains. We apply this result to derive MIP formulations for a number of the most popular nonlinear operations (e.g. ReLU and max pooling) that are strictly stronger than other approaches from the literature. We corroborate this computationally, showing that our formulations are able to offer substantial improvements in solve time on verification tasks for image classification networks.
View details
Preview abstract
We give an explicit geometric way to build ideal mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of the normal directions of all hyperplanes spanned (in a r-dimensional linear space) by a set of directions determined by the extreme points shared among the alternatives. The resulting MIP formulation is ideal, and has exactly r integer variables and 2 x (# of spanning hyperplanes) general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and the annulus constraint arising in robotics and power systems problems.
View details
Strong mixed-integer programming formulations for trained neural networks
Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings, Springer, pp. 27-42
Preview abstract
We present an ideal mixed-integer programming (MIP) formulation for a rectified linear unit (ReLU) appearing in a trained neural network. Our formulation requires a single binary variable and no additional continuous variables beyond the input and output variables of the ReLU. We contrast it with an ideal “extended” formulation with a linear number of additional continuous variables, derived through standard techniques. An apparent drawback of our formulation is that it requires an exponential number of inequality constraints, but we provide a routine to separate the inequalities in linear time. We also prove that these exponentially-many constraints are facet-defining under mild conditions. Finally, we study network verification problems and observe that dynamically separating from the exponential inequalities (1) is much more computationally efficient and scalable than the extended formulation, (2) decreases the solve time of a state-of-the-art MIP solver by a factor of 7 on smaller instances, and (3) nearly matches the dual bounds of a state-of-the-art MIP solver on harder instances, after just a few rounds of separation and in orders of magnitude less time.
View details
No Results Found
