Applied Mathematics, 2011, 2, 424-426
doi:10.4236/am.2011.24052 Published Online April 2011 (http://www.SciRP.org/journal/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
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
xg 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 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 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