Wednesday, October 10 2007

Adrian Lewis
Cornell University, School of Operations Research and Information Engineering

Alternating Projections Revisited

Von Neumann's method of alternating projections approximates a point in the intersection of two convex sets by iteratively projecting onto one set and then the other. This idea's simplicity and intuitive appeal has prompted diverse computational experiments where, despite nonconvexity, the projection subproblems may still be easy. Examples include image processing and low-order control design. I will outline the convergence theory, and sketch how the speed of convergence is related to some central ideas in variational analysis.

This is joint work with D.R. Luke and J. Malick.

Wednesday, October 17 2007

Stefan Wild
Cornell University, School of Operations Research and Information Engineering

Geometry of Data Points: A Speed Bump for the Greedy Optimizer

A standard trick in nonlinear programming is to solve a simple subproblem whose solution is a step toward solving the difficult problem of interest. Usually this involves building a model which locally approximates the original function. Of interest to us are models built by interpolating the function on a set of scattered data points. Approximation guarantees are heavily tied to the geometry of these points and algorithms must balance maintaining good geometry with making good progress overall. I'll provide some background on this problem and then show lots of pictures.

This is joint work with Christine Shoemaker and Jorge Moré.

Wednesday, October 24 2007

Jeffrey Pang
Cornell University, Center for Applied Mathematics

Variational Analysis of Robust Regularization

In continuous optimization, a solution can fail to be robust due to inaccuracies in measurement and implementation. To address robustness in a minimization problem, we consider the maximum of a function over a bounded set and its translations over the domain. This method has regularizing properties, especially for semi-algebraic functions. The relationship between calmness and Lipschitz continuity in Variational Analysis generalizes robust regularization to set-valued maps as well.

This is joint work with Adrian Lewis.

Wednesday, October 31 2007

Samuel Ehrlichman
Cornell University, School of Operations Research and Information Engineering

Univariate Stochastic Root-finding for Monotone, Convex Functions

We study the one-dimensional root finding problem for increasing convex functions. We give algorithms for both exact, and inexact (stochastic), function evaluations. For the stochastic case, we supply a probabilistic convergence guarantee in the spirit of selection-of-the-best methods. The algorithm's worst-case performance bound is an improvement upon that of its close cousin, stochastic binary search, by a constant factor.

This is joint work with Shane Henderson.

Wednesday, November 7 2007

Eric Friedman
Cornell University, School of Operations Research and Information Engineering

Finding a Simple Polytope from its Graph: Connections to Linear Programming Complexity

This talk will ostensibly focus on recent work on the complexity of finding a simple polytope from its graph; however, much of the talk will be on a combinatorial approach to understanding the computational complexity of simplex algorithm for linear programming, a topic of more general interest. At the end, I will describe the connections between the two.

Wednesday, November 14 2007

Dennis Leventhal
Cornell University, School of Operations Research and Information Engineering

Randomization Methods in Smooth Optimization: "Derivative-Light" Methods

Probabilistic ideas appear in a variety of areas in continuous optimization, but haven't yet been competitive when incorporated in directional search-based methods. In this talk, we'll examine some randomization techniques for smooth optimization and develop a method for using randomization to cheaply estimate Hessian information. Further, we'll see this leads to a variety of algorithms that are competitive with some of the classical, derivative-based methods, but with a reduced reliance on derivative information at each iteration, leading to so-called "Derivative-Light" methods.

This is joint work with Adrian Lewis.

Wednesday, November 28 2007

Huseyin Topaloglu
Cornell University, School of Operations Research and Information Engineering

Engineering applications of Martingale convergence theorems

In this talk, I will review some interesting applications of martingale convergence theorems. Our particular focus will be on using these theorems to solve "real-world" stochastic optimization problems. I will describe when the general-purpose convergence results become useful, and when they fail. I will present applications on logistics, revenue management and equipment replacement problems.

This is joint work with Sumit Kunnumkal.

Wednesday, February 13 2008

Mike Todd
Cornell University, School of Operations Research and Information Engineering

Roundness and centrality for convex bodies

This informal talk is concerned with measures of roundness and centrality for convex bodies. We'll describe some results of Loewner-John, Belloni-Freund, Nesterov, and Todd.

