Pablo A. Parrilo

Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule

  • Jason M. Altschuler
  • Pablo A. Parrilo
    • Categories Convex Optimization

    We show that for separable convex optimization, random stepsizes fully accelerate Gradient Descent. Specifically, using inverse stepsizes i.i.d. from the Arcsine distribution improves the iteration complexity from $O(k)$ to $O(k^{1/2})$, where $k$ is the condition number. No momentum or other algorithmic modifications are required. This result is incomparable to the (deterministic) Silver Stepsize Schedule which … Read more

    Sum of squares certificates for stability of planar, homogeneous, and switched systems

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We show that existence of a global polynomial Lyapunov function for a homogeneous polynomial vector field or a planar polynomial vector field (under a mild condition) implies existence of a polynomial Lyapunov function that is a sum of squares (sos) and that the negative of its derivative is also a sum of squares. This result … Read more

    On the local stability of semidefinite relaxations

  • Sameer Agarwal
  • Diego Cifuentes
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    In this paper we consider a parametric family of polynomial optimization problems over algebraic sets. Although these problems are typically nonconvex, tractable convex relaxations via semidefinite programming (SDP) have been proposed. Often times in applications there is a natural value of the parameters for which the relaxation will solve the problem exactly. We study conditions … Read more

    Stability of Polynomial Differential Equations: Complexity and Converse Lyapunov Questions

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , , , ,

    We consider polynomial differential equations and make a number of contributions to the questions of (i) complexity of deciding stability, (ii) existence of polynomial Lyapunov functions, and (iii) existence of sum of squares (sos) Lyapunov functions. (i) We show that deciding local or global asymptotic stability of cubic vector fields is strongly NP-hard. Simple variations … Read more

    Approximate cone factorizations and lifts of polytopes

  • João Gouveia
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave … Read more

    Lifts of Convex Sets and Cone Factorizations

  • João Gouveia
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representation or ‘lift’ of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over … Read more

    A Complete Characterization of the Gap between Convexity and SOS-Convexity

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

    Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials via the definition of convexity, its first order characterization, and its second order characterization are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming … Read more

    Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

  • Amir Ali Ahmadi
  • Raphaël Jungers
  • Pablo A. Parrilo
  • Mardavij Roozbehani
    • Categories Approximation Algorithms, Control Applications, Semi-definite Programming Tags , , , , ,

    We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more

    NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

  • Amir Ali Ahmadi
  • Alex Olshevsky
  • Pablo A. Parrilo
  • John N. Tsitsiklis
    • Categories Convex Optimization, Global Optimization Theory Tags , , ,

    We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic … Read more