Pablo A. Parrilo

A PTAS for the minimization of polynomials of fixed degree over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Pablo A. Parrilo
    • Categories Approximation Algorithms, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more

    The Lax conjecture is true

  • Adrian Lewis
  • Pablo A. Parrilo
  • M.V. Ramana
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    In 1958 Lax conjectured that hyperbolic polynomials in three variables are determinants of linear combinations of three symmetric matrices. This conjecture is equivalent to a recent observation of Helton and Vinnikov. CitationDepartment of Mathematics, Simon Fraser University, CanadaArticleDownload View PDF

    SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB — User’s Guide

  • Antonis Papachristodoulou
  • Stephen Prajna
  • Pablo A. Parrilo
    • Categories Convex Optimization, Problem Solving Environments, Semi-definite Programming Tags ,

    SOSTOOLS is a free MATLAB toolbox for formulating and solving sum of squares (SOS) optimization programs. It uses a simple notation and a flexible and intuitive high-level user interface to specify the SOS programs. Currently these are solved using SeDuMi, a well-known semidefinite programming solver, while SOSTOOLS handles internally all the necessary reformulations and data … Read more