Linear, Cone and Semidefinite Programming

Copositivity-based approximations for mixed-integer fractional quadratic optimization

  • Paula Alexandra Amaral
  • Immanuel M. Bomze
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We propose a copositive reformulation of the mixed-integer fractional quadratic problem (MIFQP) under general linear constraints. This problem class arises naturally in many applications, e.g., for optimizing communication or social networks, or studying game theory problems arising from genetics. It includes several APX-hard subclasses: the maximum cut problem, the $k$-densest subgraph problem and several of … Read more

    An LP-based Algorithm to Test Copositivity

  • Akihiro Tanaka
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    A symmetric matrix is called copositive if it generates a quadratic form taking no negative values over the nonnegative orthant, and the linear optimization problem over the set of copositive matrices is called the copositive programming problem. Recently, many studies have been done on the copositive programming problem (see, for example, \cite{aDUR10, aBOMZE12}). Among others, … Read more

    Approximating Pareto Curves using Semidefinite Relaxations

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Victor Magron
    • Categories Multi-Criteria Optimization, Semi-definite Programming

    We consider the problem of constructing an approximation of the Pareto curve associated with the multiobjective optimization problem $\min_{x \in S} \{(f_1(x),f_2(x))\}$, where $f_1$ and $f_2$ are two conflicting positive polynomial criteria and $S \subset R^n$ is a compact basic semialgebraic set. We provide a systematic numerical scheme to approximate the Pareto curve. We start … Read more

    Modal occupation measures and LMI relaxations for nonlinear switched systems control

  • Mathieu Claeys
  • Didier Henrion
  • Jamal Daafouz
    • Categories Control Applications, Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming

    This paper presents a linear programming approach for the optimal control of nonlinear switched systems where the control is the switching sequence. This is done by introducing modal occupation measures, which allow to relax the problem as a primal linear programming (LP) problem. Its dual linear program of Hamilton-Jacobi-Bellman inequalities is also characterized. The LPs … Read more

    Considering Copositivity Locally

  • Peter J.C. Dickinson
  • Roland Hildebrand
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    Let $A$ be an element of the copositive cone $\mathcal{COP}^n$. A zero $\mathbf{u}$ of $A$ is a nonnegative vector whose elements sum up to one and such that $\mathbf{u}^TA\mathbf{u} = 0$. The support of $\mathbf{u}$ is the index set $\mathrm{supp}\mathbf{u} \subset \{1,\dots,n\}$ corresponding to the nonzero entries of $\mathbf{u}$. A zero $\mathbf{u}$ of $A$ is … Read more

    Robust Stable Payoff Distribution in Stochastic Cooperative Games

  • Xuan Vinh Doan
  • Tri-Dung Nguyen
    • Categories Linear Programming, Robust Optimization, Supply Chain Management Tags , ,

    Cooperative games with transferable utilities belong to a branch of game theory where groups of players can enter into binding agreements and form coalitions in order to jointly achieve some objectives. In a cooperative setting, one of the most important questions to address is how to establish a payoff distribution among the players in such … Read more

    Inverse optimal control with polynomial optimization

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Edouard Pauwels
    • Categories Control Applications, Semi-definite Programming

    In the context of optimal control, we consider the inverse problem of Lagrangian identification given system dynamics and optimal trajectories. Many of its theoretical and practical aspects are still open. Potential applications are very broad as a reliable solution to the problem would provide a powerful modeling tool in many areas of experimental science. We … Read more

    Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations

  • Hongbo Dong
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming

    The current bottleneck of globally solving mixed-integer (nonconvex) quadratically constrained problem (MIQCP) is still to construct strong but computationally cheap convex relaxations, especially when dense quadratic functions are present. We pro- pose a cutting surface procedure based on multiple diagonal perturbations to derive strong convex quadratic relaxations for nonconvex quadratic problem with separable constraints. Our … Read more

    CBLIB 2014: A benchmark library for conic mixed-integer and continuous optimization

  • Henrik A. Friberg
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , ,

    The Conic Benchmark Library (CBLIB 2014) is a collection of more than a hundred conic optimization instances under a free and open license policy. It is the first extensive benchmark library for the advancing field of conic mixed-integer and continuous optimization, which is already supported by all major commercial solvers and spans a wide range … Read more

    Semidefinite Programming Reformulation of Completely Positive Programs: Range Estimation and Best-Worst Choice Modeling

  • Karthik Natarajan
  • Chung-Piaw Teo
    • Categories (Mixed) Integer Linear Programming, Semi-definite Programming

    We show that the worst case moment bound on the expected optimal value of a mixed integer linear program with a random objective c is closely related to the complexity of characterizing the convex hull of the points CH{(1 x) (1 x)’: x \in X} where X is the feasible region. In fact, we can … Read more