Newton direction

A sufficient condition for a unique Newton direction is that the matrix of constraint derivatives is of full rank (linear independence... 

Difficulty 3 can be ameliorated by using (properly) finite difference approximation as substitutes for derivatives. To overcome difficulty 4, two classes of methods exist to modify the pure Newton s method so that it is guaranteed to converge to a local minimum from an arbitrary starting point. The first of these, called trust region methods, minimize the quadratic approximation, Equation (6.10), within an elliptical region, whose size is adjusted so that the objective improves at each iteration see Section 6.3.2. The second class, line search methods, modifies the pure Newton s method in two ways (1) instead of taking a step size of one, a line search is used and (2) if the Hessian matrix H(x ) is not positive-definite, it is replaced by a positive-definite matrix that is close to H(x ). This is motivated by the easily verified fact that, if H(x ) is positive-definite, the Newton direction... 

One continuation method reconstructs exactly the Newton method when t moves in the positive direction. Think of the surface that corresponds to summing the squares of the functions one wishes to drive to zero. If the Newton method flounders in a local hole in this surface where the bottom of the hole does not reach down to zero, and thus where the equations do not have a solution, it would be very useful to climb out of the hole by going in the reverse of the Newton direction (i.e., by simply reversing the sign on f), hopefully over the top of a nearby ridge and down the other side into a hole where a solution does exist. A continuation method does just this. 

Alternatively, such a Newton direction pfc satisfies the linear system of n simultaneous equations, known as the Newton equation ... 

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... 

First, when Hk is not positive-definite, the search direction may not exist or may not be a descent direction. Strategies to produce a related positive-definite matrix Hk, or alternative search directions, become necessary. Second, far away from x, the quadratic approximation of expression [34] may be poor, and the Newton direction must be adjusted. A line search, for example, can dampen (scale) the Newton direction when it exists, ensuring sufficient decrease and guaranteeing uniform progress toward a solution. These adjustments lead to the following modified Newton framework (using a line search). 

The Wolfe criterion (Wolfe, 1969) The gradient is calculated in the Newton prediction g(x + d ). The gradient along the Newton direction at this point is... 

The Newton direction is used to perform a one-dimensional search for the minimum. 

The parameter pi must be positive, that is, [j, = 0.01. If this test is unsatisfied, the one-dimensional search along the Newton direction must be avoided. In this case, an alternative method must be adopted. 

In the former one, we assume to be valid the feature of the Newton direction to be a direction of function decreasing and, in this case, the search for a minimum is performed along the same Newton direction. 

By varying the parameter 2 (therefore, the parameter a is changed too), a onedimensional search along the Newton direction is carried out. 

The least squares problem may be solved numerically by computing a quasi-Newton direction. 

If the Jacobian is reused for several steps including a discontinuity, the Newton direction may become totally misleading. 

Another important search direction method is the Newton direction. This direction is derived from the second-order Taylor series. Methods that use the Newton direction have a fast rate of local convergence. Nevertheless, the main drawback is that it requires the explicit computation of the Hessian matrix (V /(ar)). 

Conejo, A. J., Nogales, E J., Prieto, F. J. (2002). A decomposition procedure based on approximate Newton directions mathematical programming. Mathematical programming, series A, 93, 495-515. 

---