Extremal Probability Bounds in Combinatorial Optimization

In this paper, we compute the tightest possible bounds on the probability that the optimal value of a combinatorial optimization problem in maximization form with a random objective exceeds a given number, assuming only knowledge of the marginal distributions of the objective coefficient vector. The bounds are “extremal” since they are valid across all joint … Read more

Assortment Optimization under Heteroscedastic Data

We study assortment problems under the Marginal Exponential Model (MEM) with deterministic demand. We show that optimal solutions to such assortment problems can be efficiently determined under some mild conditions, and provide a simple approach that finds near optimal solutions when these conditions fail. Furthermore, we improve the existing MEM parameter estimation method given by … Read more

Distributionally Robust Markovian Traffic Equilibrium

Stochastic user equilibrium models are fundamental to the analysis of transportation systems. Such models are typically developed under the assumption of route based choice models for the users. A class of link based models under a Markovian assumption on the route choice behavior of the users has been proposed to deal with the drawbacks of … Read more

Distributionally Robust Project Crashing with Partial or No Correlation Information

Crashing is a method for optimally shortening the project makespan by reducing the time of one or more activities in a project network by allocating resources to it. Activity durations are however uncertain and techniques in stochastic optimization, robust optimization and distributionally robust optimization have been developed to tackle this problem. In this paper, we … Read more

Fast Algorithms for the Minimum Volume Estimator

The MVE estimator is an important tool in robust regression and outlier detection in statistics. We develop fast and efficient algorithms for the MVE estimator problem and discuss how they can be implemented efficiently. The novelty of our approach stems from the recent developments in the first-order algorithms for solving the related Minimum Volume Enclosing … Read more

A First-Order Algorithm for the A-Optimal Experimental Design Problem: A Mathematical Programming Approach

We develop and analyse a first-order algorithm for the A-optimal experimental design problem. The problem is first presented as a special case of a parametric family of optimal design problems for which duality results and optimality conditions are given. Then, two first-order (Frank-Wolfe type) algorithms are presented, accompanied by a detailed time-complexity analysis of the … Read more

A Convex Optimization Approach for Computing Correlated Choice Probabilities with Many Alternatives

A popular discrete choice model that incorporates correlation information is the Multinomial Probit (MNP) model where the random utilities of the alternatives are chosen from a multivariate normal distribution. Computing the choice probabilities is challenging in the MNP model when the number of alternatives is large and simulation is used to approximate the choice probabilities. … Read more

A Modified Frank-Wolfe Algorithm for Computing Minimum-Area Enclosing Ellipsoidal Cylinders: Theory and Algorithms

We study a first-order method to find the minimum cross-sectional area ellipsoidal cylinder containing a finite set of points. This problem arises in optimal design in statistics when one is interested in a subset of the parameters. We provide convex formulations of this problem and its dual, and analyze a method based on the Frank-Wolfe … Read more

Identification and Elimination of Interior Points for the Minimum Enclosing Ball Problem

Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of $\cA$. In this note, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in $\cA$ that are guaranteed to lie … Read more

Linear convergence of a modified Frank-Wolfe algorithm for computing minimum volume ellipsoids

We show the linear convergence of a simple first-order algorithm for the minimum-volume enclosing ellipsoid problem and its dual, the D-optimal design problem of statistics. Computational tests confirm the attractive features of this method. Citation Optimization Methods and Software 23 (2008), 5–19. Article Download View Linear convergence of a modified Frank-Wolfe algorithm for computing minimum … Read more