4 papers
Complexity of Output Feedback Stabilization
Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang +1
We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system with a linea…
Disjunctive Sum of Squares
Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua +1
We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a…
Generalized Ellipsoids
Amir Ali Ahmadi, Abraar Chaudhry, Cemil Dibek
We introduce a family of symmetric convex bodies called generalized ellipsoids of degree (GE-s), with ellipsoids corresponding to the case of . Generalized ellipsoids (…
Higher-Order Newton Methods with Polynomial Work per Iteration
Amir Ali Ahmadi, Abraar Chaudhry, Jeffrey Zhang
We present generalizations of Newton's method that incorporate derivatives of an arbitrary order but maintain a polynomial dependence on dimension in their cost per iteration.…