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 - Hayato WakiExport this event to calendar

Friday, June 17, 2011 — 3:30 PM to 4:30 PM EDT

SemiDefinite Programming Relaxation for Polynomial Optimization Problems

Speaker: Hayato Waki
Affiliation: The University of Electro-Communications
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Polynomial Optimization Problem (POP) is the problem of minimizing a polynomial objective function over a set defined by finite many polynomial equalities and/or inequalities. Lasserre proposed an approach via SemiDefinite Programming (SDP) to find a tighter lower bound or the exact optimal value of a given POP. However, it is known that the resulting SDP problems by Lasserre's approach often become large-scale and/or highly degenerate. As a result, we need to overcome these difficulties to find a lower bound or the exact optimal value of a given POP. 

This talk consists of two parts. In part I, we deal with POPs with a sparse structure. For such POPs, we propose a sparse SDP relaxation. We present some numerical results and observe that the resulting SDP relaxation problems become small enough to be solved effectively. In part II, we show that for simple POPs, the 'optimal' values of SDP relaxation problems reported by the standard SDP solvers converge to the optimal values of those POPs, while the true optimal values of SDP relaxation problems are strictly and significantly less than those values. One of this reason is that the SDP relaxation problems are highly degenerate. We also demonstrate how SDPA-GMP, a multiple precision SDP solver developed by one of the authors, can deal with this situation correctly. 
This is joint work with Masakazu Kojima, Sunyoung Kim, Masakazu Muramatsu and Maho Nakata.

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)