Convex Relaxations of Nonconvex Quadratic Optimization Problems: Exactness Characterisations and Instance Generation
Time: Apr. 9 (Wed.) 14:00-15:00
Place: M212, Gongguan Campus, NTNU
Alper Yildirim
Reader in Operational Research, School of Mathematics, The University of Edinburgh
A quadratic optimization problem is concerned with minimizing a (nonconvex) quadratic function over a polyhedron. In addition to numerous applications, quadratic optimization problems arise as subproblems in many algorithmic frameworks for solving general nonlinear optimization problems. It is therefore a fundamental NP-hard problem in optimization.
In this talk, we give a brief survey of the theory and applications of quadratic optimization problems. We then focus on convex relaxations, i.e., convex optimization problems that yield provable bounds on the optimal value. We present a unifying perspective on the characterisation of nonconvex quadratic optimization problems that admit exact convex relaxations. We then discuss how our results can be turned into simple algorithmic procedures for constructing instances with exact and inexact relaxations.
