Strong convex relaxations and mixed-integer programming formulations for trained neural networks
Authors:
- Ross AndersonRARoss Anderson
- Huchette ¨ ChristianHCHuchette ¨ Christian
- Tjandraatmadja ¨JuanT¨Tjandraatmadja ¨Juan
- Pablo VielmaPVPablo Vielma
- J P VielmaJVJ P Vielma
Preprint
Abstract
We present strong convex relaxations for high-dimensional piecewise linear functions that correspond to trained neural networks. These convex relaxations can be used for a number of important tasks, such as verifying that an image classification network is robust to adversarial inputs, or providing optimality guarantees for decision problems with machine learning models embedded inside (i.e. the `predict, then optimize' paradigm). Our convex relaxations arise from mixed-integer programming (MIP) formulations, and so they can be paired with existing MIP technology to produce provably optimal primal solutions, or to further strengthen the relaxations via cutting planes. We provide convex relaxations for networks with many 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 on image classification verification tasks on the MNIST digit data set, where we show that our relaxations are able to match the bound improvement provided by state-of-the-art MIP solvers, in orders of magnitude less time.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Deterministic Global Optimization with Artificial Neural Networks EmbeddedJournal of Optimization Theory and Applications, 2018
- Strong formulations for quadratic optimization with M-matrices and indicator variablesMathematical Programming, 2018
- Deep neural networks and mixed integer linear optimizationConstraints, 2018
- On handling indicator constraints in mixed integer programmingComputational Optimization and Applications, 2016
- A lagrangian propagator for artificial neural networks in constraint programmingConstraints, 2015
- On mathematical programming with indicator constraintsMathematical Programming, 2015
- Mixed-integer nonlinear programs featuring “on/off” constraintsComputational Optimization and Applications, 2011
- Modeling disjunctive constraints with a logarithmic number of binary variables and constraintsMathematical Programming, 2009
- On the convex hull of feasible solutions to certain combinatorial problemsOperations Research Letters, 1992
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991