×

Trust region methods for unconstrained minimization. (English) Zbl 0571.90081

Nonlinear optimization, Proc. NATO Adv. Res. Inst., Cambridge/Engl. 1981, NATO Conf. Ser., Ser. II, 29-38 (1982).
[For the entire collection see Zbl 0541.00004.]
Unconstrained minimization of a real valued differentiable function of several real variables is a fundamental problem of mathematical programming. There are many algorithms for obtaining a numerical approximation to a solution of an unconstrained minimization problem. The most effective algorithms are usually iterative and are based upon some variant of Newton’s method for finding a zero of the gradient of the objective function. It is well known that Newton’s method must be modified in various ways in order to produce a robust optimization algorithm. Such modifications are generally designed to force convergence of the sequence of iterates to a point which satisfies as many necessary conditions for minimization as possible. The most familiar modifications of this type generally compute a search direction followed by a line search to obtain a new iterate from the previous iterate. Recently, various strategies have been introduced which have been designed to make better use of second order information when it is available. These strategies have resulted in iterations which converge to critical points which satisfy second order necessary conditions for minimization.
In this paper an alternate approach to safeguarding Newton-like methods is discussed. The approach is well known. It is appropriately called a model trust region method in that the step to a new iterate is obtained by minimizing a local model to the objective function over a restricted ellipsoidal region centered about the current iterate. The diameter of this region is expanded and contracted in a controlled way based upon how well the local model predicts behaviour of the objective function. This strategy will force convergence of the iterates to a critical point which satisfies second order necessary conditions for minimization under very reasonable assumptions about the objective function.

MSC:

90C30 Nonlinear programming
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods

Citations:

Zbl 0541.00004