Linear, Cone and Semidefinite 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

    Polyhedral-based Methods for Mixed-Integer SOCP in Tree Breeding

  • Tim J. Mullin
  • Sena Safarina
  • Makoto Yamashita
    • Categories (Mixed) Integer Linear Programming, Second-Order Cone Programming

    Optimal contribution selection (OCS) is a mathematical optimization problem that aims to maximize the total benefit from selecting a group of individuals under a constraint on genetic diversity. We are specifically focused on OCS as applied to forest tree breeding, when selected individuals will contribute equally to the gene pool. Since the diversity constraint in … 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

    Refining the partition for multifold conic optimization problems

  • Héctor Ramírez
  • Vera Roshchina
    • Categories Linear, Cone and Semidefinite Programming Tags ,

    In this paper we give a unified treatment to different definitions of complementarity partition for a primal-dual pair of linear conic optimization problem. Citation Submitted ArXiv 1804.00386 http://arxiv.org/abs/1804.00386 Article Download View Refining the partition for multifold conic optimization problems

    Shortfall Risk Models When Information of Loss Function Is Incomplete

  • Erick Delage
  • Shaoyan Guo
  • Huifu Xu
    • Categories Linear Programming, Robust Optimization, Stochastic Programming Tags , , , , , ,

    Utility-based shortfall risk measure (SR) has received increasing attentions over the past few years for its potential to quantify more effectively the risk of large losses than conditional value at risk. In this paper we consider the case that the true loss function is unavailable either because it is difficult to be identified or the … Read more

    A quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems

  • I. L. Galabova
  • J. A. Julian Hall
    • Categories Linear Programming

    This paper provides the first meaningful documentation and analysis of an established technique which aims to obtain an approximate solution to linear programming problems prior to applying the primal simplex method. The underlying algorithm is a penalty method with naive approximate minimization in each iteration. During initial iterations an approach similar to augmented Lagrangian is … Read more

    Trust your data or not – StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization

  • Immanuel M. Bomze
  • Michael Kahr
  • Markus Leitner
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    We consider the Robust Standard Quadratic Optimization Problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is extremized over the standard simplex. Following most approaches, we model the uncertainty sets by ellipsoids, polyhedra, or spectrahedra, more precisely, by intersections of sub-cones of the copositive matrix cone. We show that the copositive relaxation gap of … 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

    Solving Pooling Problems by LP and SOCP Relaxations and Rescheduling Methods

  • Sunyoung Kim
  • Masaki Kimizuka
  • Makoto Yamashita
    • Categories Applications - Science and Engineering, Linear, Cone and Semidefinite Programming Tags , , , , ,

    The pooling problem is an important industrial problem in the class of network flow problems for allocating gas flow in pipeline transportation networks. For P-formulation of the pooling problem with time discretization, we propose second order cone programming (SOCP) and linear programming (LP) relaxations and prove that they obtain the same optimal value as the … Read more