Tutte seminar - Dmitriy Drusvyatskiy

Monday, April 21, 2014 3:30 pm - 3:30 pm EDT (GMT -04:00)

Feasibility problems: from alternating projections to matrix completions.

Speaker: Dmitriy Drusvyatskiy
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 5158


Feasibility problems permeate computational mathematics. In the most general framework, we may seek a point in the intersection of two arbitrary closed sets. I will revisit an intuitive and widely used algorithm for such problems due to Van Neumann – the method of alternating projections. The algorithm proceeds by projecting an iterate onto one set, then onto the next, and so on. For two sets intersecting rigidly (in the sense that small perturbations do not destroy the intersection), the method converges linearly. Reassuringly, for semi-algebraic intersections --- prototypical pathology free problems in optimization --- ``generic’’ intersections are indeed rigid. On the other hand, for highly structured feasibility problems (such as those coming from graph embeddings), the two relevant sets tend to intersect only ``tangentially’’. I will illustrate, by focusing on the semi-definite and Euclidean distance completion problems, how this seemingly complicating feature can instead be used as an advantage.     
Joint work with V. Cheung (Waterloo), A.D. Ioffe (Technion), N. Krislock (NIU), A.S. Lewis (Cornell),  G. Pataki (UNC), H. Wolkowicz (Waterloo).