### Paper Menu >>

### 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 , min n x f x (1) where f is a smooth function. Line search methods [1,2] and trust-region methods [3] 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 2 TT kk k n s qs gssBs (2) subject to , k s (3) where = kk f xg is the gradient of the objective fun- ction f at the current approximation solution k x , k B is an n by n symmetric matrix which approxi- mates the Hessian matrix of f , and >0 k 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 [5] obtained a lower bound of the subproblem (2) and (3) by considering the quadratic model k s qalong 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 0 kkk qqs, res- pectively, where k s 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 k s is a solution of the problem (2)-(3) iif kk s and there exists 0 k to satisfy =, kkk k BIsg (4) 0, kk BI (5) =0, kk k s (6) where nn k B is a symmetric matrix. This lemma can b e proved by the KKT (Karush-Kuhn- Tucker) conditions for the constraint optimization pro- blem [4]. Powell [5] obtained an estimation of the lower bound of 0 kk qqs in the trust region k s as fol- lows: Lemma 2.2 (Powell, 1975 [5]) If k s is a solution of *This research was supported in part by Grant 2009CB320401 fro m N ational Basic Research Program of China, and Grant YBWL2010152 from Huawei Technologies Co., Ltd., and Grant BUPT2009RC0118 from the Fundamental Research Funds for the Central Universities. X. L. LUO Copyright © 2011 SciRes. AM 425 (2) and (3), then 1 0min, . 2 kkk kkkk qqs g B g (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 k s of (4) and its res- tricted step [2] or the parameter k [8-11] for some tru- st region methods. Therefore, we give an alternate way to estimate the lower bound of 0 kkk qqs by directly considering the solution (4)-(6) of the trust-region sub- problem (2) and (3). Lemma 2.3 If 0 k such that (5) is satisfied and k s is a solution of (4), then 1 0min,. 2 kkk kkkk qqs gsgB (8) Proof. From (4) we get =. TTT k kkkkkkk sBsssgs (9) Combining the above equality and (4)-(5), we have 2 22 111 0= = 222 11 =22 11 , 2 TT TT kkkkkkkkkk kk k T kkk kkk kk k kk qqs sBs g sss g s sgBIg sg B (10) where kk BI is the generalized inverse of kk B I . Now we consider the properties of the function 22 1. kk k sg B (11) It is not difficult to know that the function is convex when >0 k B, since 3 2 =2 0 kk gB . Thus, t he function attains its minimizer min when min satisfies =0 min 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 0 min . In this case, combining 0 k with (10)-( 13), we obt ain 22 2 1 0 = 1 =2 2 1 . 2 kkk kk k min kk kk kk s qq sg B gs Bs gs (14) The other case is < kk k gs B, which gives <0 min from (13). Since the function is mono- tonically increasing for all 0 k when < kk k gs B, from (10) and (11), we obtain 22 2 11 02 111 =0=. 222 kkk kkk kk kkk qqs sg B gB (15) Combining (14) with (15), we obtain 1 0min,. 2 kkk kkkk qqs ggBs (16) When =0 k which shows the constraint is inactive, from (4) and (5), and the definition of k qs, we have 2 11 0= 22 T kkkkkkkk qqsgBggB (17) which shows that (8) is also true. □ 3. Conclusions In this article, we give an alternate way to estimate the lower bound of the trust-region method. This new te- chnique can be applied to analyze the convergence of trajectory-following methods for unconstrained optimi- zation problems [9-11]. The interested future works is that this new technique is applied to estimate the lower bound of the trust-region subproblem of the constraint optimization. 4. Acknowledgments We would like to acknowledge Jiawang Nie and Hong- chao Zhang for their constructive suggestions. 5. References [1] J. E. Dennis and R. B. Schnabel, “Numerical Methods for Unconstrained Optimization and Nonlinear Equations,” Prentice-Hall, Inc., Englewood Cliffs, 1983. X. L. LUO Copyright © 2011 SciRes. AM 426 [2] R. Fletcher, “Practical Methods of Optimization,” 2nd Edition, John Wiley & Sons, Chichester, 1987 [3] A. R. Conn, N. Gould and P. L. Toint, “Trust-Region Methods,” SIAM, Philadelphia, 2000. doi:10.1137/1.9780898719857 [4] J. Nocedal and S. J. Wright, “Numerical Optimization,” Springer-Verlag, New York, 1999. doi:10.1007/b98874 [5] M. J. D. Powell, “Convergence Properties of a Class of Minimization Algorithms,” In: O. L. Mangasarian, R. R. Meyer and S. M. Robinson Eds., Nonlinear Programming 2, Academic Press, New York, 1975, pp. 1-27. [6] D. M. Gay, “Computing Optimal Locally Constrained Steps,” SIAM Journal on Scientific and Statistical Com- puting, Vol. 42, No. 2, 1981, pp. 186-197. doi:10.1137/0902016 [7] J. J. Moré and D. C. Sorensen, “Computing a Trust Re- gion Step,” SIAM Journal on Scientific and Statistical Computing, Vol. 4, No. 3, 1983, pp. 553-572. doi:10.1137/0904038 [8] D. J. Higham, “Trust Region Algorithms and Time Step Selection,” SIAM Journal on Numerical Analysis, Vol. 37, No. 1, 1999, pp. 194-210. doi:10.1137/S0036142998335972 [9] X.-L. Luo, C. T. Kelley, L.-Z. Liao and H. W. Tam, “Combining Trust Region Techniques and Rosenbrock Methods to Compute Stationary Points,” Journal of Op- timization Theory and Applications, Vol. 140, No. 2, 2009, pp. 265-286. doi:10.1007/s10957-008-9469-0 [10] X.-L. Luo, L.-Z. Liao and H. W. Tam, “Convergence Analysis of the Levenberg-Marquardt Method,” Optimi- zation Methods and Software, Vol. 22, No. 4, 2007, pp. 659-678. doi:10.1080/10556780601079233 [11] X.-L. Luo, “A Second-Order Pseudo-Transient Method for Steady-State Problems,” Appllied Mathematics Com- putation, Vol. 216, No. 6, 2010, pp. 1752-1762. doi:10.1016/j.amc.2009.12.029 |