University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Henry WolkowiczExport this event to calendar

Friday, May 27, 2011 — 3:30 PM to 4:30 PM EDT

Strong Duality in Semidefinite Programming and Facial Reduction with Applications to Sensor Network Localization and Molecular Conformation

Speaker: Henry Wolkowicz
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The Slater constraint qualification (SCQ) is essential for many classes of convex programs, e.g., Linear Programming (LP), ordinary convex programming (CP), and cone optimization (CO). However, SCQ fails for many problems, e.g., for many instances of semidefinite programming (SDP) that arise from relaxations of computationally hard problems. Thisdegeneracy results in theoretical problems (possible loss of strong duality) as well as numerical problems (due to ill-posedness). A theoretical tool to regularize these problems uses facial reduction. We present a backwards stable approach for preprocessing an SDP using facial reduction. 


In addition, we consider several applications where the structure of the problem allows us to exploit the degeneracy. Rather than presenting numerical difficulties, we obtain smaller stable problems that allow for efficient high accuracy solutions for many large scale instances. In particular, we look at facial reduction for sensor network localization (SNL) and molecular conformation (MC). For SNL we are able to exploit the low rank of the optimal solution and solve huge problems; equivalent to an SDP with order 109 variables and 106 constraints, to 16 decimal accuracy in a few minutes on a laptop. For MC, one can exploit the amino acid structure in protein molecules to significantly reduce the size of problems before using an SDP solver.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
  1. 2020 (114)
    1. December (1)
    2. November (11)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (136)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)