318 Hanes Hall, CB #3260 Chapel Hill, NC 27599-3260
919-962-1329
Loading Events

Graduate Seminar: Alex Touzov

March 6, 2020 @ 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.

 

Share This Event

  • This event has passed.

Details

Date:
March 6, 2020
Time:
3:30 pm - 4:30 pm
Event Category:

Venue

Hanes 120