Robert Hildebrand - Compact mixed-integer programming relaxations in quadratic optimization
663 بار بازدید -
3 سال پیش
-
Part of Discrete Optimization Talks:
Part of Discrete Optimization Talks: https://talks.discreteopt.com
Robert Hildebrand - Virginia Tech
Compact mixed-integer programming relaxations in quadratic optimization
Speaker webpage: https://sites.google.com/site/robertd...
Abstract: In joint work with Ben Beach and Joey Huchette, we present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky, formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in the approximation error. Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. Further, we show that our formulation represents feasible points via a Gray code. We close with computational results on problems with quadratic objectives and/or constraints, showing that our proposed method i) across the board outperforms existing MIP relaxations from the literature, and ii) on hard instances produces better bounds than exact solvers within a fixed time budget.
Bio: Robert is an assistant professor in the Grado Department of Industrial and Systems Engineering (ISE) at Virginia Tech. He obtained his PhD in 2013 at the University of California, Davis under the supervision of Matthias Köppe. Afterward, he spent two years in Zurich, Switzerland as a postdoctoral researcher at the Institute for Operations Research in the Department for Mathematics at ETH Zurich. Subsequently, he was a Goldstine Fellow Postdoctoral Researcher at IBM Watson Research Center in Yorktown Heights, New York, and also participated in the semester-long Simons Institute program on Bridging Continuous and Discrete Optimization at UC Berkeley.
Robert's current research interests are Mixed-Integer Nonlinear Optimization, Cutting Plane Theory and Practice, Redistricting, Stochastic Scheduling and Machine Learning.
Robert Hildebrand - Virginia Tech
Compact mixed-integer programming relaxations in quadratic optimization
Speaker webpage: https://sites.google.com/site/robertd...
Abstract: In joint work with Ben Beach and Joey Huchette, we present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky, formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in the approximation error. Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. Further, we show that our formulation represents feasible points via a Gray code. We close with computational results on problems with quadratic objectives and/or constraints, showing that our proposed method i) across the board outperforms existing MIP relaxations from the literature, and ii) on hard instances produces better bounds than exact solvers within a fixed time budget.
Bio: Robert is an assistant professor in the Grado Department of Industrial and Systems Engineering (ISE) at Virginia Tech. He obtained his PhD in 2013 at the University of California, Davis under the supervision of Matthias Köppe. Afterward, he spent two years in Zurich, Switzerland as a postdoctoral researcher at the Institute for Operations Research in the Department for Mathematics at ETH Zurich. Subsequently, he was a Goldstine Fellow Postdoctoral Researcher at IBM Watson Research Center in Yorktown Heights, New York, and also participated in the semester-long Simons Institute program on Bridging Continuous and Discrete Optimization at UC Berkeley.
Robert's current research interests are Mixed-Integer Nonlinear Optimization, Cutting Plane Theory and Practice, Redistricting, Stochastic Scheduling and Machine Learning.
3 سال پیش
در تاریخ 1400/02/10 منتشر شده
است.
663
بـار بازدید شده