Friday, July 17

MS67
Interior-Point Methods and Convex Programming (Part I of II)

10:30 AM-12:30 PM
Room: Sidney Smith 1069

Since the publication of Karmarkar's paper in 1984, our view of how to solve optimization problems has changed dramatically. In particular, there has been great success in both theoretical complexity analysis and practical experience with solving large-scale linear programs using the new primal-dual interior-point approaches.

Much of the success for the linear case has followed through to the convex programming case, e.g. for semidefinite programming and for quadratic constrained quadratic convex programs. However, many questions such as exploiting sparsity remain open. In the first part of this minisymposium, the speakers will focus on Interior-Point Methods and Convex Programs.

Although the success for interior-point methods has not yet followed through to the general nonlinear programming case, there are many promising steps in this direction. Many difficulties have arisen, e.g. line search problems, scaling, sparsity considerations, ill-conditioning. The speakers in the second part of this minisymposium will focus on Interior-Point Methods and General Nonlinear Programs.

See Part II, MS76.

10:30 Search Directions in Interior-Point Methods for Convex Programming

Michael J. Todd , Cornell University

11:00 Primal-Dual Interior-Point Algorithms for Semidefinite Programming and Extensions

Levent Tuncel, University of Waterloo, Canada; and Osman Güler, University of Maryland, Baltimore County

11:30 Geometric Properties and Complexity Implications of Some Condition Numbers for Linear and Convex Optimization

Robert M. Freund, Massachusetts Institute of Technology; and Jorge Vera, University of Chile, Santiago, Chile

12:00 An Interior-Point Method for the Euclidean Distance Matrix Completion Problem

Abdo Alfakih, University of Waterloo, Canada; and Henry Wolkowicz, Organizer