Reduced Direction Search Methods

Note that the minimum found along the gradient projection is very far from and worse than the one obtained with the KKT direction. Since both the points are feasible, the one achieved with the KKT direction is the solution. The point achieved with the gradient projection lies on the bottom of a relatively narrow valley and would struggle to find the solution if only the gradient directions were adopted. 

In sparse large-scale problems, it may be computationally onerous to project a ( ) vector using either (13.41) or LQ factorization. 

In this case, it is opportune to use the null space of constraints rather than projecting the search vector on the constraints. This will be shown in the following section. 

In the BzzConstrainedMinimization class the LQ factorization is used in small-medium dense problems. 

These methods exploit the active constraints equations to reduce the dimensions of the problem. The first of these methods was proposed by Wolfe (1963) where the search direction adopted is the function gradient and the constraints are linear. To introduce this family of methods, it is opportune to consider this simple problem  

---

Projection or Reduced Direction Search Methods for Bound-Constrained Problems 1407... 

The proposed method can be called the Projection Direction Search Method or Reduced Direction Search Method since whatever search direction is selected, the projection on a bound constraint corresponds to the removal of such a constraint from the same direction. 

Chapter 13 illustrates the problem of constrained optimization by introducing the active set methods. Successive linear programming (SLP), projection, reduced direction search, SQP methods are described, implemented, and adopted to solve several practical examples of constrained linear/nonlinear optimization, including the solution of the Maratos effect. 

In this chapter we described and illustrated only a few unidimensional search methods. Refer to Luenberger (1984), Bazarra et al. (1993), or Nash and Sofer (1996) for many others. Naturally, you can ask which unidimensional search method is best to use, most robust, most efficient, and so on. Unfortunately, the various algorithms are problem-dependent even if used alone, and if used as subroutines in optimization codes, also depend on how well they mesh with the particular code. Most codes simply take one or a few steps in the search direction, or in more than one direction, with no requirement for accuracy—only that fix) be reduced by a sufficient amount. 

Voigt CA, Mayo SL, Arnold FH, Wang ZG (2001) Computational method to reduce the search space for directed protein evolution. Proc Natl Acad Sci USA 98 3778-3783... 

As noted in the example above, the reduced-step Newton method can fail when the search direction is nearly perpendicular to the steepest descent direction so that only very short steps are taken. This problem originates from the fact that the direction of the frill Newton step is always accepted we rednce only the magnitude of the step to attain rednction of... 

Once a direction is estabflshed for the next poiat ia the space of the variables of optimization (whether by random search, by systematic evaluation of gradients, or by any other methods of making perturbations), it is possible to take a jump ia the directioa of the improvement much greater than the size of the perturbations. This could speed up the process of finding the optimum and reduce computer time. If such a leap is successful, the next iteration may take a bigger leap and so on, until the improvement stops. Then one could reverse the direction and decrease the size of the step until the optimum is found. 

Line search. The oldest and simplest method of calculating a to obtain Ax is via a unidimensional line search. In a given direction that reduces/(x), take a step, or a sequence of steps yielding an overall step, that reduces/(x) to some acceptable degree. This operation can be carried out by any of the one-dimensional search... 

---