Publications

Ph.D. Thesis

  • Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis
    A. A. Ahmadi
    PhD Thesis, Massachusetts Institute of Technology, 2011
    [pdf], [abstract]

Papers

  • Generalized Ellipsoids
    A. A. Ahmadi, A. Chaudhry, C. Dibek
    Submitted, 2024
    [pdf]
     
  • Higher-Order Newton Methods with Polynomial Work per Iteration
    A. A. Ahmadi, A. Chaudhry, J. Zhang
    To appear in Advances in Mathematics, 2024
    [pdf]
     
  • Convex Ternary Quartics are SOS-Convex
    A. A. Ahmadi, G. Blekherman, P. A. Parrilo
    Submitted, 2024
    [pdf]
     
  • Robust-to-Dynamics Optimization
    A. A. Ahmadi and O. Gunluk
    To appear in Mathematics of Operations Research, 2024
    [pdf]
     
  • Safely Learning Dynamical Systems
    A. A. Ahmadi, A. Chaudhry, V. Sindhwani, S. Tu
    Submitted, 2023
    [pdf]
     
  • A Sum of Squares Characterization of Perfect Graphs
    A. A. Ahmadi, C. Dibek
    SIAM Journal on Applied Algebra and Geometry, 2023
    [pdf
     
  • Learning Dynamical Systems with Side Information
    A. A. Ahmadi and B. El Khadir
    SIAM Review (Research Spotlight paper), 2023
    Shorter version appeared in Learning for Dynamics and Control, 2020
    [pdf]
     
  • Sums of Separable and Quadratic Polynomials
    A. A. Ahmadi, C. Dibek, and G. Hall
    Mathematics of Operations Research, 2022
    [pdf
     
  • Complexity Aspects of Local Minima and Related Notions 
    A. A. Ahmadi and J. Zhang
    Advances in Mathematics, 2022
    [pdf], slides  
     
  • On the Complexity of Finding a Local Minimizer of a Quadratic Function over a Polytope
    A. A. Ahmadi and J. Zhang
    Mathematical Programming, 2022
    [pdf]
     
  • Safely Learning Dynamical Systems from Short Trajectories
    A. A. Ahmadi, A. Chaudhry, V. Sindhwani, S. Tu
    Learning for Dynamics and Control, 2021
    [pdf]
     
  • Time-Varying Semidefinite Programs
    A. A. Ahmadi and B. El Khadir
    Mathematics of Operations Research, 2021
    [pdf]

     
  • On the Complexity of Detecting Convexity over a Box
    A. A. Ahmadi and G. Hall
    Mathematical Programming, 2019
    [pdf]
     
  • On the Construction of Converging Hierarchies for Polynomial Optimization based on Certificates of Global Positivity
    A. A. Ahmadi and G. Hall
    Mathematics of Operations Research, 2019
    [pdf] [Young Researchers' Prize of the INFORMS Optimization Society]
     
  • DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization
    A. A. Ahmadi and A. Majumdar
    SIAM Journal on Applied Algebraic Geometry, 2019
    [pdf]
    (Related news article by Quanta Magazine)
    (Related rebuttal: [pdf]) 
     
  • On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization 
    A. A. Ahmadi and J. Zhang
    Mathematical Programming, 2019
    [pdf]
     
  • A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
    A. Majumdar, G. Hall, and A. A. Ahmadi
    Annual Reviews in Control, Robotics, and Autonomous Systems, 2020
    [pdf
     
  • A Globally Asymptotically Stable Polynomial Vector Field with Rational Coefficients and no Local Polynomial Lyapunov Function
    A. A. Ahmadi and B. El Khadir
    Systems & Control Letters, 2018
    [pdf]
     
  • On Algebraic Proofs of Stability for Homogeneous Vector Fields
    A. A. Ahmadi and B. El Khadir
    IEEE Transactions on Automatic Control, 2019
    [pdf
     
  • Semidefinite Programming and Nash Equilibria in Bimatrix Games
    A. A. Ahmadi and J. Zhang
    INFORMS Journal on Computing, 2019
    [pdf]
     
  • Polynomial Norms
    A. A. Ahmadi, E. de Klerk, G. Hall
    SIAM Journal on Optimization, 2019
    [pdf]
     
  • SOS-Convex Lyapunov Functions and Stability of Difference Inclusions
    A. A. Ahmadi and R. M. Jungers
    Submitted, 2018
    [pdf]
     
  • Sum of Squares Polynomials and Geometry of 3D Environments
    A. A. Ahmadi, G. Hall, A. Makadia, and V. Sindhwani
    Robotics: Science and Systems, 2017
    [pdf]
     
  • Sum of Squares Certificates for Stability of Planar, Homogeneous, and Switched Systems
    A. A. Ahmadi, Pablo A Parrilo
    IEEE Transactions on Automatic Control, 2017
    [pdf
     
  • A Characterization of Lyapunov Inequalities for Stability of Switched Systems
    R. Jungers, A. A. Ahmadi, P. A. Parrilo, and M. Roozbehani
    IEEE Transactions on Automatic Control, 2017
    [pdf
     
  • DC Decomposition of Nonconvex Polynomials with Algebraic Techniques
    A. A. Ahmadi and G. Hall
    To appear in Math Programming, 2016
    [pdf]
     
  • Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming
    A. A. Ahmadi and G. Hall
    Contemporary Mathematics, to appear, 2016
    [pdf]
     
  • Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation
    A. A. Ahmadi, S. Dash, and G. Hall
    Discrete Optimization, to appear, 2016
    [pdf]
     
  • Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations
    A. A. Ahmadi, G. Hall, A. Papachristodoulou, J. Saunderson, and Y. Zheng
    In the Proceedings of the IEEE Conference on Decision and Control, 2017
    [pdf
     
  • Robust-to-dynamics Optimization
    A. A. Ahmadi and O. Gunluk
    In preparation, 2017 - conference version appeared in the Proceedings of the 2015 IEEE Conference on Decision and Control.
    [slides]
     
  • Lower Bounds on Complexity of Lyapunov Functions for Switched Linear Systems
    A. A. Ahmadi and R. Jungers
    Nonlinear Analysis: Hybrid Systems, 2016
    [pdf]
     
  • Towards Scalable Algorithms with Formal Guarantees for Lyapunov Analysis of Control Systems via Algebraic Optimization
    A. A. Ahmadi and P. A. Parrilo
    Tutorial paper - to appear in the Proceedings of the 53rd the IEEE Conference on Decision and Control, 2014
    [pdf]
     
  • Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making
    A. A. Ahmadi and A. Majumdar
    To appear in Optimization Letters, 2015.
    [pdf]
     
  • Control and Verification of High-Dimensional Systems via DSOS and SDSOS Optimization
    A. Majumdar, A. A. Ahmadi, and R. Tedrake
    To appear in the Proceedings of the 53rd the IEEE Conference on Decision and Control, 2014
    [pdf]
     
  • DSOS and SDSOS Optimization: LP and SOCP-Based Alternatives to SOS Optimization
    A. A. Ahmadi and A. Majumdar
    In the Proceedings of the 2014 Conference on Information Sciences and Systems
     
  • On Complexity of Lyapunov Functions for Switched Linear Systems
    A. A. Ahmadi and R. Jungers
    To appear in the Proceedings of the World Congress of the International Federation of Automatic Control, 2014 
    [pdf]
     
  • Switched Stability of Nonlinear Systems via SOS-Convex Lyapunov Functions and Semidefinite Programming 
    A. A. Ahmadi and R. Jungers
    In the Proceedings of the IEEE Conference on Decision and Control, 2013 
    [pdf]
     
  • Computational and Algebraic Aspects of Convexity
    Fall 2013 Newsletter of the INFORMS Computing Society
    [link to pdf]
     
  • Modern Optimization Tools for Complex Business and Economic Dynamics
    A. A. Ahmadi 
    In preparation, 2013
     
  • Stability of Polynomial Differential Equations: Complexity and Converse Lyapunov Questions
    A. A. Ahmadi and P. A. Parrilo
    IEEE Transactions on Automatic Control, Submitted, 2013
    [pdf]
     
  • A Complete Characterization of the Gap between Convexity and SOS-Convexity
    A. A. Ahmadi and P. A. Parrilo
    SIAM Journal on Optimization, 2013 [INFORMS Computing Society Prize 1/3 ---]
    [pdf][arXiv]
     
  • NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
    A. A. Ahmadi, A. Olshevsky, P. A. Parrilo, J. N. Tsitsiklis
    Mathematical Programming , 2013 [INFORMS Computing Society Prize 2/3 ---], [MIT News]
    [pdf][arXiv]
     
  • A Convex Polynomial that Is Not SOS-Convex
    A. A. Ahmadi, P. A. Parrilo 
    Mathematical Programming , 2011 [INFORMS Computing Society Prize 3/3 ---]
    [pdf][arXiv]
     
  • Joint Spectral Radius and Path-Complete Graph Lyapunov Functions
    A. A. Ahmadi, R. Jungers, P. A. Parrilo, and M. Roozbehani
    SIAM Journal on Optimization and Control, to appear, 2014 [Best SICON Paper Prize, 2013-2015]
    [pdf][arXiv]
     
  • Complexity of Ten Decision Problems in Continuous Time Dynamical Systems
    A. A. Ahmadi, A. Majumdar, and R. Tedrake
    In Proceedings of the 2013 American Control Conference, 2012
    [pdf]
     
  • Control Design Along Trajectories via Sum of Squares Optimization
    A. Majumdar, A. A. Ahmadi, and R. Tedrake
    In Proceedings of the 2013 International Conference on Robotics and Automation, 2012
    [pdf]
     
  • Joint Spectral Radius of Rank One Matrices and the Maximum Cycle Mean Problem
    A. A. Ahmadi and P. A. Parrilo
    In Proceedings of the 51st IEEE Conference on Decision and Control, 2012 
    [pdf]
     
  • On the Difficulty of Deciding Asymptotic Stability of Cubic Homogeneous Vector fields
    A. A. Ahmadi
    In Proceedings of the American Control Conference, 2012
    [pdf][arXiv] [Best presentation in session on Stability of Nonlinear Systems]
     
  • Feasibility Checks and Control Laws for Reconfigurations of Spacecraft Clusters
    N. Moshtagh, A. A. Ahmadi, and M. Mesbahi
    In Proceedings of the American Control Conference, 2012
    [pdf]
     
  • A Globally Asymptotically Stable Polynomial Vector Field with no Polynomial Lyapunov Function
    A. A. Ahmadi, M. Krstic, P. A. Parrilo
    In Proceedings of  the 50th IEEE Conference on Decision and Control, 2011
    [pdf]
     
  • Converse Results on Existence of Sum of Squares Lyapunov Functions
    A. A. Ahmadi, P. A. Parrilo
    In Proceedings of  the 50th IEEE Conference on Decision and Control, 2011
    [pdf]
     
  • Analysis of the Joint Spectral Radius via Lyapunov Functions on Path-Complete Graphs
    A. A. Ahmadi, R. Jungers, P. A. Parrilo, M. Roozbehani
    Hybrid Systems: Computation and Control, 2011  (Book Chapter)
    [pdf]
     
  • On the Equivalence of Algebraic Conditions for Convexity and Quasiconvexity of Polynomials
    A. A. Ahmadi, P. A. Parrilo
    In Proceedings of 49th IEEE Conference on Decision and Control, 2010
    [pdf]
     
  • On Higher Order Derivatives of Lyapunov Functions
    A. A. Ahmadi, P. A. Parrilo
    In Proceedings of the 2011 American Control Conference, Submitted in 2010
    [pdf]
     
  • A Positive Definite Polynomial Hessian that Does not Factor
    A. A. Ahmadi, P. A. Parrilo
    In Proceedings of 48th IEEE Conference on Decision and Control, 2009
    [pdf]
  • Non-monotonic Lyapunov Functions for Stability of Discrete Time Nonlinear and Switched Systems
    A. A. Ahmadi, P. A. Parrilo
    In Proceedings of 47th IEEE Conference on Decision and Control, 2008
    [pdf] [Best Student Paper Award Finalist]
  • High-Speed Broadband Polarization-Independent Optical Clock Recovery in a Silicon Detector
    A. A. Ahmadi, R. Salem, T. E. Murphy
    The Optical Fiber Communication Conference, 2006
    [pdf] [Washington Society of Engineers' Young Engineer Prize]
  • Two-Photon Absorption for Optical Clock Recovery in OTDM Networks
    R.Salem, A. A. Ahmadi, G. E. Tudury, G. M. Carter, T. E. Murphy
    IEEE Journal of Lightwave Technology, 2007
    [pdf] 

Working Papers

  • Convex Ternary Quartics are SOS-Convex
    A. A. Ahmadi, G. Blekherman, P. A. Parrilo

S.M. Thesis

  • Non-monotonic Lyapunov Functions for Stability of Nonlinear and Switched Systems: Theory and Computation
    A. A. Ahmadi
    Master's Thesis, Massachusetts Institute of Technology, 2008 
    [pdf], [official]