Amir Ali Ahmadi

On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    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 popularity. At their heart, these hierarchies rely crucially on Positivstellens\”atze from the late 20th century (e.g., due to Stengle, Putinar, or Schm\”udgen) that certify positivity of a polynomial on an … Read more

    Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations

  • Amir Ali Ahmadi
  • Antonis Papachristodoulou
  • Georgina Hall
  • James Saunderson
  • Yang Zheng
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    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 SOS programs, as the SDPs generated by this procedure are large and costly to solve when the polynomials involved in the SOS programs have a … Read more

    Semidefinite Programming and Nash Equilibria in Bimatrix Games

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Game Theory, Semi-definite Programming Tags , ,

    We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium (NE) problem and provide a number of valid inequalities to improve the quality of the relaxation. If a rank-1 solution to this SDP is … 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

    Polynomial Norms

  • Amir Ali Ahmadi
  • Etienne de Klerk
  • Georgina Hall
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    In this paper, we study polynomial norms, i.e. norms that are the dth root of a degree-d homogeneous polynomial f. We first show that a necessary and sufficient condition for f^(1/d) to be a norm is for f to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from dth … Read more

    Geometry of 3D Environments and Sum of Squares Polynomials

  • Amir Ali Ahmadi
  • Georgina Hall
  • Ameesh Makadia
  • Vikas Sindhwani
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , ,

    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: tightly containing a cloud of points (e.g., representing an obstacle) with convex or nearly-convex basic semialgebraic sets, computation of Euclidean distance between two such sets, separation of two convex … Read more

    Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation

  • Amir Ali Ahmadi
  • Sanjeeb Dash
  • Georgina Hall
    • Categories Approximation Algorithms, Linear, Cone and Semidefinite Programming, Nonlinear Optimization

    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 algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation … Read more

    DC Decomposition of Nonconvex Polynomials with Algebraic Techniques

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Statistics Tags , , ,

    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, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure … Read more

    Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Approximation Algorithms, Linear, Cone and Semidefinite Programming, Nonlinear Optimization

    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 (SDP) or sum of squares (SOS) program. The first LP and SOCP-based bounds in the sequence come from the recent work of Ahmadi and Majumdar on diagonally … 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