Fall 2014 Seminar Series

DATE: 11/20/2014
LOCATION: E51-335
TIME: 4:15pm
Reception immediately following

SPEAKER:
Fatma Kılınç-Karzan

TITLE
Structure in Disjunctive Conic Optimization and Non-convex Quadratic Programs

ABSTRACT
Non-convex optimization problems with conic constraints are critical components of operational problems in many diverse fields facing uncertainty, and thus have gained considerable interest recently. While these problems can be stated as Disjunctive Conic Programs involving a regular cone K such as the nonnegative orthant, the second-order cone (SOC) or the positive semidefinite cone, they remain to be very challenging to solve. In this talk, we will describe the broad background of such problems, together with our recent developments, which unify and extend previous results. First, we will introduce K-minimality notion to identify dominance relations among valid linear inequalities for these problems, and show how tight K-minimal inequalities underlie both the strong (functional) duality theorems for linear (and also specific conic) integer programs and the derivations of closed form expressions for convex hull descriptions in simple setups such as split disjunctions on SOCs. Our results also highlight several challenges faced in the non-convex quadratic setups such as the need for general convex inequalities as opposed to the inequalities in conic form. Second, we will study structured non-convex sets defined by the intersection of a SOC representable constraint, a single homogeneous non-convex quadratic and an affine hyperplane. We will derive simple, computable convex relaxations given by a new SOC representable constraint, and show that our relaxations precisely describe the corresponding convex hull under easy to check conditions. We illustrate the applicability and generality of our approach with many examples including how to solve the classical trust region problem by only relying on SOC optimization.

 

Parts of this talk are based on joint works with Sam Burer and Sercan Yıldız.