Seminar: Gizem Sağol Mullaoğlu, “On Polyhedral Approximations of Copositive Formulations of Certain Quadratic Optimization Problems”

Date-Time: April 22, 2016 – 10.00

Place: F003

On Polyhedral Approximations of Copositive Formulations of Certain Quadratic Optimization Problems

by Gizem Sağol Mullaoğlu

A matrix is called copositive if its quadratic form is nonnegative for all nonnegative vectors. Copositive optimization is the minimization (or maximization) of a linear objective function subject to linear equality constraints over the cone of copositive matrices. A large class of NP-hard problems can be exactly reformulated as copositive optimization problems. Furthermore, the convex cone of copositive matrices can be approximated from the inside and from the outside by two sequences of nested polyhedral cones. It is an intriguing area since it allows a new perspective for difficult optimization problems. In this seminar, we focus on the copositive reformulation of a certain class of NP-hard optimization problems. We provide the theoretical aspects of inner and outer polyhedral approximations for these specific optimization problems. The first problem class we study is standard quadratic programming problems. We give a complete description of the instances on which upper and lower bounds are already exact at a finite level of the hierarchy, and the instances on which upper and lower bounds converge to the optimal value only in the limit. Next, we analyze the box constrained quadratic optimization problems (BoxQP). We consider alternative formulations. We study the sequences of upper and lower bounds on the optimal value of a (BoxQP) arising from the two hierarchies of inner and outer polyhedral approximations for both of these formulations. Our main objectives are to give characterizations of easier instances of NP-hard problems and to shed light on the quality of approximation resulting from the inner and outer polyhedral approximations.

Short Bio:

Gizem Sağol Mullaoğlu is a Ph.D. candidate at the Department of Industrial Engineering and Operations Management, Koç University. She holds a B.S. degree in Industrial Engineering from Bilkent University. Her research interests are polyhedral approximations, copositive optimization and conic optimization.