Trust region

The trust-region methods are a class of robust and efficient globalization strategies for the computation of a local minimum of a possibly non-convex, once continuously differentiable function. The trust-region methods are closely related to the Levenberg -Marquardt algorithm, but have significant differences in the quadratic subproblems to be solved and are deterministic in the choice of step-size restriction. Under certain circumstances, one may also show that linesearch methods are special variants of trust-region method.

Survey

Trust-region methods are used to Nonlinear programming problems (NLP ) of the type

To solve.

In this case, it is believed that once continuously differentiable on. This does not mean that a convex function. Since you also with minimal changes to the algorithm, the following non- smooth nonlinear programming problem

Can solve, we will consider the trust-region method for this class of problems. This is, as well as a Hilbert space.

A trust region method is an iterative process which consists of individual, so-called trust-region steps. Such a trust-region step proceeds in two logical units: First, we calculated a correction. The manner in which such compensation is calculated is, in principle, be chosen freely, as long as the correction satisfies a so-called " Sufficient Decrease Condition". For performance reasons, however, one often calculates the correction by solving a quadratic minimization problem under constraints. The Sequential Quadratic Programming with this ( SQP ) Variant corrections are calculated, under certain circumstances, the corrections you calculated in a ( quasi- ) Newton step. Since this correction, in the sense of the task of the minimization problem can be arbitrarily bad, however, you measure the usefulness of the correction and changed the basis of which the constraints of the quadratic problem.

A trust-region step in detail

Calculating the correction

We assume that a feasible iterate is given. Thus, a correction is calculated by solving the following quadratic programming problem (QP )

With the quadratic function

Herein, the trust-region radius and a symmetric approximation to the Hessian matrix may not exist. In case the function is a second-order Taylor expansion.

We accept short that the matrix symmetric positive (semi-) is definite and that no constraints in the above QP problem occur. Thus the necessary and sufficient conditions for a minimum are just

Which is a quasi- Newton step.

Remark on the solution of the quadratic problem

This minimization problem can generally be solved approximatively. This means that the solution only needs to be a better solution to the QP problem than the so-called Cauchypunkt. More specifically, this means that the following Unlgleichung must meet

Wherein a Coleman -Li scaling matrix, which stores the distance to the obstacle on the diagonal.

Without further assumptions must be a penalty function for the solution formulation of the quadratic minimization problem use to be included in the solution. However, for a finite dimensional space, to be replaced by a truncated conjugate gradient method and ( truncated CG) or a non-linear Gauss -Seidel methods are used for solution.

As mentioned, a desired correction can be poor, so it is calculated to determine the quality of a scalar correction, the so-called contraction rate

This value measures the deviation of the predicted by the quadratic function reduction (predicted reduction) of the actual (actual reduction). In the literature, therefore, is also often

Comment on: De facto measures the contraction rate of the linearity of the gradient. If a quadratic function, the contraction rate will always be 1 if. In practice, you should test therefore whether applies.

Update step

Finally, it is determined based on whether the correction is accepted and as the next trust region radius is selected.

Does, then, and selected. Otherwise, and

Here, and to choose a priori. In the literature, further constants are often used to elect the new trust-region radius to adjust fine, but the process comes up with these constants.

Convergence properties

One can under certain, but very weak assumptions show that the thus calculated iterates converge to solutions of the necessary first-order conditions.

Basically, you go here, proceed as follows:

• The solution of the QP problem always satisfies the Sufficient decrease condition (if not Choose the Cauchy point). That is: Are corrections successful, so holds, then we obtain the following inequality

So you can limit the actual descent into by the norm of the gradient and the trust-region radius at the bottom.

• If we now assume that the norm of the gradient is limited by down, we obtain the following: Suppose there are infinitely many successful steps, then converges to or and to solve the problem ( at least the necessary first-order conditions ). Otherwise, due to the above inequality the trust-region radius must converge to 0. In the event but would the quadratic function in an increasingly better approximation and the Decrease ratio would go against one. But that would assume disagree that there are not an infinite number of successful steps.

Differences to other methods

• The Levenberg -Marquardt method performs a non-deterministic update the step-size restriction.
• The trust region method is Newton -like, ie the corrections are calculated using a Taylor expansion of the second order, the Levenberg- Marquardt method a quadratic auxiliary problem is solved based on a Taylor expansion of the first order.
• Unlike linesearch algorithms, the step size restriction is selected in the trust-region method of calculating a correction. Due to the additional constraints in the minimization problem, therefore a different and better solution is calculated, as they would provide the same step-size restriction in the line search algorithm.

Extensions to trust-region method

• In order Nonlinear programming problems with more general constraints of the type

Where one can use so-called filter- trust-region method.

• There are extensions to trust-region method, which also calculate convergence to critical points of the second order, ie points for which it holds