Linear, Cone and Semidefinite Programming

A Globally Asymptotically Stable Polynomial Vector Field with Rational Coefficients and no Local Polynomial Lyapunov Function

  • Amir Ali Ahmadi
  • Bachir El Khadir
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    We give an explicit example of a two-dimensional polynomial vector field of degree seven that has rational coefficients, is globally asymptotically stable, but does not admit an analytic Lyapunov function even locally. Citation Submitted for publication Article Download View A Globally Asymptotically Stable Polynomial Vector Field with Rational Coefficients and no Local Polynomial Lyapunov Function

    Axial symmetry indices for convex cones: axiomatic formalism and applications

  • Alberto Seeger
  • Mounir Torki
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We address the issue of measuring the degree of axial symmetry of a convex cone. By following an axiomatic approach, we introduce and explore the concept of axial symmetry index. This concept is illustrated with the help of several interesting examples. By way of application, we establish a conic version of the Blekherman inequality concerning … Read more

    Optimality conditions and global convergence for nonlinear semidefinite programming

  • Roberto Andreani
  • Gabriel Haeser
  • Daiana O. Santos
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , ,

    Sequential optimality conditions have played a major role in unifying and extending global convergence results for several classes of algorithms for general nonlinear optimization. In this paper, we extend theses concepts for nonlinear semidefinite programming. We define two sequential optimality conditions for nonlinear semidefinite programming. The first is a natural extension of the so-called Approximate-Karush-Kuhn-Tucker … Read more

    SOS-Convex Lyapunov Functions and Stability of Difference Inclusions

  • Amir Ali Ahmadi
  • Raphaël Jungers
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , , , , ,

    We introduce the concept of sos-convex Lyapunov functions for stability analysis of both linear and nonlinear difference inclusions (also known as discrete-time switched systems). These are polynomial Lyapunov functions that have an algebraic certificate of convexity and that can be efficiently found via semidefinite programming. We prove that sos-convex Lyapunov functions are universal (i.e., necessary … Read more

    On Algebraic Proofs of Stability for Homogeneous Vector Fields

  • Amir Ali Ahmadi
  • Bachir El Khadir
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We prove that if a homogeneous, continuously differentiable vector field is asymptotically stable, then it admits a Lyapunov function which is the ratio of two polynomials (i.e., a rational function). We further show that when the vector field is polynomial, the Lyapunov inequalities on both the rational function and its derivative have sum of squares … Read more

    Extensions of Yuan’s Lemma to fourth-order tensor system with applications

  • Qingzhi Yang
  • Yuning Yang
  • Yang Zhou
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming

    Yuan’s lemma is a basic proposition on homogeneous quadratic function system. In this paper, we extend Yuan’s lemma to 4th-order tensor system. We first give two gen- eralized definitions of positive semidefinite of 4th-order tensor, and based on them, two extensions of Yuan’s lemma are proposed. We illustrate the difference between our ex- tensions and … Read more

    Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs

  • Samuel Burer
  • Yinyu Ye
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , ,

    We study a class of quadratically constrained quadratic programs (QCQPs), called {\em diagonal QCQPs\/}, which contain no off-diagonal terms $x_j x_k$ for $j \ne k$, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature … Read more

    On self-concordant barriers for generalized power cones

  • Scott Roy
  • Lin Xiao
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In the study of interior-point methods for nonsymmetric conic optimization and their applications, Nesterov introduced the power cone, together with a 4-self-concordant barrier for it. In his PhD thesis, Chares found an improved 3-self-concordant barrier for the power cone. In addition, he introduced the generalized power cone, and conjectured a nearly optimal self-concordant barrier for … Read more

    A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by linear programming Strong Duality into combinatorial min-max theorems. The definition of total dual integrality (TDI) revolves around the existence of optimal dual solutions that are integral, and thus naturally applies … Read more

    The first heuristic specifically for mixed-integer second-order cone optimization

  • Sertalp B. Çay
  • Imre Pólik
  • Tamás Terlaky
    • Categories Branch and Cut Algorithms, Integer Programming, Second-Order Cone Programming Tags , ,

    Mixed-integer second-order cone optimization (MISOCO) has become very popular in the last decade. Various aspects of solving these problems in Branch and Conic Cut (BCC) algorithms have been studied in the literature. This study aims to fill a gap and provide a novel way to find feasible solutions early in the BCC algorithm. Such solutions … Read more