Search vector

At the start of the jth iteration we denote by k1- the current estimate of the parameters. The j,h iteration consists of the computation of a search vector Ako l) from which we obtain the new estimate krjl,)according to the following equation... 

In this method the search vector is the negative of the gradient of the objective function and is given by the next equation... 

By this method the step-size parameter p is taken equal to 1 and the search vector is obtained from... 

Scales (1986) recommends the Polak Ribiere version because it has slightly better convergence properties. Scales also gives an algorithm which is used for both methods that differ only in the formula for the updating of the search vector. 

It is reasonable to choose a search vector p that will be a descent direction, that is, a direction leading to function reduction. A descent direction p is defined as one along which the directional derivative is negative ... 

Minimization methods that incorporate only function values generally involve some systematic method to search the conformational space. In coordinate descent methods, the search directions are the standard basis vectors. A sweep through these n search vectors produces a sequential modification of one function variable at a time. Through repeated sweeping of the n-dimensional space, a local minimum might ultimately be found. Unfortunately, this strategy is inefficient and not reliable.3 4... 

As the convergence ratio measures the reduction of the error at every step (llx +i x ll — Pita x ll for a linear rate), the relevant SD value can be arbitrarily close to 1 when k is large (Figure 12). In other words, because the n lengths of the elliptical axes belonging to the contours of the function are proportional to the eigenvalue reciprocals, the convergence rate of SD is slowed as the contours of the objective function become more eccentric. Thus, the SD search vectors may in some cases exhibit very inefficient paths toward a solution (see final section for a numerical example). 

In describing the steps of a CG method to solve Ax = — b, the residual vector Ax + b is useful. We define r = —(Ax + b) and use the vectors dA below to denote the CG search vectors (for reasons that will become clear in the Newton Methods section). The solution x can then be obtained by the following procedure, once a starting point Xq is specified.78 79... 

The recurrence relations for the preconditioned conjugate gradient (PCG) method can be derived from Algorithm [A2] after substituting x = M 1/2x and r + M1/2r. New search vectors d = M 1/2d can be used to derive the iteration process, and then the tilde modifiers dropped. The PCG method becomes the following iterative process. 

In the classic Newton method, the Newton direction is used to update each previous iterate by the formula xfe+1 = x + pfe, until convergence. The reader may recognize the one-dimensional version of Newton s method for solving a nonlinear equation f(x) = 0 x +1 = xk — f(xk)/f (xk). The analogous iteration process for minimizing f x) is x +1 — xk — f xk)lf"(xk). Note that the one-dimensional search vector, -f xit)lf"(.xk), is replaced by the Newton direction -Hk lgt in the multivariate case. This direction is defined for nonsingular Hk. When x0 is sufficiently close to a solution x, quadratic convergence can be proven for Newton s method.3-6 That is, a constant 3 exists such that... 

A.NegativeCurvature ( d) returns the direction with negative curvature in the vector d. It can be used as the search vector for a one-dimensional minimum. 

Search vectors pj are not mutually conjugate (therefore, the algorithm does not solve any quadratic problem in nv one-dimensional searches). 

Note that when a constraint is inserted into the working matrix, the KKT system is not solved to identify the search vector d, but the reduced or projected gradient is exploited. 

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. 

Equation (58) can be regarded as a Gauss-Newton method with memory, where "memory" means that the current search vector is involved in the... 

The Conjugate Gradient method generally converges faster than the steepest descent method due to the fact that it avoids moving in a previous search direction. This is achieved by linearly combining the gradient vector and the last search vector,... 

An optimization framework which determines the search vector at each step according to the size of region in which the objective function is well approximated by a quadratic model. 

We generalize Newton s method for minimization in equation (25) to multivariate functions by expanding /(x) locally along a search vector p (in analogy to equation 24) ... 

From this B, the BFGS search vector is defined as p = -Bkgk-... 

In each step of the nonlinear CG method, a search vector Ak is defined by a recursive formula. A line search is then used as outlined in Algorithm [Al]. The iteration process that defines the search vectors (d is given by ... 

---