An official website of the United States government
The multilinear polytope of a hypergraph is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of the multilinear polytope, referred to as the running intersection relaxation, and identify conditions under which this relaxation is tight. Namely, we show that for kite-free beta-acyclic hypergraphs, a class that lies between gamma-acyclic and beta-acyclic hypergraphs, the running intersection relaxation coincides with the multilinear polytope and it admits a polynomial size extended formulation.
more »
« less
On the impact of running intersection inequalities for globally solving polynomial optimization problems
We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary points z satisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance of BARON and lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set.
more »
« less
- Award ID(s):
- 1634768
- PAR ID:
- 10128200
- Date Published:
- Journal Name:
- Mathematical Programming Computation
- ISSN:
- 1867-2949
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvátal rank. We determine the Chvátal rank of all known cutting planes and show that almost all of them have Chvátal rank 1. We observe that these inequalities have an associated hypergraph that is β-acyclic. Our second goal is to derive deeper cutting planes; to do so, we consider hypergraphs that admit β-cycles. We introduce a novel class of valid inequalities arising from odd β-cycles, that generally have Chvátal rank 2. These inequalities allow us to obtain the first characterization of the multilinear polytope for hypergraphs that contain β-cycles. Namely, we show that the multilinear polytope for cycle hypergraphs is given by the standard linearization inequalities, flower inequalities, and odd β-cycle inequalities. We also prove that odd β-cycle inequalities can be separated in linear time when the hypergraph is a cycle hypergraph. This shows that instances represented by cycle hypergraphs can be solved in polynomial time. Last, to test the strength of odd β-cycle inequalities, we perform numerical experiments that imply that they close a significant percentage of the integrality gap.more » « less
-
We study the structure of the set of all possible affine hyperplane sections of a convex polytope. We present two different cell decompositions of this set, induced by hyperplane arrangements. Using our decomposition, we bound the number of possible combinatorial types of sections and craft algorithms that compute optimal sections of the polytope according to various combinatorial and metric criteria, including sections that maximize the number of -dimensional faces, maximize the volume, and maximize the integral of a polynomial. Our optimization algorithms run in polynomial time in fixed dimension, but the same problems show computational complexity hardness otherwise. Our tools can be extended to intersection with halfspaces and projections onto hyperplanes. Finally, we present several experiments illustrating our theorems and algorithms on famous polytopes.more » « less
-
We study the problem of finding the Löwner–John ellipsoid (i.e., an ellipsoid with minimum volume that contains a given convex set). We reformulate the problem as a generalized copositive program and use that reformulation to derive tractable semidefinite programming approximations for instances where the set is defined by affine and quadratic inequalities. We prove that, when the underlying set is a polytope, our method never provides an ellipsoid of higher volume than the one obtained by scaling the maximum volume-inscribed ellipsoid. We empirically demonstrate that our proposed method generates high-quality solutions and can be solved much faster than solving the problem to optimality. Furthermore, we outperform the existing approximation schemes in terms of solution time and quality. We present applications of our method to obtain piecewise linear decision rule approximations for dynamic distributionally robust problems with random recourse and to generate ellipsoidal approximations for the set of reachable states in a linear dynamical system when the set of allowed controls is a polytope.more » « less
-
Deep neural networks (DNNs) are becoming increasingly important components of software, and are considered the state-of-the-art solution for a number of problems, such as image recognition. However, DNNs are far from infallible, and incorrect behavior of DNNs can have disastrous real-world consequences. This paper addresses the problem of architecture-preserving V-polytope provable repair of DNNs. A V-polytope defines a convex bounded polytope using its vertex representation. V-polytope provable repair guarantees that the repaired DNN satisfies the given specification on the infinite set of points in the given V-polytope. An architecture-preserving repair only modifies the parameters of the DNN, without modifying its architecture. The repair has the flexibility to modify multiple layers of the DNN, and runs in polynomial time. It supports DNNs with activation functions that have some linear pieces, as well as fully-connected, convolutional, pooling and residual layers. To the best our knowledge, this is the first provable repair approach that has all of these features. We implement our approach in a tool called APRNN. Using MNIST, ImageNet, and ACAS Xu DNNs, we show that it has better efficiency, scalability, and generalization compared to PRDNN and REASSURE, prior provable repair methods that are not architecture preserving.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s12532-019-00169-z
