### Journal Menu >> Applied Mathematics, 2011, 2, 424-426 doi:10.4236/am.2011.24052 Published Online April 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM A New Technique for Estimating the Lower Bound of the Trust-Region Subproblem* Xinlong Luo School of Information and Communication Engineering, Beijing University of Posts and Telecommu nications, Beijing, China E-mail: luoxinlong@gmail.com, luoxinlong@bupt.edu.cn Received January 23, 2011; revised February 10, 2011; accept ed Feb ruary 12, 2011 Abstract Trust-region methods are popular for nonlinear optimization problems. How to determine the predicted re-duction of the trust-region subproblem is a key issue for trust-region methods. Powell gave an estimation of the lower bound of the trust-region subproblem by considering the negative gradient direction. In this article, we give an alternate way to estimate the same lower bound of the trust-region subproblem. Keywords: Trust-Region Method, Unconstrained Optimization, Trust-Region Subproblem 1. Introduction There are many methods for solving an unconstrained optimi zati on problem ,minnxfx (1) where f is a smooth function. Line search methods [1,2] and trust-region methods  are the two popular classes of methods for the problem (1). In this article, we consi- der the trust-region method for this problem. The trust- region method for the problem (1) need to solve the fol- lowing trust-region subproblem at every step: 1 ,min 2TTkk knsqs gssBs (2) subject to ,ks (3) where =kkfxg is the gradient of the objective fun- ction f at the current approximation solution kx, kB is an n by n symmetric matrix which approxi- mates the Hessian matrix of f, and >0k is a trust- region radius. It is a key issue to estimate the lower bound of the trust-region subproblem (2) and (3) for analyzing the global convergence of the trust-region methods for the problem (1) [1-5]. Powell  obtained a lower bound of the subproblem (2) and (3) by considering the quadratic model ksqalong the negative gradient direction kg. In the next section we give an alternate way to obtain the same estimation of its lower bound. Throughout the paper  denotes the Euclidean vector norm or its in- duced matrix norm. 2. A New Estimation Technique In this section, we give an alternate way to estimate the lower bound and upper bound of 0kkkqqs, res- pectively, where ks is the solution of the subproblem (2) and (3). Firstly, we give the well-known properties of the trust-region problem [6,7]: Lemma 2.1 Vector ks is a solution of the problem (2)-(3) iif kks and there exists 0k to satisfy =,kkk kBIsg (4) 0,kkBI (5) =0,kk ks (6) where nnkB is a symmetric matrix. This lemma can b e proved by the KKT (Karush-Kuhn- Tucker) conditions for the constraint optimization pro- blem . Powell  obtained an estimation of the lower bound of 0kkqqs in the trust region ks as fol- lows: Lemma 2.2 (Powell, 1975 ) If ks is a solution of *This research was supported in part by Grant 2009CB320401 fromNational Basic Research Program of China, and Grant YBWL2010152from Huawei Technologies Co., Ltd., and Grant BUPT2009RC0118from the Fundamental Research Funds for the Central Universities. X. L. LUO Copyright © 2011 SciRes. AM 425(2) and (3), then 10min, .2kkk kkkkqqsgBg (7) The estimation of the predicted reduction (7) is a key property to analyze the convergence of the trust-region method. Here, we are interested in the question whether we can obtain the analogous result of (7) if we directly consider the solution of (4) and (5). Our motivation is that we obtain the solution of the trust-region subpro- blem (2) and (3) by solving (4)-(6), and we need to dire- ctly consider the search direction ks of (4) and its res- tricted step  or the parameter k [8-11] for some tru- st region methods. Therefore, we give an alternate way to estimate the lower bound of 0kkkqqs by directly considering the solution (4)-(6) of the trust-region sub- problem (2) and (3). Lemma 2.3 If 0k such that (5) is satisfied and ks is a solution of (4), then 10min,.2kkk kkkkqqs gsgB (8) Proof. From (4) we get =.TTTk kkkkkkksBsssgs (9) Combining the above equality and (4)-(5), we have 2221110= =22211 =2211 ,2TT TTkkkkkkkkkk kk kTkkk kkkkk kkk qqs sBsgsssgssgBIgsgB (10) where kkBI is the generalized inverse of kkBI. Now we consider the properties of the function 221.kkk sgB (11) It is not difficult to know that the function  is convex when >0kB, since 32=2 0kk gB. Thus, t he function  attains its minimizer min when min satisfies =0min and k B, i.e. 2=2 ,mink kk kgsBs (12) when =,and>.mink kkminkgs BB (13) We will prove this property by distinguishing two cases separately, namely min is nonnegative or negative. When kk kgs B, from (13), we have 0min. In this case, combining 0k with (10)-( 13), we obt ain 22210 =1 =221 .2kkk kkkminkk kkkks qq sgBgs Bsgs (14) The other case is