Efficient methods for several classes of ambiguous stochastic programming problems under mean-MAD information

  • Dick den Hertog
  • Krzysztof Postek
  • Ward Romeijnders
  • Maarten H. van der Vlerk
    • Categories Robust Optimization, Stochastic Programming

    We consider decision making problems under uncertainty, assuming that only partial distributional information is available – as is often the case in practice. In such problems, the goal is to determine here-and-now decisions, which optimally balance deterministic immediate costs and worst-case expected future costs. These problems are challenging, since the worst-case distribution needs to be … Read more

    Adjustable robust strategies for flood protection

  • Dick den Hertog
  • Krzysztof Postek
  • Jarl Kind
  • Chris Pustjens
    • Categories Civil and Environmental Engineering Tags , , ,

    Flood protection is of major importance to many flood-prone regions and involves substantial investment and maintenance costs. Modern flood risk management requires often to determine a cost-efficient protection strategy, i.e., one with lowest possible long run cost and satisfying flood protection standards imposed by the regulator throughout the entire planning horizon. There are two challenges … Read more

    Exact and Inexact Subsampled Newton Methods for Optimization

  • Raghu Bollapragada
  • Richard H. Byrd
  • Jorge Nocedal
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags ,

    The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and Hessian to yield a superlinear rate of convergence in expectation. The second part of … Read more

    Time and Dynamic Consistency of Risk Averse Stochastic Programs

  • Alois Pichler
  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , ,

    In various settings time consistency in dynamic programming has been addressed by many authors going all the way back to original developments by Richard Bellman. The basic idea of the involved dynamic principle is that a policy designed at the first stage, before observing realizations of the random data, should not be changed at the … Read more

    Positive and Z-operators on closed convex cones

  • Michael Orlitzky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Let K be a closed convex cone with dual K-star in a finite-dimensional real Hilbert space V. A positive operator on K is a linear operator L on V such that L(K) is a subset of K. Positive operators generalize the nonnegative matrices and are essential to the Perron-Frobenius theory. We say that L is … Read more

    Improving the Randomization Step in Feasibility Pump

  • Santanu S. Dey
  • Andres Iroume
  • Marco Molinaro
  • Domenico Salvagnin
    • Categories 0-1 Programming, Stochastic Programming Tags , , ,

    Feasibility pump (FP) is a successful primal heuristic for mixed-integer linear programs (MILP). The algorithm consists of three main components: rounding fractional solution to a mixed-integer one, projection of infeasible solutions to the LP relaxation, and a randomization step used when the algorithm stalls. While many generalizations and improvements to the original Feasibility Pump have … Read more

    The Multilinear polytope for acyclic hypergraphs

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , ,

    We consider the Multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as binary polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the Multilinear polytope … Read more

    Max-Norm Optimization for Robust Matrix Recovery

  • Ethan Fang
  • Kim-Chuan Toh
  • Han Liu
  • Wen-Xin Zhou
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , ,

    This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform … Read more

    Maximizing a class of utility functions over the vertices of a polytope

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Stochastic Programming Tags , , , , , , , ,

    Given a polytope X, a monotone concave univariate function g, and two vectors c and d, we study the discrete optimization problem of finding a vertex of X that maximizes the utility function c’x + g(d’x). This problem has numerous applications in combinatorial optimization with a probabilistic objective, including estimation of project duration with stochastic … Read more

    A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides

  • Samuel Burer
  • Guanglin Xu
    • Categories Dynamic Programming, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , , ,

    We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which … Read more