Seminar Monday September 21, 13.30-14.30, Room 3721, Lindstedtsvägen 25

Active set identification for linearly constrained minimization without explicit derivatives

Professor Virginia Torczon
College of William & Mary, Williamsburg, Virginia, USA

We consider active set identification for linearly constrained optimization problems in the absence of explicit information about the derivative of the objective function. We begin by presenting some general results on active set identification that are not tied to any particular algorithm. These general results are sufficiently strong that, given a sequence of iterates converging to a Karush-Kuhn-Tucker point, it is possible to identify binding constraints for which there are nonzero multipliers. We then focus on generating set search methods, a class of derivative-free direct search methods. We discuss why these general results, which are posed in terms of the direction of steepest descent, apply to generating set search, even though these methods do not have explicit recourse to derivatives. Nevertheless, there is a clearly identifiable subsequence of iterations at which we can reliably estimate the set of constraints that are binding at a solution. We discuss how active set estimation can be used to accelerate generating set search methods and illustrate the appreciable improvement that can result using several examples from the CUTEr test suite. We also introduce two algorithmic refinements for generating set search methods.

The first expands the subsequence of iterations at which we can make inferences about stationarity. The second is a more flexible step acceptance criterion.


This is joint work with Robert Michael Lewis.