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

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

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

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

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

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

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

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

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

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

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