Month: February 2019

A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary fi rst and second stage variables

  • Ignacio E. Grossmann
  • Can Li
    • Categories Stochastic Programming

    In this paper, we propose a generalized Benders decomposition-based branch and cut algorithm for solving two stage stochastic mixed-integer nonlinear programs (SMINLPs) with mixed binary rst and second stage variables. At a high level, the proposed decomposition algorithm performs spatial branch and bound search on the rst stage variables. Each node in the branch and … Read more

    Exploiting Sparsity for Semi-Algebraic Set Volume Computation

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Matteo Tacchi
  • Tillmann Weisser
    • Categories Convex Optimization, Semi-definite Programming

    We provide a systematic deterministic numerical scheme to approximate the volume (i.e. the Lebesgue measure) of a basic semi-algebraic set whose description follows a sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set. This is … Read more

    A scalable mixed-integer decomposition approach for optimal power system restoration

  • Ignacio Aravena
  • Shmuel Oren
  • Deepak Rajan
  • Georgios Patsakis
  • Jennifer Rios
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Energy Tags , , ,

    The optimal restoration problem lies at the foundation of the evaluation and improvement of resilience in power systems. In this paper we present a scalable decomposition algorithm, based on the integer L-shaped method, for solving this problem for realistic power systems. The algorithm works by partitioning the problem into a master problem and a slave … Read more

    Non-asymptotic Results for Langevin Monte Carlo: Coordinate-wise and Black-box Sampling

  • Krishnakumar Balasubramanian
  • Saeed Ghadimi
  • Lingqing Shen
    • Categories Nonlinear Optimization, Statistics Tags , , ,

    Euler-Maruyama and Ozaki discretization of a continuous time diffusion process is a popular technique for sampling, that uses (upto) gradient and Hessian information of the density respectively. The Euler-Maruyama discretization has been used particularly for sampling under the name of Langevin Monte Carlo (LMC) for sampling from strongly log-concave densities. In this work, we make … Read more

    Subdifferentials and SNC property of scalarization functionals with uniform level sets and applications

  • Christiane Tammer
  • Bao Q. Truong
    • Categories Constrained Nonlinear Optimization, Multi-Criteria Optimization, Nonsmooth Optimization

    This paper deals with necessary conditions for minimal solutions of constrained and unconstrained optimization problems with respect to general domination sets by using a well-known nonlinear scalarization functional with uniform level sets (called Gerstewitz’ functional in the literature). The primary objective of this work is to establish revised formulas for basic and singular subdifferentials of … Read more

    Inexact restoration with subsampled trust-region methods for finite-sum minimization

  • Stefania Bellavia
  • Nataša Krejić
  • Benedetta Morini
    • Categories Unconstrained Optimization Tags , , , ,

    Convex and nonconvex finite-sum minimization arises in many scientific computing and machine learning applications. Recently, first-order and second-order methods where objective functions, gradients and Hessians are approximated by randomly sampling components of the sum have received great attention. We propose a new trust-region method which employs suitable approximations of the objective function, gradient and Hessian … Read more

    Quasi-Newton Methods for Deep Learning: Forget the Past, Just Sample

  • Albert S. Berahas
  • Majid Jahani
  • Martin Takac
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    We present two sampled quasi-Newton methods: sampled LBFGS and sampled LSR1. Contrary to the classical variants of these methods that sequentially build (inverse) Hessian approximations as the optimization progresses, our proposed methods sample points randomly around the current iterate to produce these approximations. As a result, the approximations constructed make use of more reliable (recent … Read more

    A study of rank-one sets with linear side constraints and application to the pooling problem

  • Santanu S. Dey
  • Burak Kocuk
  • Asteroide Santana
    • Categories Applications - Science and Engineering, Global Optimization

    We study sets defined as the intersection of a rank-1 constraint with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-1 set is polyhedral or second-order cone representable. In all these cases, we also show that a linear objective can be … Read more

    Active-set Newton methods and partial smoothness

  • Adrian Lewis
  • Calvin Wylie
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    Diverse optimization algorithms correctly identify, in finite time, intrinsic constraints that must be active at optimality. Analogous behavior extends beyond optimization to systems involving partly smooth operators, and in particular to variational inequalities over partly smooth sets. As in classical nonlinear programming, such active-set structure underlies the design of accelerated local algorithms of Newton type. … Read more

    Chance-Constrained Bin Packing Problem with an Application to Operating Room Planning

  • Jinlin Li
  • Sanjay Mehrotra
  • Shanshan Wang
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    We study the chance-constrained bin packing problem, with an application to hospital operating room planning. The bin packing problem allocates items of random size that follow a discrete distribution to a set of bins with limited capacity, while minimizing the total cost. The bin capacity constraints are satisfied with a given probability. We investigate a … Read more