Global convergence of trust region methods for minimizing a nondifferentiable function

[摘要] Three fundamental convergence properties of trust region (TR) methods for solving nonsmooth unconstrained minimization problems are considered in this paper. The first is to prevent the false termination of the TR iterates, $i.e.$, if the optimal solution of the TR subproblem is at the current iterate, then the current iterate is a stationary point of the objective function. Under the assumptions given in this thesis, we prove that false termination cannot happen. The second property is that an acceptable TR step can eventually be obtained by reducing the size of trust region. The third property states that any accumulation point of the TR iterates is a stationary point of the objective function. The convergence analysis is made for two classes of nonsmooth objective functions, regular functions and locally Lipschitz functions. Some general assumptions made on the objective function and the local model are shown to be satisfied by many nonsmooth TR methods. An example of locally Lipschitz function is also proved to satisfy these assumptions. Under these assumptions, a unified approach to analyze the global convergence of TR methods is provided in the paper. The order of approximation between the objective function and the local model at each iteration plays an important part in the analysis. Three equivalent conditions of the first order approximation have been derived for nonsmooth TR methods. We give an alternative approach for obtaining the convergence result of El Hallabi & Tapia (1987) for TR methods with convex local models.

[发布机构] Rice University