Newton Methods

IMSL, LANCELOT, MATLAB, NAG ( NAG Fortran, or NAG C) OPTIMA, PORT 3, TN/TNBC , and VE08 implement quasi-Newton, truncated Newton, and Newton algorithms for bound-constrained optimization. The NEOS SERVER's bound-constrained minimization facility also implements a quasi-Newton algorithm. All these codes implement line-search and trust-region versions of unconstrained minimization algorithms, so our discussion here is brief, emphasizing the differences between the unconstrained and bound-constrained cases.

A line-search method for bound-constrained problems generates a sequence of iterates by setting

,

where is a feasible approximation to the solution, is a search direction, and is the step. The direction is obtained as an approximate minimizer of the subproblem

where is the working set and is an approximation to the Hessian matrix of at . All variables in the working set are fixed during this iteration, while all other variables are in the free set . We can express this subproblem in terms of the free variables by noting that it is equivalent to the unconstrained problem

where is the number of free variables, is the matrix obtained from by taking those rows and columns whose indices correspond to the free variables, and is obtained from by taking the components whose indices correspond to the free variables,

The main requirement on is that be a feasible direction, that is, satisfies the constraints for all sufficiently small. This is certainly the case if , where

is the set of active constraints at . As long as progress is being made with the current , the next working set is obtained by merging with . This updating process is continued until the function cannot be reduced much further with the current working set. At this point, the classical strategy is to drop a constraint in for which has the wrong sign, that is, but , where the binding set

is defined as before. In general it is advantageous to drop more than one constraint, in the hope that the algorithm will make more rapid progress towards the optimal binding set. However, all dropping strategies are constrained by the requirement that the solution of the subproblem be a feasible direction.

An implementation of a line-search method based on subproblem (1.1) must cater to the situation in which the reduced Hessian matrix is indefinite, because in this case the subproblem does not have a solution. This situation may arise, for example, if is the Hessian matrix or an approximation obtained by differences of the gradient. Here, it is necessary to specify by other means. For example, we can use the modified Cholesky factorization.

Quasi-Newton methods for bound-constrained problems update an approximation to the reduced Hessian matrix since, as already noted, only the reduced Hessian matrix is likely to be positive definite. The updating process is not entirely satisfactory because there are situations in which a positive definite update that satisfies the quasi-Newton condition does not exist. Moreover, complications arise because the dimension of the reduced matrix changes when the working set changes. Quasi-Newton methods are usually beneficial when the working set remains fixed during consecutive iterations.

The choice of line-search parameter is quite similar to the unconstrained case. If subproblem (1.1) has a solution and violates one of the constraints, then we compute the largest such that

is feasible. A standard strategy for choosing is to seek an that satisfies the sufficient decrease and curvature conditions. We are guaranteed the existence of such an unless satisfies the sufficient decrease condition and

This situation is likely to happen if, for example, is strictly decreasing on the line segment . In this case it is safe to set .

Up To:

Bound Constrained Optimization.

[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]

Updated 28 March 1996