Fast infeasibility detection in nonlinear optimization

Monday, November 17, 2008 - 2:00pm - 2:45pm
EE/CS 3-180
Jorge Nocedal (Northwestern University)
An important issue in branch and bound methods for mixed integer nonlinear programming is the fast detection of infeasibility. This topic has not received sufficient attention and the methods developed for nonlinear programming often required a large number of iterations before a declaration of infeasibility can be made.

The focus of this talk is to address the need for optimization
algorithms that can both efficiently solve feasible problems and rapidly detect when a given problem instance is infeasible. One way to address these concerns is to employ a switch in an algorithm to decide whether
the current iteration should seek a solution of the nonlinear program
or, in contrast, to solely minimize some measure of feasibility. A challenge with such an approach lies in the difficulty of designing effective criteria for determining when such a switch should be made.

We propose an alternative approach involving a single optimization
strategy, and show that it is effective for finding an optimal feasible solution (when one exists) or finding the minimizer of a feasibility measure (when no feasible point exists). Our algorithm is an active-set method that uses the penalty parameter to emphasize optimality over
infeasibility detection, or vice versa. We establish superlinear convergence results and discuss numerical experiments that demonstrate
the advantages of our approach.
MSC Code: