Newton Methods

From NEOS

Revision as of 01:04, 10 April 2007 by Leyffer (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

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

x k + 1 = x k + α k d k

where $x k$ is a feasible approximation to the solution, $d k$ is a search direction, and $α k > 0$ is the step. The direction $d k$ is obtained as an approximate minimizer of the subproblem

$\min_d \left\{ \nabla f(x_k)^T d + \frac{1}{2} d^T B_k d \; : \; d_i = 0 \; \forall i \in W_k\right\}$

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

$\min_w \left\{ g_k^T w + \frac{1}{2} w^T A_k w, \; w \in R^{m_k} \right\}$

where $m k$ is the number of free variables, $A k$ is the matrix obtained from $B k$ by taking those rows and columns whose indices correspond to the free variables, and $g k$ is obtained from $\nabla f(x_k)$ by taking the components whose indices correspond to the free variables, $F k$ .

The main requirement on $W k$ is that $d k$ be a feasible direction, that is, $x k + α d k$ satisfies the constraints for all $α > 0$ sufficiently small. This is certainly the case if $W k = A (x k)$ , where

$A(x_k) = \{ i : x_i = l_i\} \cup \{ i : x_i = u_i \|$

is the set of active constraints at $x$ . A s long as progress is being made with the current $W k$ , the next working set $W k + 1$ is obtained by merging $A (x k + 1)$ with $W k$ . 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 $W k$ for which $\partial_i f(x_k)$ has the wrong sign, that is, $i \in W_k$ but $i \not \in B(x_k)$ , where the binding set

$B(x_k) = \{ i : x_i = l_i, \partial_i f(x_k) \geq 0 \} \cup \{ i : x_i = u_i, \partial_i f(x_k) \leq 0 \}$

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 toward s the optimal binding set. However, all dropping strategies are constrained by the requir ement that the solution $d k$ of the subproblem be a feasible direction.

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

Quasi-Newton methods for bound-constrained problems update an approximation to t he 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 th e reduced matrix changes when the working set $W k$ changes. Quasi-Newt on methods are usually beneficial when the working set remains fixed during consecutive iterations.

The choice of line-search parameter $W k$ is quite similar to the unconstrained case. If subproblem (1.1) has a solution $d k$ and $x k + d k$ violates one of the constraints, then we compute the largest $\mu_k \in (0,1)$ such that

x k + μ k d k

is feasible. A standard strategy for choosing $α k$ is to seek an $\alpha_k \in (0,\mu_k]$ that satisfies the sufficient decrease and curvature conditions. We are guaranteed the existence of such an $α k$ unless $μ k$ satisfies the sufficient decrease condition and

$\nabla f(x_k + \mu_k d_k)^T d_k < 0$

This situation is likely to happen if, for example, $f (x)$ is strictly decreasing on the line segment $[x k, x k + μ k d k]$ . In this case it is safe to set $α k = μ k$ .

Newton Methods

From NEOS

Views

Personal tools

Navigation

Search

Toolbox