Wednesday, February 27 2008

Selin Damla Ahipasaoglu
Cornell University, School of Operations Research and Information Engineering

The Minimum Area Enclosing Ellipsoidal Cylinder Problem

Given an arbitrary set A in n-dimensional Euclidean space and an integer k, we are interested in finding an ellipsoidal cylinder, centered at the origin, such that its intersection with the subspace {y : y(k+1)=...=y(n)=0} has minimum area. This problem is referred to as the Minimum-Area Enclosing Ellipsoidal Cylinder (MAEC) problem. We show that the MAEC and its dual can be written as convex problems, and present a Frank-Wolfe type algorithm with away steps. We present computational results and discuss local and global convergence properties of the algorithm.

Wednesday, March 5 2008

A. Kevin Tang
Cornell University, School of Electrical and Computer Engineering

Internet Congestion Control: From Optimization to Game Theory

Given the important role the Internet plays in our society, a fundamental understanding of how this critical resource is managed becomes crucial. In this talk, we focus on Internet congestion control. We will first provide a brief introduction to its basic mechanism and the current theory. We will then discuss two motivating examples to show that the theory does not work in networks with flows that use different congestion signals to regulate their rates. A general framework is developed for such networks. It is conceptually a generalization of the existing network utility maximization (NUM) theory for homogeneous congestion control. Instead of a convex optimization characterization in NUM, a game with multiple convex optimizations is formulated to characterize equilibria in such a network. We also provide some basic properties of the game and point out some possible future directions along this line.

Wednesday, March 12 2008

Paat Rusmevichientong
Cornell University, School of Operations Research and Information Engineering

Dynamic Assortment Optimization with a Multinomial Logit Choice Model

The paper considers a stylized model of a dynamic assortment optimization problem faced by a retailer. Given the limited store capacity, the retailer must decide which products to offer to customers to maximize the expected profit. We assume that each customer chooses the product that maximizes her utility and consider the multinomial logit choice model to represent demand. The retailer, however, does not know the demand for each product. She can learn the demand distribution by offering different product assortments, observing resulting purchases, and inferring the demand distribution from past sales and assortment decisions. We present an adaptive algorithm for joint parameter estimation and assortment optimization. To evaluate our proposed policy, we define a benchmark profit as the maximum expected profit that the retailer can earn if she knows the demand distribution in advance. We show that the running average expected profit generated by our algorithm converges to the benchmark profit and establish its convergence rate. Numerical experiments based on sales data from an online retailer indicate that our policy performs well.

Joint work with Max Shen (UC Berkeley) and David Shmoys (Cornell)

Wednesday, April 9 2008

Spyridon Schismenons
Cornell University, School of Operations Research and Information Engineering

Low-Rank Approximations in Optimization Problems

In practice, for large optimization problems that are intractable, an approximation of the constraints has to be used. Motivated by a particular optimization problem, we study the effect of approximations in second-order cone programs (SOCP's). For a specific class of SOCP's, we study two approximation methods, one based on the SVD and one based on a recently proposed randomized algorithm. We give results about the relationship between the optimal values of the original and the approximating problem and compare the two methods. We also provide asymptotic results, when the dimension of the problem tends to infinity.

This is joint work with Shane Henderson and Adrian Lewis.

Monday-Friday, April 21-25 2008

Robert Bixby
Rice University

Fulkerson Lecture Series

News Release, More Information

Wednesday, April 30 2008

Tamon Stephen
Department of Mathematics, Simon Fraser University

The Colourful Feasibility Problem

A colourful version of the linear programming feasibility problem is to find a feasible basis that respects a given colouring (partition) of the vertices. This problem was presented by Barany and Onn in 1997, it is still not known if a polynomial time algorithm exists. We compare the methods introduced by Barany and Onn with new methods. We perform benchmarking on generic and ill-conditioned problems, as well as recently introduced highly structured problems. We show that some algorithms can lead to cycling or slow convergence, but we provide numerical experiments which show that others perform much better than predicted by complexity arguments. We conclude that an effective method in practice is a proposed multi-update algorithm.

This is joint work with A. Deza, S. Huang and T. Terlaky.