• The Continuous Optimization Seminar meets weekly on Wednesdays at 4:30 pm in the ORIE Seminar Room, Rhodes 253.
• For weekly reminders and updates, please subscribe to the mailing list by sending an email to optimization-l-request@cornell.edu with the word join in the body.
• For last year's seminar information, visit the 2007-2008 COS Page.
• If you'd like to give a talk or would like more information, please send an e-mail to leventhal*@*orie.*cornell.*edu (with the *'s removed).

Schedule 2008-2009:

• 2/12/2009, Michael Todd
  
• 2/25/2009, Adrian Lewis
  
• 3/11/2009, Dennis Leventhal
  
• 3/25/2009, Jeffrey Pang
  
• 4/8/2009, Selin Damla Ahipasaoglu
  
• 4/29/2009, Sasha Gutfraind
  

Spring 2009:

• 2/12/09: Michael Todd, School of Operations Research and Information Engineering, Cornell University
• Title: Certificates of (im)possibility.
  
• Note Special Time: Thursday, 4:00pm, Rhodes 253
  
  Abstract
  
  We consider various problems in number theory, geometry, algebra, and operations research from the viewpoint of providing short certificates of possibility or impossibility.

• 2/25/09: Adrian Lewis, School of Operations Research and Information Engineering, Cornell University
• Title: Semi-Algebraic Convex Optimization
  
  Abstract
  
  Concrete convex optimization problems are often "semi-algebraic": we seek to minimize a linear cost function c.x where the variable vector x must lie in one of several given sets, each defined by several polynomial inequalities. Semidefinite programming is an example. Assuming the sets are compact, for almost all cost vectors c this problem has a unique solution, which furthermore varies smoothly as we perturb c.

• 3/11/09: Dennis Leventhal, School of Operations Research and Information Engineering, Cornell University
• Title: Randomized Algorithms: Convergence and Conditioning
  
  Abstract
  
  Conditioning issues often affect both the computational performance and convergence analysis of iterative algorithms. In that sense, we examine randomized variants of two classical algorithms--coordinate descent for linear equations and iterated projections for linear equality and inequality systems--and show that, under appropriate probability distributions, linear rates of convergence can be obtained in terms of natural linear-algebraic condition measures for the underlying problems. Generalizations to convex feasiblity problems, via iterated projections, and monotone inclusion problems, via the proximal point method, are then considered under metric regularity assumptions.

• 3/25/09: Jeffrey Pang, Center for Applied Mathematics, Cornell University
  
• Title: Fast Methods for Mountain Passes, and generic continuity of semi-algebraic set-valued maps
  
  Abstract
  
  In the first part, we describe an algorithm to compute the "mountain pass" between two given points: a connecting path along which the maximum value is minimized. We describe an algorithm that maintains lower bounds on the optimal value by keeping the two points in separate level set components. This algorithm converges, even in the nonsmooth case, and converges superlinearly locally in the smooth finite-dimensional case. Applications include computational chemistry and partial differential equations. We mention a few ideas in the multidimensional mountain pass. In the second part, I will illustrate how recent results in a semi-algebraic Sard's theorem and metric regularity lead to a result on the generic continuity of semi-algebraic set-valued maps, and the implications in semi-algebraic variational analysis.

• 4/8/2009: Selin Damla Ahipasaoglu, School of Operations Research and Information Engineering, Cornell University
• Title: Identification and Elimination of Interior Points for the Minimum Enclosing Ball Problem
  
  Abstract:
  
  Given a set of points A, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of A. In this talk, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in A that are guaranteed to lie in the interior of the minimum-radius ball enclosing A. Our computational results reveal that incorporating this procedure into the two recent algorithms proposed by Yildrim leads to significant speed-ups in running times especially for randomly generated large-scale problems. We also illustrate that the extra overhead due to the elimination procedure remains at an acceptable level for spherical or almost spherical input sets.

• 4/29/2009: Sasha Gutfraind, Center for Applied Mathematics, Cornell University
• Title: A Markovian Approach to Network Interdiction
  
  Abstract:
  
  The interdiction problem arises in a variety of areas including military logistics, infectious disease control, and counter-terrorism. In the typical formulation of network interdiction, the task of the interdictor is to find a set of edges in a weighted network such that the removal of those edges would maximally increase the cost to an evader of traveling on a path through the network.
  
  Our work is motivated by cases in which the evader has incomplete information about the network or lacks planning time or computational power, e.g. when authorities set up roadblocks to catch bank robbers, the criminals do not know all the roadblock locations or the best path to use for their escape.
  
  We introduce a model of network interdiction in which the motion of one or more evaders is described by Markov processes and the evaders are assumed not to react to interdiction decisions. The interdiction objective is to find an edge set of size B, that maximizes the probability of capturing the evaders.
  
  We prove that similar to the standard least-cost formulation for deterministic motion this interdiction problem is also NP-hard. But unlike that problem our interdiction problem is submodular and the optimal solution can be approximated within 1-1/e using a greedy algorithm. Additionally, we exploit submodularity through a priority evaluation strategy that eliminates the linear complexity scaling in the number of network edges and speeds up the solution by orders of magnitude. Taken together the results bring closer the goal of finding realistic solutions to the interdiction problem on global-scale networks.

Fall 2008:

• The Continuous Optimization Seminar is postponed for Fall 2008 Semester. It will return for Spring 2009.
• 9/10/08: Brief Organizational Meeting