Session Detail Information
Add this session to your itinerary

Cluster :  Conic Programming

Session Information  : Tuesday Jul 14, 10:20 - 11:50

Title:  Computational Issues in Semidefinite Programming
Chair: Henry Wolkowicz,Professor, University of Waterloo, Faculty of Mathematics, Waterloo ON N2L3G1, Canada, hwolkowi@uwaterloo.ca

Abstract Details

Title: Singularity Degree in Semi-definite Programming
 Presenting Author: Dmitriy Drusvyatskiy,Professor, University of Washington, Box 354350, Seattle 98195, United States of America, ddrusv@uw.edu
 Co-Author: Nathan Krislock,Assistant Professor, Northern Illinois University, 1425 W. Lincoln Hwy., DeKalb IL 60115, United States of America, krislock@math.niu.edu
 Gabor Pataki,University of North Carolina at Chapel Hill, Chapel Hill, NC, Chapel Hill, United States of America, gabor@unc.edu
 Yuen-Lam Voronin,Dr, University of Colorado, Boulder CO, United States of America, Yuen-Lam.Voronin@colorado.edu
 Henry Wolkowicz,Professor, University of Waterloo, Faculty of Mathematics, Waterloo ON N2L3G1, Canada, hwolkowi@uwaterloo.ca
 
Abstract: Degenerate semi-definite programs -- those without a strictly feasible point --- often arise in applications. The singularity degree of an SDP, introduced by Sturm, is an elegant complexity measure of such degeneracies. I will revisit this notion and its relationship to basic concepts, such as nonexposed faces of conic images, facial reduction iterations, and error bounds. Matrix completion problems will illustrate the ideas.
  
Title: Computational Aspects of Finding Lyapunov Certificates for Polynomial System via SOS Relaxation
 Presenting Author: Yuen-Lam Voronin,Dr, University of Colorado, Boulder CO, United States of America, Yuen-Lam.Voronin@colorado.edu
 Co-Author: Sriram Sankaranarayanan,Dept of Computer Science, Unversity of Colorado, Boulder CO, United States of America, srirams@colorado.edu
 
Abstract: We consider the problem of finding polynomial Lyapunov functions that certify the stability of polynomial systems. Using SOS relaxation, we often arrive at large scale semidefinite (SDP) feasibility problem instances even for polynomial systems with only modest amount of variables. We discuss some numerical difficulties that arise when solving those SDP instances. We explore several strategies for efficiently and accurately solving the SDP relaxation for finding polynomial Lyapunov functions: (1) understanding the linear maps associated with the SOS-Lyapunov stability, (2) facial reduction techniques for regularization, if necessary, and (3) specialized solution methods for finding polynomial Lyapunov certificates.
  
Title: Conic Optimization over Nonnegative Univariate Polynomials
 Presenting Author: Mohammad Ranjbar,PhD Student, Rugers University, 100 Rockafeller RD, New Brunswick NJ 08854, United States of America, 59ranjbar@gmail.com
 Co-Author: Farid Alizadeh,Professor, Rutgers University, MSIS department, 100 Rockefallar, room 5142, Piscataway NJ 08854, United States of America, alizadeh@rci.rutgers.edu
 
Abstract: We consider the conic optimization problem over nonnegative univariate polynomials and the dual moment cone; both polynomials nonnegative on an interval and on the real line are considered. It is well-known that such optimization problems can be reduced to semidefinite programming. However, this transformation may require squaring the number of variables. In addition, working with polynomials in the standard basis is notoriously ill-conditioned. We propose dual algorithms which express polynomials in the numerically stable basis of Chebyshev polynomials, and reduce cost of forming the Schur complement in interior point methods by using Fast Fourier Transform and other techniques. Concrete numerical results will be presented.