An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two … Read more

On max-k-sums

The max-$k$-sum of a set of real scalars is the maximum sum of a subset of size $k$, or alternatively the sum of the $k$ largest elements. We study two extensions: First, we show how to obtain smooth approximations to functions that are pointwise max-$k$-sums of smooth functions. Second, we discuss how the max-$k$-sum can … Read more

An improved Kalai-Kleitman bound for the diameter of a polyhedron

Kalai and Kleitman established the bound $n^{\log(d) + 2}$ for the diameter of a $d$-dimensional polyhedron with $n$ facets. Here we improve the bound slightly to $(n-d)^{\log(d)}$. Citation School of Operations Research and Information Engineering, Cornell University, Ithaca NY, USA, February 2014 Article Download View An improved Kalai-Kleitman bound for the diameter of a polyhedron

Computing a Cournot Equilibrium in Integers

We give an efficient algorithm for computing a Cournot equilibrium when the producers are confined to integers, the inverse demand function is linear, and costs are quadratic. The method also establishes existence, which follows in much more generality because the problem can be modelled as a potential game. Citation School of Operations Research and Information … Read more

Optimization of Demand Response Through Peak Shaving

We consider a model in which a consumer of a resource over several periods must pay a per unit charge for the resource as well as a peak charge. The consumer has the ability to reduce his consumption in any period at some given cost, subject to a constraint on the total amount of reduction … Read more

A Robust Robust Optimization Result

We study the loss in objective value when an inaccurate objective is optimized instead of the true one, and show that “on average” this loss is very small, for an arbitrary compact feasible region. Citation Technical Report 1479, School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853, April 2011 Article Download View … Read more

On the implementation and usage of SDPT3 — a Matlab software package for semidefinite-quadratic-linear programming, version 4.0

This software is designed to solve primal and dual semidefinite-quadratic-linear conic programming problems (known as SQLP problems) whose constraint cone is a product of semidefinite cones, second-order cones, nonnegative orthants and Euclidean spaces, and whose objective function is the sum of linear functions and log-barrier terms associated with the constraint cones. This includes the special … 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

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

On Khachiyan’s Algorithm for the Computation of Minimum Volume Enclosing Ellipsoids

Given $\cA := \{a^1,\ldots,a^m\} \subset \R^d$ whose affine hull is $\R^d$, we study the problems of computing an approximate rounding of the convex hull of $\cA$ and an approximation to the minimum volume enclosing ellipsoid of $\cA$. In the case of centrally symmetric sets, we first establish that Khachiyan’s barycentric coordinate descent (BCD) method is … Read more