[CSDM] ORFE Seminar: Amir Ali Ahmadi, February 12 at 4:30pm, Sherrerd Hall 101

[Philippe Rigollet]

This ORFE talk might be of interest to the theory folks.
Philippe
--
Philippe Rigollet
www.princeton.edu/~rigollet<http://www.princeton.edu/~rigollet>





Begin forwarded message:

From: Lisa Glass <lglass at PRINCETON.EDU<mailto:lglass at PRINCETON.EDU>>
Subject: [ORFE seminars] ORFE Seminar: Amir Ali Ahmadi, February 12 at 4:30pm, Sherrerd Hall 101
Date: February 6, 2013 12:14:27 PM EST
To: <ORFE-TALKS at Princeton.EDU<mailto:ORFE-TALKS at Princeton.EDU>>
Reply-To: Lisa Glass <lglass at PRINCETON.EDU<mailto:lglass at PRINCETON.EDU>>



=== ORFE Seminar Announcement ===

DATE:   Tuesday, February 12, 2013

TIME:   4:30pm

LOCATION:   Room 101, Sherrerd Hall

SPEAKER:  Amir Ali Ahmadi, IBM Watson Research Center

TITLE:  The Interplay of Convexity and Algorithmic Algebra in Oprimization and Systems Analysis

ABSTRACT:

Exciting recent developments at the interface of computational algebra and convex optimiza-
tion have led to major algorithmic advances in a broad range of problems in optimization
and systems theory. I will start this talk by giving an overview of these techniques and
presenting applications in continuous and combinatorial optimization, statistics, and control
theory. I will then focus on two recent results on computational and algebraic aspects of
convexity in optimization: (i) I will show that deciding convexity of polynomials of degree as
low as four is strongly NP-hard. This solves a problem that appeared as one of seven open
problems in complexity theory for numerical optimization in 1992. (ii) I will introduce an
algebraic, semidefinite programming (SDP) based sufficient condition for convexity known
as sum-of-squares-convexity and present a complete characterization of the cases where it
is equivalent to convexity. This characterization draws an interesting parallel to a seminal
1888 result of Hilbert in real algebraic geometry.
In the final part of the talk, I will move on to a problem with numerous applications in
engineering and sciences: understanding the asymptotic behavior of linear dynamical systems
under uncertainty. I will tackle this problem with a novel class of SDP-based algorithms (with
provable guarantees) that are based on new connections between ideas from control theory
and the theory of finite automata.





-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20130211/0557b215/attachment-0001.html>