Valid Inequalities and Restrictions for Stochastic Programming Problems with First Order Stochastic Dominance Constraints

  • Nilay Noyan
  • Andrzej Ruszczyński
    • Categories Stochastic Programming Tags , , ,

    Stochastic dominance relations are well-studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance (SSD) constraints can be solved by linear programming (LP). However, problems involving first order stochastic dominance … Read more

    An inexact primal-dual path following algorithm for convex quadratic SDP

  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose primal-dual path-following Mehrotra-type predictor-corrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: $\min_{X} \{ \frac{1}{2} X\bullet {\cal Q}(X) + C\bullet X : {\cal A} (X) = b, X\succeq 0\}$, where ${\cal Q}$ is a self-adjoint positive semidefinite linear operator on ${\cal S}^n$, $b\in R^m$, and ${\cal A}$ is a … Read more

    Improved bounds for the symmetric rendezvous search problem on the line

  • Donglei Du
  • Q. Han
  • Juan Vera
  • Luis F. Zuluaga
    • Categories Combinatorial Optimization, Game Theory, Semi-definite Programming Tags , , ,

    A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance apart between the two players is 2. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best … Read more

    Exponential neighborhood search for a parallel machine scheduling problem

  • Yasmin Rios-Solis
  • Francis Sourd
    • Categories Applications - OR and Management Sciences, Scheduling

    We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution … Read more

    Robust Semidefinite Programming Approaches for Sensor Network Localization with Anchors

  • Nathan Krislock
  • Veronica Piccialli
  • Henry Wolkowicz
    • Categories Applications - OR and Management Sciences, Civil and Environmental Engineering, Linear, Cone and Semidefinite Programming Tags , , , , ,

    We derive a robust primal-dual interior-point algorithm for a semidefinite programming, SDP, relaxation for sensor localization with anchors and with noisy distance information. The relaxation is based on finding a Euclidean Distance Matrix, EDM, that is nearest in the Frobenius norm for the known noisy distances and that satisfies given upper and lower bounds on … Read more

    New Inequalities for Finite and Infinite Group Problems from Approximate Lifting

  • Yanjun Li
  • Jean-Philippe P. Richard
  • Lisa A. Miller
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , , , ,

    In this paper, we derive new families of piecewise linear facet-defining inequalities for the finite group problem and extreme inequalities for the infinite group problem using approximate lifting. The new valid inequalities for the finite group problem are two- and three-slope facet-defining inequalities as well as the first family of four-slope facet-defining inequalities. The new … Read more

    Perturbed projections and subgradient projections for the multiple-sets split feasibility problem

  • Yair Censor
  • Avi Motova
  • Alexander Segal
    • Categories Convex and Nonsmooth Optimization, Unconstrained Optimization

    We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in … Read more

    Target following algorithms for semidefinite programming

  • Chek Beng Chua
    • Categories Convex Optimization, Semi-definite Programming

    We present a target-following framework for semidefinite programming, which generalizes the target-following framework for linear programming. We use this framework to build weighted path-following interior-point algorithms of three distinct flavors: short-step, predictor-corrector, and large-update. These algorithms have worse-case iteration bounds that parallel their counterparts in linear programming. We further consider the problem of finding analytic … Read more

    Recognizing Underlying Sparsity in Optimization

  • Sunyoung Kim
  • Masakazu Kojima
  • Philippe L. Toint
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding … Read more

    Robust and Data-Driven Optimization: Modern Decision-Making Under Uncertainty

  • Dimitris Bertsimas
  • Aurelie Thiele
    • Categories Robust Optimization

    Traditional models of decision-making under uncertainty assume perfect information, i.e., accurate values for the system parameters and specific probability distributions for the random variables. However, such precise knowledge is rarely available in practice, and a strategy based on erroneous inputs might be infeasible or exhibit poor performance when implemented. The purpose of this tutorial is … Read more