Tuesday, May 21
8:00-10:00 AM
Saanich 1

MS16
Condition Numbers and Problem Complexity in Convex Programming (Part I of II)

There are many weaknesses in the traditional measure of problem complexity for linear programming based on the bitlength L of a binary encoding of a problem, not the least of which include the lack of extendibility of this measure to nonlinear optimization, the inability of this measure to adequately predict the difficulty in solving problems in practice, and the lack of connection between L and standard condition measures for solving linear equations. The subject of this minisymposium is recent research aimed at exploring the properties and prospects of some alternative ways of defining the "condition number" of an optimization problem. These alternatives are based on more intuitive and appealing notions of "conditioning" for convex optimization, and that are relevant both to the theory and the application of linear and nonlinear programming.

Organizer: Robert M. Freund
Massachusetts Institute of Technology

Convergence of an Interior Point Method for Linear Programming in Terms of the Condition Number of the Coefficient Matrix
Stephen Vavasis, Cornell University
Condition Measures and Properties of the Central Trajectory of a Linear Program
Manuel Nunez, Massachusetts Institute of Technology
Finite Precision Computation in Optimization: A Complexity Analysis Based on Ill-Posedness Measures
Jorge Vera, University of Chile, Chile
Perturbation Analysis of a Condition Number for Convex Systems
Sien Deng, Northern Illinois University

Registration | Hotel Information | Transportation | Speaker Index | Program Overview


LMH, 3/15/96