tailieunhanh - A trust region method using subgradient for minimizing a nondifferentiable function

The minimization of a particular nondifferentiable function is considered. The first and second order necessary conditions are given. A trust region method for minimization of this form of the objective function is presented. The algorithm uses the subgradient instead of the gradient. | Yugoslav Journal of Operations Research Volume 19 (2009) Number 2, 249-262 DOI: A TRUST REGION METHOD USING SUBGRADIENT FOR MINIMIZING A NONDIFFERENTIABLE FUNCTION Milanka GARDAŠEVIĆ FILIPOVIĆ Faculty of Architecture, University of Belgrade, Serbia milanka@ Received: Avgust 2007 / Accepted: November 2009 Abstract: The minimization of a particular nondifferentiable function is considered. The first and second order necessary conditions are given. A trust region method for minimization of this form of the objective function is presented. The algorithm uses the subgradient instead of the gradient. It is proved that the sequence of points generated by the algorithm has an accumulation point which satisfies the first and second order necessary conditions Keywords: Trust region method, non-smooth convex optimization. 1. INTRODUCTION A motivation for the idea of the trust region method is to circumvent the difficulty caused by non-positive definite Hessian matrix in the well known Newton method. In this case the following quadratic function q ( k ) (δ ) , obtained by truncating the Taylor series for f ( x ( k ) + δ ) , given as follows T 1 f ( x ( k ) + δ ) ≈ q ( k ) (δ ) = f ( k ) + g ( k ) δ + δ T G ( k )δ 2 does not have a unique minimum and the method is not well defined. We used the following notation: denote by f ( k ) = f ( x ( k ) ), g ( k ) = g ( x ( k ) ) = ∇f ( x ( k ) ) , where ∇ denotes the gradient operator T ⎛ ∂ ∂ ∂ ⎞ (k ) (k ) (k ) , ,., ⎜ ⎟ , G = G ( x ) denotes the Hessian at x , and a vector refers to a x x x ∂ ∂ ∂ 2 n ⎠ ⎝ 1 M., Gardašević Filipović / A Trust Region Method Using Subgradient 250 column vector. Another obstacle is that the region about x ( k ) in which the Taylor series approximates the function does not include a minimizing point of q ( k ) (δ ) . A more realistic approach therefore is to assume that it can be defined some neighborhood Ω( k ) of x ( k ) in which q ( k ) (δ ) agrees with f ( x (