2394. Using quadratic cuts to iteratively strengthen convexifications of box quadratic programs
Invited abstract in session WB-35: MINLP 1, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.
Wednesday, 10:30-12:00Room: Michael Sadler LG15
Authors (first author is the speaker)
| 1. | Daniel Porumbel
|
| CEDRIC CS Lab, CNAM | |
| 2. | Amélie Lambert
|
| CEDRIC, CNAM |
Abstract
We consider the exact solution of minimizing a quadratic function f with box-constrained variables. Our idea is to compute convex-quadratic functions that form a piecewise-quadratic convex underestimator. To do so, we generate one by one p quadratic-convex cuts as in a cutting-planes fashion. Then, our underestimator is defined as the maximum of p convex-quadratic functions. We show that when p → ∞ the optimal solution of this relaxation converges to an optimal solution of the strong “Shor plus RLT” semi-definite relaxation of the initial problem.
The integration of the resulting quadratic convex bound into a spatial branch-and-bound algorithm allows us to solve the initial problem to global optimality. Numerical results show that even a small value of p can often be enough to reduce the branching tree size by half compared to sticking to p = 1. The resulting algorithm is also competitive in terms of CPU time compared to well-established solvers that rely on other techniques.
Full paper at cedric.cnam.fr/~porumbed/pconvex.pdf
Keywords
- Convex Optimization
- Global Optimization
- Continuous Optimization
Status: accepted
Back to the list of papers