Tutte seminar - Dominique Orban

Degeneracy in Continuous Optimization

Abstract:

Over the past two decades, interior-point methods for smooth problems have emerged in the optimization community as the de-facto standard for the efficient solution of large-scale linear, convex, and nonconvex optimization problems. Not only are those methods robust and scalable, they turn out to be equally well suited, with little modification, to so-called degenerate problems. In this talk, we review various aspects of degeneracy in nonlinear optimization, their origin, their effects on the problem, the algorithm, and the linear algebra at the core of interior-point methods, as well as some remedies that can be put in place.