The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent

The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of … Read more

Convex Quadratic Relaxations for Mixed-Integer Nonlinear Programs in Power Systems

This paper presents a set of new convex quadratic relaxations for nonlinear and mixed-integer nonlinear programs arising in power systems. The considered models are motivated by hybrid discrete/continuous applications where existing approximations do not provide optimality guarantees. The new relaxations offer computational efficiency along with minimal optimality gaps, providing an interesting alternative to state-of-the-art semi-definite … Read more

Ray Projection for Optimizing Polytopes with Prohibitively Many Constraints in Set-Covering Column Generation

A recurrent task in mathematical programming requires optimizing polytopes with prohibitively-many constraints, e.g., the primal polytope in cutting-plane methods or the dual polytope in Column Generation (CG). This paper is devoted to the ray projection technique for optimizing such polytopes: start from a feasible solution and advance on a given ray direction until intersecting a … Read more

Optimization Models for Differentiating Quality of Service Levels in Probabilistic Network Capacity Design Problems

This paper develops various chance-constrained models for optimizing the probabilistic network design problem (PNDP), where we differentiate the quality of service (QoS) and measure the related network performance under uncertain demand. The upper level problem of PNDP designs continuous/discrete link capacities shared by multi-commodity flows, and the lower level problem differentiates the corresponding QoS for … Read more

Optimization Methods for Disease Prevention and Epidemic Control

This paper investigates problems of disease prevention and epidemic control (DPEC), in which we optimize two sets of decisions: (i) vaccinating individuals and (ii) closing locations, given respective budgets with the goal of minimizing the expected number of infected individuals after intervention. The spread of diseases is inherently stochastic due to the uncertainty about disease … Read more

On Solving a Hard Quadratic 3-Dimensional Assignment Problem

We address the exact solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to proven optimality, from the choice of an appropriate mixed-integer programming formulation, to cutting planes and symmetry handling. Using these techniques … Read more

Quantitative Characterizations of Regularity Properties of Collections of Sets

Several primal and dual characterizations of regularity properties of collections of sets in normed linear spaces are discussed. Relationships between regularity properties of collections of sets and those of set-valued mappings are provided. Citation JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS (2015) 164:41–67 Article Download View Quantitative Characterizations of Regularity Properties of Collections of Sets

Complementarity Formulations of l0-norm Optimization Problems

In a number of application areas, it is desirable to obtain sparse solutions. Minimizing the number of nonzeroes of the solution (its l0-norm) is a difficult nonconvex optimization problem, and is often approximated by the convex problem of minimizing the l1-norm. In contrast, we consider exact formulations as mathematical programs with complementarity constraints and their … Read more

Smooth minimization of nonsmooth functions with parallel coordinate descent methods

We study the performance of a family of randomized parallel coordinate descent methods for minimizing the sum of a nonsmooth and separable convex functions. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss (“AdaBoost problem”). We assume the input data defining the loss function is contained … Read more

Two-Stage Decomposition Algorithms for Single Product Maritime Inventory Routing

We present two decomposition algorithms for single product deep-sea maritime inventory routing problems (MIRPs) that possess a core substructure common in many real-world applications. The problem involves routing vessels, each belonging to a particular vessel class, between loading and discharging ports, each belonging to a particular region. Our algorithms iteratively solve a MIRP by zooming … Read more