- This event has passed.
Graduate Seminar: Alex Touzov
6 Mar @ 3:30 pm - 4:30 pm
Graduate Seminar
Friday, March 6th, 2020
120 Hanes Hall
3:30pm
Alex Touzov
UNC-Chapel Hill
Weak infeasibility in semidefinite programming: a complete characterization and generating all instances
Abstract: In this work, we analyze weakly infeasible semidefinite programs (SDPs). These SDPs are infeasible, but an arbitrarily small perturbation can make them feasible.
Weakly infeasible SDPs appear in many guises, some classical and some more recent: 1) as asymptotes of the semidefinite cone; as 2) difficult SDPs, which are often mistaken for feasible ones by even the best solvers; and as 3) infeasible SDPs within zero distance to ill-posedness.
We first describe a very simple combinatorial characterization of weak infeasibility in SDPs. The characterization uses elementary operations (inherited from Gaussian elimination) and reformulates the original SDP into a form that makes the weak infeasibility trivial to see. We then introduce two simple combinatorial algorithms to generate any weakly infeasible SDP: with a suitable starting data, any such SDP is obtained as an output of our algorithms. We conclude with a computational study.