Category Archives: Uncategorized

Amir Ali Ahmadi; Nonnegative polynomials: from optimization to control and learning

CORE Series
Amir Ali Ahmadi, ORFE, Princeton University
Friday, May 17, 2019
ECE 037, 2:30-3:30pm

Poster PDF

*Title:
Nonnegative polynomials: from optimization to control and learning

*Speaker:
Amir Ali Ahmadi
Princeton, ORFE

*Abstract:
The problem of recognizing nonnegativity of a multivariate polynomial
has a celebrated history, tracing back to Hilbert’s 17th problem. In
recent years, there has been much renewed interest in the topic
because of a multitude of applications in applied and computational
mathematics and the observation that one can optimize over an
interesting subset of nonnegative polynomials using “sum of squares
optimization”.

In this talk, we give a brief overview of some of our recent
contributions to this area. In part (i), we propose more scalable
alternatives to sum of squares optimization and show how they impact
verification problems in control and robotics. Our algorithms do not
rely on semidefinite programming, but instead use linear programming,
or second-order cone programming, or are altogether free of
optimization. In particular, we present the first Positivstellensatz
that certifies infeasibility of a set of polynomial inequalities
simply by multiplying certain fixed polynomials together and checking
nonnegativity of the coefficients of the resulting product.

In part (ii), we study the problem of learning dynamical systems from
very limited data but in presence of “side information”, such as
physical laws or contextual knowledge. This is motivated by
safety-critical applications where an unknown dynamical system needs
to be controlled after a very short learning phase where a few of its
trajectories are observed. (Imagine, e.g., the task of autonomously
landing a passenger airplane that has gone through sudden wing
damage.) We show that sum of squares and semidefinite optimization are
particularly suited for exploiting side information in order to assist
the task of learning when data is limited. Joint work with A. Majumdar
and G. Hall (part (i)) and with B. El Khadir (part (ii)).

