Hybrid Filter Methods for Nonlinear Optimization

Abstract

Globalization strategies used by algorithms to solve nonlinear constrained optimization problems must balance the oftentimes conflicting goals of reducing the objective function and satisfying the constraints. The use of merit functions and filters are two such popular strategies, both of which have their strengths and weaknesses. In particular, traditional filter methods require the use of a restoration phase that is designed to reduce infeasibility while ignoring the objective function. For this reason, there is often a significant decrease in performance when restoration is triggered.

In Chapter 3, we present a new filter method that addresses this main weakness of traditional filter methods. Specifically, we present a hybrid filter method that avoids a traditional restoration phase and instead employs a penalty mode that is built upon the l-1 penalty function; the penalty mode is entered when an iterate decreases both the penalty function and the constraint violation. Moreover, the algorithm uses the same search direction computation procedure during every iteration and uses local feasibility estimates that emerge during this procedure to define a new, improved, and adaptive margin (envelope) of the filter. Since we use the penalty function (a combination of the objective function and constraint violation) to define the search direction, our algorithm never ignores the objective function, a property that is not shared by traditional filter methods. Our algorithm thusly draws upon the strengths of both filter and penalty methods to form a novel hybrid approach that is robust and efficient. In particular, under common assumptions, we prove global convergence of our algorithm.

In Chapter 4, we present a nonmonotonic variant of the algorithm in Chapter 3. For this version of our method, we prove that it generates iterates that converge to a first-order solution from an arbitrary starting point, with a superlinear rate of convergence. We also present numerical results that validate the efficiency of our method.

Finally, in Chapter 5, we present a numerical study on the application of a recently developed bound-constrained quadratic optimization algorithm on the dual formulation of sparse large-scale strictly convex quadratic problems. Such problems are of particular interest since they arise as subproblems during every iteration of our new filter methods.