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.

Seminar - Yinyu YeExport this event to calendar

Wednesday, July 10, 2013 — 3:00 PM to 4:00 PM EDT

Complexity Analysis beyond Convex Optimization

Speaker: Yinyu Ye
Affiliation: Standford University
Room: Mathematics and Computer Building (MC) 5158

Abstract:

A powerful approach to solving difficult optimization problems is convex relaxation. In a typical application, the problem is first formulated as a cardinality-constrained linear program (LP) or rank–constrained semidefinite program (SDP), where the cardinality or rank corresponds to the target support size or dimension. Then, the non–convex cardinality or rank constraint is either dropped or replaced by a convex surrogate, thus resulting in a convex optimization problem. In this talk, we explore the use of a non–convex surrogate of the cardinality or rank function, namely the so–called Schatten quasi–norm. Although the resulting optimization problem is non–convex, we show, for many cases, that a first and second order critical point can be approximated to arbitrary accuracy in polynomial time. We also generalize and summarize our complexity analysis results to more general non-convex optimization, which recently becomes a popular research topic and has wide applications.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
25
26
27
28
29
30
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
31
1
2
3
4
5
  1. 2021 (45)
    1. May (5)
    2. April (9)
    3. March (13)
    4. February (8)
    5. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    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)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)