There are many weaknesses in the traditional measure of problem complexity for
linear programming based on the bit length 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
LMH, 3/15/96