22 citations · 58 across the 13 of their papers we have counts for
16 papers · 1 filter
On Approximate Computation of Critical Points
Amir Ali Ahmadi, Georgina Hall
We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a…
Sum of Squares Submodularity
Anna Deza, Georgina Hall
We introduce the notion of -sum of squares (sos) submodularity, which is a hierarchy, indexed by , of sufficient algebraic conditions for certifying submodularity of set func…
Learning to Warm-Start Fixed-Point Optimization Algorithms
Rajiv Sambharya, Georgina Hall, Brandon Amos +1
We introduce a machine-learning framework to warm-start fixed-point optimization algorithms. Our architecture consists of a neural network mapping problem parameters to warm starts…
Sums of Separable and Quadratic Polynomials
Amir Ali Ahmadi, Cemil Dibek, Georgina Hall
We study separable plus quadratic (SPQ) polynomials, i.e., polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by th…
Shape-Constrained Regression using Sum of Squares Polynomials
Mihaela Curmei, Georgina Hall
We present a hierarchy of semidefinite programs (SDPs) for the problem of fitting a shape-constrained (multivariate) polynomial to noisy evaluations of an unknown shape-constrained…
A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
Anirudha Majumdar, Georgina Hall, Amir Ali Ahmadi
Historically, scalability has been a major challenge to the successful application of semidefinite programming in fields such as machine learning, control, and robotics. In this pa…
Engineering and Business Applications of Sum of Squares Polynomials
Georgina Hall
Optimizing over the cone of nonnegative polynomials, and its dual counterpart, optimizing over the space of moments that admit a representing measure, are fundamental problems that…
Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
Georgina Hall
The problem of optimizing over the cone of nonnegative polynomials is a fundamental problem in computational mathematics, with applications to polynomial optimization, control, mac…
On the Complexity of Detecting Convexity over a Box
Amir Ali Ahmadi, Georgina Hall
It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is…
Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations
Amir Ali Ahmadi, Georgina Hall, Antonis Papachristodoulou +2
It is well-known that any sum of squares (SOS) program can be cast as a semidefinite program (SDP) of a particular structure and that therein lies the computational bottleneck for…
On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity
Amir Ali Ahmadi, Georgina Hall
In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much…
Polynomial Norms
Amir Ali Ahmadi, Etienne de Klerk, Georgina Hall
In this paper, we study polynomial norms, i.e. norms that are the root of a degree- homogeneous polynomial . We first show that a necessary and sufficient con…
Geometry of 3D Environments and Sum of Squares Polynomials
Amir Ali Ahmadi, Georgina Hall, Ameesh Makadia +1
Motivated by applications in robotics and computer vision, we study problems related to spatial reasoning of a 3D environment using sublevel sets of polynomials. These include: tig…
Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation
Amir Ali Ahmadi, Sanjeeb Dash, Georgina Hall
We develop algorithms for inner approximating the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear a…
Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming
Amir Ali Ahmadi, Georgina Hall
We devise a scheme for solving an iterative sequence of linear programs (LPs) or second order cone programs (SOCPs) to approximate the optimal value of any semidefinite program (SD…
DC Decomposition of Nonconvex Polynomials with Algebraic Techniques
Amir Ali Ahmadi, Georgina Hall
We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, se…