18. Filter Methods

The filter methods developed by Fletcher and Leyffer (2002) as a new technique for globalization, the nonlinear optimization algorithms, are described in this chapter. The idea is motivated by the aim of avoiding the need to choose penalty parameters in penalty functions or augmented Lagrangan functions and their variants. Let us consider the nonlinear optimization problems with inequality constraints:subject towhere the objective function f : ℝ ⁿ  → ℝ and the functions c _i  : ℝ ⁿ  → ℝ i = 1 ,  …  , m defining the constraints are supposed to be twice continuously differentiable. The methods for solving this problem are based on the Newton method. Given an estimate x _k of the solution x ^∗ of (18.1), a linear or quadratic approximation of (18.1) is solved, thus obtaining a new estimate x _k + 1 which we hope to be better as the previous one. Near a solution, this approach is guaranteed to be convergent. However, far away from the solution, the sequence {x _k } generated by the above procedure may not converge. In this situation, away from the solution, the idea is to use the Newton method again but considering the penalty or merit functions. The penalty functions or the merit functions are a combination of the objective function and a measure of constraints violation such as h(x) = ‖c(x)⁺‖_∞, where c(x) = [c ₁(x),  … , c _m (x)]^T and \( {c}_i^{+}=\max \left\{0,{c}_i\right\} \). A very well-known example is the l ₁ exact penalty function p(x, σ) = f(x) + σh(x), where σ > 0 is the penalty parameter. If σ is sufficiently large, then this penalty function can be minimized in an iterative procedure to ensure progress to the solution.