123 citations · 525 across the 31 of their papers we have counts for
42 papers
A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting
Amir Ali Ahmadi, Pravesh K. Kothari, Yukai Tang
We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perf…
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…
Convex Ternary Quartics Are SOS-Convex
Amir Ali Ahmadi, Grigoriy Blekherman, Pablo A. Parrilo
We prove that convex ternary quartic forms are sum-of-squares-convex (sos-convex). This result is in a meaningful sense the ``convex analogue'' a celebrated theorem of Hilbert from…
Safely Learning Dynamical Systems
Amir Ali Ahmadi, Abraar Chaudhry, Vikas Sindhwani +1
A fundamental challenge in learning an unknown dynamical system is to reduce model uncertainty by making measurements while maintaining safety. We formulate a mathematical definiti…
A Sum of Squares Characterization of Perfect Graphs
Amir Ali Ahmadi, Cemil Dibek
We present an algebraic characterization of perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph. We show that a gr…
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…
Safely Learning Dynamical Systems from Short Trajectories
Amir Ali Ahmadi, Abraar Chaudhry, Vikas Sindhwani +1
A fundamental challenge in learning to control an unknown dynamical system is to reduce model uncertainty by making measurements while maintaining safety. In this work, we formulat…
Learning Dynamical Systems with Side Information
Amir Ali Ahmadi, Bachir El Khadir
We present a mathematical and computational framework for the problem of learning a dynamical system from noisy observations of a few trajectories and subject to side information.…
Complexity aspects of local minima and related notions
Amir Ali Ahmadi, Jeffrey Zhang
We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and…
On the complexity of finding a local minimizer of a quadratic function over a polytope
Amir Ali Ahmadi, Jeffrey Zhang
We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance (for any constant ) of a local minimizer of an …
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…
Time-Varying Semidefinite Programs
Amir Ali Ahmadi, Bachir El Khadir
We study time-varying semidefinite programs (TV-SDPs), which are semidefinite programs whose data (and solutions) are functions of time. Our focus is on the setting where the data…
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…
Robust-to-Dynamics Optimization
Amir Ali Ahmadi, Oktay Gunluk
A robust-to-dynamics optimization (RDO) problem is an optimization problem specified by two pieces of input: (i) a mathematical program (an objective function $f:\mathbb{R}^n\right…
SOS-Convex Lyapunov Functions and Stability of Difference Inclusions
Amir Ali Ahmadi, Raphael M. Jungers
We introduce the concept of sos-convex Lyapunov functions for stability analysis of both linear and nonlinear difference inclusions (also known as discrete-time switched systems).…
On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization
Amir Ali Ahmadi, Jeffrey Zhang
We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem wh…
A Globally Asymptotically Stable Polynomial Vector Field with Rational Coefficients and no Local Polynomial Lyapunov Function
Amir Ali Ahmadi, Bachir El Khadir
We give an explicit example of a two-dimensional polynomial vector field of degree seven that has rational coefficients, is globally asymptotically stable, but does not admit an an…
On Algebraic Proofs of Stability for Homogeneous Vector Fields
Amir Ali Ahmadi, Bachir El Khadir
We prove that if a homogeneous, continuously differentiable vector field is asymptotically stable, then it admits a Lyapunov function which is the ratio of two polynomials (i.e., a…
Sum of squares certificates for stability of planar, homogeneous, and switched systems
Amir Ali Ahmadi, Pablo A. Parrilo
We show that existence of a global polynomial Lyapunov function for a homogeneous polynomial vector field or a planar polynomial vector field (under a mild condition) implies exist…
Response to "Counterexample to global convergence of DSOS and SDSOS hierarchies"
Amir Ali Ahmadi, Anirudha Majumdar
In a recent note [8], the author provides a counterexample to the global convergence of what his work refers to as "the DSOS and SDSOS hierarchies" for polynomial optimization prob…
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…
Semidefinite Programming and Nash Equilibria in Bimatrix Games
Amir Ali Ahmadi, Jeffrey Zhang
We explore the power of semidefinite programming (SDP) for finding additive -approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic…
DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization
Amir Ali Ahmadi, Anirudha Majumdar
In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite progra…