Anirudha Majumdar

A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics

  • Amir Ali Ahmadi
  • Georgina Hall
  • Anirudha Majumdar
    • Categories Basic Sciences Applications, Control Applications, Semi-definite Programming Tags , , , ,

    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 paper, we survey recent approaches for addressing this challenge including (i) approaches for exploiting structure (e.g., sparsity and symmetry) in a problem, (ii) approaches that produce low-rank approximate solutions to … Read more

    Response to “Counterexample to global convergence of DSOS and SDSOS hierarchies”

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming

    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 problems (POPs) and purports that this refutes claims in our extended abstract [4] and slides in [3]. The goal of this paper is to clarify that … Read more

    DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , , , , ,

    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 programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear programming and second-order cone … Read more

    Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more

    Complexity of Ten Decision Problems in Continuous Time Dynamical Systems

  • Amir Ali Ahmadi
  • Anirudha Majumdar
  • Russ Tedrake
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags ,

    We show that for continuous time dynamical systems described by polynomial differential equations of modest degree (typically equal to three), the following decision problems which arise in numerous areas of systems and control theory cannot have a polynomial time (or even pseudo-polynomial time) algorithm unless P=NP: local attractivity of an equilibrium point, stability of an … Read more