Department
Home Page
About Us:
• Contact Info.
• Faculty
• Staff
• Teaching Assistants
Academic Program:
• Admission
• Undergraduate
• Graduate
• Certificates
Courses:
• Course Description
• Class Web Pages
• Class Syllabi
Research:
• Colloquium
• Interdisciplinary Seminar
• Seminars
• Steve Goldman Lectures in Mathematical Physics
Links:
| • Completing Online GEP Courses |
| • Best Jobs |
| • Newsletter |
| • Math Lab |
| •Math Placement Test |
| • Careers |
| • American Mathematical Society |
| • Mathematical Association of America |
03/28/06 Colloquium
Dr. Florian Potra
University of Maryland and National Institute
of Standards and Technology
University of Maryland and National Institute
of Standards and Technology
Polynomial Complexity and Superlinear Convergence of Interior Point Methods for Mathematical Programming
Abstract: The modern era of interior-point methods dates to 1984, when Karmarkar proposed his algorithm for linear programming. In the years since then, algorithms and software for linear programming have become quite sophisticated, while extensions to more general classes of problems, such as convex quadratic programming, semidefinite programming, and nonconvex and nonlinear problems, have reached varying levels of maturity. The first part of the talk will review the most important results in interior-point methods obtained over the past two decades, emphasizing the distinction between computational complexity and superlinear convergence. While the work on computational complexity has shown that interior-point methods can solve in polynomial time some important mathematical programming problems, superlinear convergence results explain why the practical performance of interior-point methods is better than predicted by the computational complexity results. The second part of the talk will concentrate on some recent results obtained by the author and his collaborators.