Semi-definite Programming

Distributionally robust optimization with polynomial densities: theory, models and algorithms

  • Etienne de Klerk
  • Daniel Kuhn
  • Krzysztof Postek
    • Categories Robust Optimization, Semi-definite Programming Tags , , ,

    In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a known ambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distribution that give nature too much … Read more

    A new approximation algorithm for unrelated parallel machine scheduling problem with release dates

  • Zhi Pei
  • Ziteng Wang
  • Mingzhong Wan
    • Categories Approximation Algorithms, Scheduling, Semi-definite Programming

    In this research, we consider the unrelated parallel machine scheduling problem with release dates. The goal of this scheduling problem is to find an optimal job assignment with minimal sum of weighted completion times. As it is demonstrated in the present paper, this problem is NP-hard in the strong sense. Albeit the computational complexity, which … Read more

    Representation of distributionally robust chance-constraints

  • Jean-Bernard Lasserre
  • Tillmann Weisser
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming, Stochastic Programming

    Given $X\subset R^n$, $\varepsilon \in (0,1)$, a parametrized family of probability distributions $(\mu_{a})_{a\in A}$ on $\Omega\subset R^p$, we consider the feasible set $X^*_\varepsilon\subset X$ associated with the {\em distributionally robust} chance-constraint \[X^*_\varepsilon\,=\,\{x\in X:\:{\rm Prob}_\mu[f(x,\omega)\,>\,0]> 1-\varepsilon,\,\forall\mu\in\mathscr{M}_a\},\] where $\mathscr{M}_a$ is the set of all possibles mixtures of distributions $\mu_a$, $a\in A$. For instance and typically, the family … Read more

    Moments and convex optimization for analysis and control of nonlinear partial differential equations

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Milan Korda
    • Categories Distributed Control, Optimization of Systems modeled by PDEs, Semi-definite Programming Tags , , , ,

    This work presents a convex-optimization-based framework for analysis and control of nonlinear partial differential equations. The approach uses a particular weak embedding of the nonlinear PDE, resulting in a \emph{linear} equation in the space of Borel measures. This equation is then used as a constraint of an infinite-dimensional linear programming problem (LP). This LP is … Read more

    On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known “Frank-Wolfe type” theorems … Read more

    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

    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