Linear, Cone and Semidefinite Programming

Data-Driven Distributionally Robust Chance-Constrained Optimization with Wasserstein Metric

  • Ran Ji
  • Miguel A. Lejeune
    • Categories Robust Optimization, Second-Order Cone Programming, Stochastic Programming Tags , ,

    We study distributionally robust chance-constrained programming (DRCCP) optimization problems with data-driven Wasserstein ambiguity sets. The proposed algorithmic and reformulation framework applies to distributionally robust optimization problems subjected to individual as well as joint chance constraints, with random right-hand side and technology vector, and under two types of uncertainties, called uncertain probabilities and continuum of realizations. … Read more

    The automorphism group and the non-self-duality of p-cones

  • Masaru Ito
  • Bruno F. Lourenço
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In this paper, we determine the automorphism group of the p-cones (p\neq 2) in dimension greater than two. In particular, we show that the automorphism group of those p-cones are the positive scalar multiples of the generalized permutation matrices that fix the main axis of the cone. Next, we take a look at a problem … Read more

    A multilevel analysis of the Lasserre hierarchy

  • Juan S. Campos
  • Panos Parpas
  • Ruth Misener
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. … Read more

    On positive duality gaps in semidefinite programming

  • Gabor Pataki
    • Categories Convex Optimization, Semi-definite Programming

    We study semidefinite programs (SDPs) with positive duality gaps, i.e., different optimal values in the primal and dual problems. the primal and dual problems differ. These SDPs are considered extremely pathological, they are often unsolvable, and they also serve as models of more general pathological convex programs. We first fully characterize two variable SDPs with … Read more

    Strict Complementarity in MaxCut SDP

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

    The MaxCut SDP is one of the most well-known semidefinite programs, and it has many favorable properties. One of its nicest geometric/duality properties is the fact that the vertices of its feasible region correspond exactly to the cuts of a graph, as proved by Laurent and Poljak in 1995. Recall that a boundary point x … Read more

    An ADMM-Based Interior-Point Method for Large-Scale Linear Programming

  • Tianyi Lin
  • Shiqian Ma
  • Yinyu Ye
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper, we propose a new framework to implement interior point method (IPM) in order to solve some very large scale linear programs (LP). Traditional IPMs typically use Newton’s method to approximately solve a subproblem that aims to minimize a log-barrier penalty function at each iteration. Due its connection to Newton’s method, IPM is … Read more

    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