*Bio:
Amir Ali Ahmadi ( http://aaa.princeton.edu/ ) is a Professor at the
Department of Operations Research and Financial Engineering at
Princeton University and an Associated Faculty member of the Program
in Applied and Computational Mathematics, the Department of Computer
Science, the Department of Mechanical and Aerospace Engineering, and
the Center for Statistics and Machine Learning. Amir Ali received his
PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson
Research Center prior to joining Princeton. His research interests are
in optimization theory, computational aspects of dynamics and control,
and algorithms and complexity. Amir Ali’s distinctions include the
Sloan Fellowship in Computer Science, a MURI award from the AFOSR, the
NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA
Faculty Award, the Google Faculty Award, the Howard B. Wentz Junior
Faculty Award as well as the Innovation Award of Princeton University,
the Goldstine Fellowship of IBM Research, and the Oberwolfach
Fellowship of the NSF. His undergraduate course at Princeton (ORF 363,
“Computing and Optimization’’) has received the 2017 Excellence in
Teaching of Operations Research Award of the Institute for Industrial
and Systems Engineers and the 2017 Phi Beta Kappa

Rainer Sinn and Daniel Plaumann; From conic programming to real algebraic geometry and back

Rainer Sinn, Fachbereich Mathematik und Informatik, Freie Universität Berlin
Daniel Plaumann, Fakultät für Mathematik, Technische Universität Dortmund 

Tuesday May 14, 2019, More Hall 234, 4pm-5:30pm

Poster PDF

Title: From conic programming to real algebraic geometry and back

Abstract: In this talk, we will present interactions between conic programming, a branch of optimization, and real algebraic geometry, the algebraic and geometric study of real polynomial systems. This has led to a number of beautiful mathematical theorems, both improving our understanding of the geometric picture as well as sharpening our tools for applications.

On the optimization side, we will take a look at hyperbolic programs, an instance of conic programs first studied in the 1990s that comprises linear programs as well as semidefinite programs. On the algebraic side, it is based on the theory of hyperbolic respectively real stable polynomials, which show up in many parts of mathematics, ranging from control theory to combinatorics. In many ways, hyperbolic polynomials behave like determinants of families of symmetric matrices. We will compare these two paradigms, one based in matrix calculus, the other purely in algebraic geometry, through a series of examples, pictures, theorems, and conjectures.

 

Bios:

Daniel Plaumann has been associate professor of algebra and its applications at TU Dortmund, Germany, since 2016. His research interests are real and classical algebraic geometry, positive polynomials, matrix inequalities, and applications to optimization and functional analysis. He received his PhD in 2008 from the University of Konstanz under the supervision of Claus Scheiderer. In 2010, he was Feodor Lynen Fellow of the Alexander von Humboldt Foundation at UC Berkeley and in 2014 Research Fellow at the Nanyang Technological University in Singapore. From 2013-2016 he was Research Felllow at the Zukunftskolleg of the University of Konstanz. He is currently a long-term visitor at the Simons Institute for the Theory of Computing in Berkeley.
 
Rainer Sinn has been assistant professor for discrete geometry at Freie Universität Berlin, Germany, since 2017. His research interests are discrete, convex, and real algebraic geometry. He graduated from the University of Konstanz in 2014 under the supervision of Claus Scheiderer with a fellowship of the German National Academic Foundation. In 2014, before moving to the Georgia Institute of Technology for a postdoc position with Greg Blekherman, he was a visiting researcher at the National Institute of Mathematical Sciences in Daejeon, Korea, during a Thematic Program on Applied Algebraic Geometry. In 2017, he was at the Max Planck Institute for Mathematics in the Sciences in Leipzig as a member of the Nonlinear Algebra group led by Bernd Sturmfels. He is currently a research fellow at the Simons Institute for the Theory of Computing in Berkeley as part of the program on Geometry of Polynomials.

Jon Kleinberg; Incen­tives for Col­lec­tive Behav­ior: Badges, Pro­cras­ti­na­tion, and Long-Range Goals

CORE Series, joint with ​CSE Distinguished Lecture Series, Data Science Seminar​
January 15, 2014, 3:30pm
EEB 105
Jon Kleinberg, Depart­ments of Com­puter Sci­ence and Infor­ma­tion Sci­ence, Cornell Uni­ver­sity.
Incen­tives for Col­lec­tive Behav­ior: Badges, Pro­cras­ti­na­tion, and Long-Range Goals

Abstract: Many systems involve the allocation of rewards for achievements, and these rewards produce a set of incentives that in turn guide behavior. Such effects are visible in many domains from everyday life, and they are increasingly forming a designed aspect of participatory on-line sites through the use of badges and other reward systems. We consider several aspects of the interaction between rewards and incentives in the context of collective effort, including a method for reasoning about on-line user activity in the presence of badges, and a graph-theoretic framework for analyzing procrastination and other forms of behavior that are inconsistent over time. The talk will be based on joint work with Ashton Anderson, Dan Huttenlocher, Jure Leskovec, and Sigal Oren.

Bio: Professor Kleinberg is a professor at Cornell University. His research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other on-line media. His work has been supported by an NSF Career Award, an ONR Young Investigator Award, a MacArthur Foundation Fellowship, a Packard Foundation Fellowship, a Simons Investigator Award, a Sloan Foundation Fellowship, and grants from Google, Yahoo!, and the NSF. He is a member of the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Sciences.

Henry Wolkowicz; Taking Advantage of Degeneracy in Cone Optimization: with Applications to Sensor Network Localization

November 13, 2014, 4:00pm
EEB 003
Henry Wolkowicz, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Water­loo.
Taking Advantage of Degeneracy in Cone Optimization: with Applications to Sensor Network Localization

Abstract: The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. However, the theory and preprocessing techniques that are successful for LP can fail for cone programming over nonpolyhedral cones.

Surprisingly, many important applications of semidefinite programming, SDP, that arise from relaxations of hard combinatorial problems are degenerate. (Slater’s constraint qualification fails.) This includes relaxations for problems such as the: Quadratic Assignment; Graph Partitioning; Set Covering and partitioning; and sensor network localization and molecular conformation. Rather than being a disadvantage, we show that this degeneracy can be exploited. In particular, several huge instances of SDP completion problems can be solved quickly and to extremely high accuracy. In particular, we illustrate this on the sensor network localization problem.

Peter Bürgisser; Condition of Convex Optimization and Spherical Intrinsic Volumes

CORE Series
December 2, 2014, 4:00pm
EE 125
Peter Bürgisser, Insti­tute for Math­e­mat­ics, TU Berlin.
Condition of Convex Optimization and Spherical Intrinsic Volumes

Abstract: The analysis of the stability and efficiency of algorithms for convex optimization naturally leads to the study of condition numbers. The Grassmann condition, which is a geometric version of Renegar’s condition, is especially suited for a probabilistic analysis. Such analysis can be performed by relying on techniques from spherical convex geometry and differential geometry. Along this way, we obtain an average analysis of the Grassmann condition number that holds for any regular convex cone. A closer look prompts the investigation of the spherical counterparts of intrinsic volumes — a notion thoroughly studied for euclidean spaces, but much less so for spheres, so that many fascinating questions remain.
Joint work with Dennis Amelunxen.

Peter Bürgisser

Bio: Peter Bürgisser has been a professor of Mathematics at the Technical University of Berlin since 2013. Prior to that he was a professor of Mathematics at the University of Paderborn. His research interests are algebraic complexity theory, symbolic and numeric computation, and more recently, the probabilistic analysis of numerical algorithms. Bürgisser was an invited speaker at the International Congress of Mathematicians in Hyderabad in 2010 and plenary speaker at Foundations of Computational Mathematics 2008 in Hong Kong. He is an associate editor of Computational Complexity, and an editor of the journal Foundations of Computational Mathematics. He served as a workshop co-organizer for the Foundations of Computational Mathematics conferences (2005, 2008, 2011), for the Special Year on Applications of Algebraic Geometry (IMA 2006/2007), and for the Oberwolfach workshops on Complexity Theory (2009, 2012). His research interests lie in algebraic complexity theory: both the design of efficient algorithms for algebraic problems, and the quest for lower bounds.

Jonathan Hauenstein; Opti­miza­tion and Numer­i­cal Alge­braic Geometry

October 28, 2014, 4:00pm
GUG 204
Jonathan Hauenstein, Depart­ment of Applied and Com­pu­ta­tional Math­e­mat­ics and Sta­tis­tics, Uni­ver­sity of Notre Dame.
Opti­miza­tion and Numer­i­cal Alge­braic Geometry

Abstract: Classically, one can observe the combination of algebraic geometry and optimization in solving polynomial systems constructed from necessary condition of polynomial optimization problems. More recently, the connection between semidefinite programming and real algebraic geometry has been exploited. This talk will explore another use of optimization related to algebraic geometry, namely to construct homotopies in numerical algebraic geometry for solving polynomial systems. This idea has been used recently to solve a problem in real enumerative geometry. This talk will conclude with using algebraic geometry to solve sparse optimization problems arising from the concept of matrix rigidity. To incorporate a broad audience, all necessary concepts related to algebraic geometry and homotopies will be covered.

Elina Robeva; Fixed Points of the EM Algorithm and Nonnegative Rank Boundaries

May 27, 2014, 4:00pm
EEB 303
Elina Robeva, Department of Mathematics, UC Berkeley.
Fixed Points of the EM Algorithm and Nonnegative Rank Boundaries

Abstract: Matrices of nonnegative rank $r$ represent mixtures of $r$ independent distributions for two random variables. Likelihood inference for this model leads to problems in real algebraic geometry that we address in this paper. We characterize the set of fixed points of Expectation Maximization, and we study the boundary of the space of matrices with nonnegative rank at most $3$. Both of these correspond to algebraic varieties with many irreducible components.