Discrete Optimization Talks (DOTs)
DOTs are virtual discrete optimization talks, organized by Aleksandr M. Kazachkov and Elias B. Khalil. To receive updates (and the Zoom link) for upcoming DOTs, please join our mailing list. If you would like to give a DOT, please fill out this form or email us.
Topics of interest include theoretical, computational, and applied aspects of integer and combinatorial optimization.
The format is a weekly session with two 30-minute talks. Currently, the seminars are scheduled on Fridays at 1:00 p.m. ET. We will have a limited schedule for the time being, with a more active series of talks starting January 2021.
A special feature of DOTs will be a social component. After a usual talk, you might grab a tea/coffee and chat with other attendees. Why not here too? Join us for some informal discussion after each DOT and throughout the week on our Discord channel.
Videos of past DOTs are posted under Past Talks and can also be found on our Youtube Channel.
Join the mailing list to receive information about our upcoming seminars and how to virtually participate. Joining this list is necessary to receive the password for each DOT (usually sent on Monday mornings). You may also wish to subscribe to our Google calendar (also available in ics format).
Upcoming Talks
Friday, October 23, 2020 at 1:00 p.m. ET
Felipe Serrano
Zuse Institute Berlin
Zuse Institute Berlin
TBD
TBD
Sparse PSD approximation of the PSD cone
While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k × k principal submatrices — we call this the sparse SDP relaxation. Surprisingly, it has been observed empirically that in some cases this approach appears to produce bounds that are close to the optimal objective function value of the original SDP. In this talk, we formally attempt to compare the strength of the sparse SDP relaxation vis-à-vis the original SDP from a theoretical perspective. In order to simplify the question, we arrive at a data independent version of it, where we compare the sizes of SDP cone and the k-PSD closure, which is the cone of matrices where PSDness is enforced on all k × k principal submatrices. In particular, we investigate the question of how far a matrix of unit Frobenius norm in the k-PSD closure can be from the SDP cone. We provide two incomparable upper bounds on this farthest distance as a function of k and n. We also provide matching lower bounds, which show that the upper bounds are tight within a constant in different regimes of k and n. Other than linear algebra techniques, we extensively use probabilistic methods to arrive at these bounds. One of the lower bounds is obtained by observing a connection between matrices in the k-PSD closure and matrices satisfying the restricted isometry property (RIP).
This is joint work with Grigoriy Blekherman, Marco Molinaro, and Shengding Sun.
Calendar
For questions or suggestions, please contact Aleksandr M. Kazachkov or Elias B. Khalil.
DOTs are supported by the Canada Excellence Research Chair in Data Science for Real-Time Decision-Making and the University of Florida Department of Industrial and Systems Engineering.
