Month: July 2019

Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints

  • Stephen Wright
  • Yue Xie
    • Categories Constrained Nonlinear Optimization

    We analyze worst-case complexity of a Proximal augmented Lagrangian (Proximal AL) framework for nonconvex optimization with nonlinear equality constraints. When an approximate first-order (second-order) optimal point is obtained in the subproblem, an $\epsilon$ first-order (second-order) optimal point for the original problem can be guaranteed within $\mathcal{O}(1/ \epsilon^{2 – \eta})$ outer iterations (where $\eta$ is a … Read more

    Random projections for quadratic programs

  • Claudia D'Ambrosio
  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories Quadratic Programming Tags , , , ,

    Random projections map a set of points in a high dimensional space to a lower dimen- sional one while approximately preserving all pairwise Euclidean distances. While random projections are usually applied to numerical data, we show they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving … Read more

    Robust stochastic optimization with the proximal point method

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. In this work, we show that a wide class of such algorithms on strongly convex problems can be augmented with sub-exponential confidence bounds at an overhead cost that is only … Read more

    Logic-based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling

  • Dionne M. Aleman
  • Merve Bodur
  • Cheng Guo
  • David R. Urbach
    • Categories Cutting Plane Approaches, Scheduling, Stochastic Programming

    The distributed operating room (OR) scheduling problem aims to find an assignment of surgeries to ORs across collaborating hospitals that share their waiting lists and ORs. We propose a stochastic extension of this problem where surgery durations are considered to be uncertain. In order to obtain solutions for the challenging stochastic model, we use sample … Read more

    On Inexact Solution of Auxiliary Problems in Tensor Methods for Convex Optimization

  • Geovani Nunes Grapiglia
  • Yurii Nesterov
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    In this paper we study the auxiliary problems that appear in p-order tensor methods for unconstrained minimization of convex functions with \nu-Holder continuous pth derivatives. This type of auxiliary problems corresponds to the minimization of a (p+\nu)-order regularization of the pth order Taylor approximation of the objective. For the case p=3, we consider the use … Read more

    A conservative convergent solution for continuously distributed two-stage stochastic optimization problems

  • Carlos Gamboa
  • Alexandre Street
  • Davi Valladão
    • Categories Stochastic Programming Tags , ,

    Two-stage stochastic programming is a mathematical framework widely used in real- life applications such as power system operation planning, supply chains, logistics, inventory management, and financial planning. Since most of these problems cannot be solved analytically, decision makers make use of numerical methods to obtain a near-optimal solution. Some applica- tions rely on the implementation … Read more

    An Exact Solution Approach for the Inventory Routing Problem with Time Windows

  • Esra Koca
  • Gizem Ozbaygin
  • Hande Yaman
    • Categories Applications - OR and Management Sciences, Production and Logistics, Transportation

    The inventory routing problem (IRP) is an integrated inventory and transportation planning problem that jointly determines the replenishment schedules for a given set of retailers, and the routing decisions for a supplier that distributes a product to the retailers over a finite planning horizon typically consisting of multiple periods. In the classical IRP, retailers are … Read more

    Constraint Programming Approaches for the Discretizable Molecular Distance Geometry Problem

  • Merve Bodur
  • Moira MacNeil
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

    The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so-called discretization assumptions allow to discretize the search space of DGP instances. In this paper, we focus on a key subclass of DGP, namely the Discretizable Molecular … Read more

    Navigating Concave Regions in Continuous Facility Location Problems

  • Michael Beacher
  • Md. Noor-E-Alam
  • Ma Dinghao
  • Ruilin Ouyang
    • Categories Applications - OR and Management Sciences Tags , , ,

    In prior literature regarding facility location problems, there has been little explicit acknowledgement of problems arising from concave (non-convex) regions. By extension, there is a distinct deficiency in existing methods to deal with them outside of problem relaxation. In this work, we present a novel algorithm for finding representative regional center-points, referred to as “Concave … Read more

    Dual sufficient characterizations of transversality properties

  • Nguyen Duy Cuong
  • Alexander Y. Kruger
    • Categories Convex and Nonsmooth Optimization

    This paper continues the study of ‘good arrangements’ of collections of sets near a point in their intersection. Our aim is to develop a general scheme for quantitative analysis of several transversality properties within the same framework. We consider a general nonlinear setting and establish dual space (subdifferential and normal cone) sufficient characterizations of transversality … Read more