Local Convergence of the Symmetric Rank-One Iteration.
We consider conditions under which the SR1 iteration is locally convergent. We apply the result to a pointwise structured SR1 method that has been used in optimal control.
Introduction
. The symmetric rank-one (SR1) update [1] is a quasi-Newton
method that preserves symmetry of an approximate Hessian (optimization problems)
or Jacobian (nonlinear equations). The analysis in this paper is from the nonlinear
equations point of view. Our purpose is to prove a local convergence result using
the concept of uniform linear independence from [5], extend that result to structured
updates where part of the Jacobian can be computed exactly, and then apply those
results to the pointwise SR1 update considered in [14] in the context of optimal control.
We we begin with a nonlinear equation
in R N . We make the standard assumptions in nonlinear equations.
Assumption 1.1. F has a root x   . There is ffi ? 0 such that the Jacobian F 0 (x)
exists and is Lipschitz continuous in the set
with Lipschitz constant fl. F 0 (x   ) is nonsingular.
Later in this paper we will assume that F 0 (x) is symmetric near x   and use the
SR1 update to maintain symmetric approximations to F 0 (x   ).
From current approximations iteration computes a
new point x+ by computing a search direction,
and updating x c ,
Version of May 17, 1995.
y North Carolina State University, Department of Mathematics and Center for Research in Scientific
Computation, Box 8205, Raleigh, N. C. 27695-8205 (Tim Kelley@ncsu.edu). The research of this
author was supported by National Science Foundation grant #DMS-9321938 and North Atlantic Treaty
Organization grant #CRG 920067. Computing was partially supported by an allocation of time from
the North Carolina Supercomputing Center.
z Universit?t Trier, FB IV - Mathematik and Graduiertenkolleg Mathematische Optimierung, 54296
Trier, Germany (sachs@uni-trier.de). The research of this author was supported by North Atlantic
Treaty Organization grant #CRG 920067.
is updated to form B+ by setting
and, if (y updating B c to obtain
the update for B is skipped, so
Observations have been reported [15], [4], [5], [19], [10], [18], [11], [20], [14], that
indicate that SR1 can outperform BFGS in the context of optimization, where either
the approximate Hessians can be expected to be positive definite or a trust-region
framework is used [3], [4], [5].
One modification of SR1 that allows for a convergence analysis has been proposed
in [17].
The SR1 update was considered in [2] where it was shown that the local superliner
convergence theory in that paper did not apply, because the updates could become
undefined.
Preservation of symmetry is an attractive feature, as is the possibility of storing one
vector per iterate in a matrix-free limited memory implementation. However, implementations
that store a single vector for each iteration are known for Broyden's method
[8], [13], and the BFGS method [21], which have much better understood convergence
properties. The advantage of the SR1 method over others is in a reduction in the number
of iterations. Such a reduction has been observed by many authors as we indicated
above.
As is standard, we update the approximate Jacobian only if
for some oe 2 (0; 1) fixed. In many recent papers [5], [15], [3], on SR1, (1.5), with an
arbitrary choice of oe, is one of the assumptions used to prove convergence of B n to
The numerical results presented in [5], [15], and [3] use very small values of oe.
In this paper, as was done in [14], we use a larger value of oe than in other treatments
of the SR1 iteration as a way to improve stability. The estimates in x 2 can be used as
a rough guide in selection of an appropriate value of oe. The numerical results in x 5
illustrate the benefits of varying oe.
In this paper we show that if the initial approximations to the solution and Jacobian
are sufficiently good and if the sequence of steps that satisfy (1.5) also satisfy a uniform
linear independence condition [5], then the iteration will be locally linearly convergent
and the sequence fB k g will remain near to F 0 (x   ). A stronger uniform linear independence
condition implies k-step superlinear convergence for some integer k. Thus, our
goal is different from that in [5], [15], and [3], where convergence of the iteration to the
solution was an assumption and conditions were given that guaranteed convergence of
the approximate Jacobians to F 0 (x   ).
While the uniform linear independence condition may seem strong, it is a reasonable
condition for very small problems. Such problems arise as part of the pointwise SR1
method proposed in [14] for certain optimal control problems and the results in this
paper give insight that we use to improve the performance of the pointwise SR1 method.
In x 2 we state and prove our basic convergence results. We consider structured updates
in x 3 and the application to pointwise updates in x 4. Finally we report numerical
results in x 5.
2. Basic Lemmas and Convergence Results. As we deal with local convergence
only in this paper, we take full steps use the fact that
which is a direct consequence of the definition and the
equation for the quasi-Newton step B c s Hence the SR1 update can be
We use the notation
for errors in Jacobian and solution approximations.
It may happen that many iterations take place between updates of B. We must
introduce notation to keep track of those iterations that result in a change in B. We
say that s n is a major step, x n+1 is a major iteration, and B n+1 a major update
1). In this case B n+1 6= B n .
A step is a minor step if it is not a major step (and hence no update of B takes place
local convergence theory must show that the new approximation
B n+1 to the Jacobian at the solution is nonsingular. We do this by proving an analog of
the "bounded deterioration" results used in the study of other quasi-Newton methods.
However, an inherent instability must be kept in check and this is where the uniform
linear independence becomes important.
2.1. Stability. We base our main result on several lemmas. The first simply summarizes
some well known results in nonlinear equations [6], [13], [16], and has nothing to
do with an assumption of symmetry of F 0 (x   ) or any particular quasi-Newton method.
Lemma 2.1. Let Assumption 1.1 hold and let ae 2 (0; 1) be given. Then there are
ffl 0 and ffi 0 such that if x c and B c satisfy
then B c is nonsingular and
Moreover
Lemma 2.2. Let the hypotheses of Lemma 2.1 hold. Then there is C 1 such that if
c is a major step, then
ks c k
and
ks c
Proof. By (2.2)
and hence, using (2.6),
ks c k -
ks c k
This is (2.7) with C
We apply (2.9) again to obtain
and hence (2.8) follows from (2.6) and the the fact that C 1 ? fl.
At this point we need to consider a sequence of major steps. Several minor steps in
which (1.5) fails could lie between any two major steps, but they have no effect on the
estimates of the approximate Jacobians. This is also the first place where symmetry
of E (and hence of F 0 (x   )) plays an important role. We remark that (2.11) and (2.12)
differ from estimates of kE k k, used in other recent papers [5],
[15] in that the assumption of good approximations to x   and F 0 (x   ) is used in a crucial
way. The next lemma uses the general approach of [5] and the observation from [5] and
[15] that only the major steps need be considered in the estimates.
Lemma 2.3. Let Assumption 1.1 hold, let ae 2 (0; 1), and let ffl 0 and ffi 0 be such that
the conclusions of Lemma 2.1 hold. Let - k - 0, x 0 , and B 0 be such that F 0
symmetric and
Then at least - k major steps can be taken with B k+1 nonsingular for all
Moreover, there is
are the
sequence of the first k - k major steps, iterations, and updates, then for any 1 - k - k,
Also, for any 0 -
ks
Proof. We set
We note that implies that
ks
We prove the lemma by induction on k. For
and (2.14). We obtain (2.12) from (2.8) and (2.13).
If (2.11) holds for all k ! K -
k, then from (2.7) and (2.14),
We use the induction hypothesis and C to obtain
which proves the first inequality in (2.11). The second inequality
from (2.10).
apply Lemma 2.1 to conclude that at least - k major steps
can be taken and
k. Hence, for
ks
ks l k:
Assuming that (2.12) holds for we note that (2.12) is a consequence of
Lemma 2.2 if
oeks K
Every E k is symmetric because E 0 is. Hence, if we write
then
Combining (2.16) and (2.6) yields
Hence, by (2.15),
ks
ks
As in the proof of (2.11) we have
and
We apply (2.18), (2.19), and the induction hypothesis to (2.17) to get
ks
verifying (2.12).
The estimates in Lemma 2.3 are analogs to the bounded deterioration results common
in the quasi-Newton method literature. However, in this case the deviation of
B k from F 0 (x   ) is exponentially increasing and, at least according to the bounds in
Lemma 2.3, can eventually become so large that convergence may be lost. The SR1
update has, however, a self-correcting property in the linear case [9] that has been exploited
in much of the recent work on the method [15], [3], [5]. This self-correction
property overcomes the instability indicated in the estimates (2.11) and (2.12).
2.2. Uniform Linear Independence. Our uniform linear independence assumption
differs slightly from that in [5]. We only consider major steps and are not concerned
at this point with the total number (major steps required to form the sequence
of linearly independent major steps.
Assumption 2.1. There are c min ? 0 and - k - n such that the hypotheses of
Lemma 2.3 hold. Moreover from each of the sets of columns of normalized major steps
a subsequence fv p
can be extracted such that the matrix S p with columns fv p
has minimum singular value at least c min .
2.3. Convergence Results. Using the assumptions above we can prove q-linear
convergence directly using Lemma 2.3 and the methods for exploitation of uniform
linear independence from [5].
Theorem 2.4. Let Assumptions 2.1 and the hypotheses of Lemma 2.3 hold. Let
ae 2 (0; 1) be given. Then if sufficiently small the SR1 iterates
converge q-linearly to x   with q-factor at most ae.
Proof. The proof is based on the simple observation that Lemma 2.3 states that
the iteration may proceed through -
major steps that then Assumption 2.1
implies that the iteration may continue.
2.3 implies that
k and that by (2.14)
ks ks k k
Note that
min
Now enough so that
then are replaced by E- k and e- k . Hence, we may continue the
iteration by Lemmas 2.1 and 2.3, obtaining q-linear convergence with q-factor at most
ae.
3. Structured Updates. In order to apply the convergence results to optimal
control problems in the context of pointwise updates, as a next step, we extend the
statements from the previous sections to the case of structured updates. We use the
notational conventions of [7] in the formulation.
Suppose that the Jacobian F 0 of F can be split into a Lipschitz continuous computable
part C(x) and a part A(x) which will be approximated by a SR1 update:
We define the SR1 update by
where the step is computed by solving
If we choose
the secant condition (B+ holds and we obtain from (3.2)
and (3.3)
Hence the SR1 update can be written with a perturbation ~
F+ of F (x+ )
~
c
~
We use the notation
for errors in the Jacobian.
Next we apply Lemma 2.1 to obtain a similar estimate
Lemma 3.1. Let Assumption 1.1 hold and let ae 2 (0; 1) be given. Then there are
ffl 0 and ~ ffi 0 such that if x c and B c for a structured SR1 update satisfy
then defined and satisfies
Moreover
ks c
Proof. Note that
with a Lipschitz constant fl C for C. Then holds and since Lemma 2.1 holds
for arbitrary approximations of the Jacobian, x+ exists and (3.8) holds. Observing that
ks c k 2
proves (3.9) and completes the proof.
The next lemma is an extension of Lemma 2.2. Before we can state the lemma we
define when an update is skipped. We update B only if
for some oe 2 (0; 1) fixed. The definition of minor and major steps is the same as that
in x 2 with (3.10) playing the role of (1.5).
Lemma 3.2. Let the hypotheses of Lemma 3.1 hold. Then there is C 1 such that if
c is a major step, then
ks c k
and
ks c
Proof. For the structured updates we have
~
If we note that
ks c k
and (3.10) has been changed accordingly then the proof is the same as for Lemma 2.2
with
and F (x) replaced by ~
F .
In the next lemma symmetry is assumed which causes some additional changes for
the proof.
Lemma 3.3. Let Assumption 1.1 and the hypotheses of Lemma 3.1 hold. Let -
be such that
Then at least - k major steps can be taken with B k+1 nonsingular for all
Moreover, there is
are the
sequence of the first k - k major steps, iterations, and updates, then for any 1 - k - k,
Also, for any 0 -
ks
Proof. The first part of the induction proof for (3.15) is identical to the one for
Lemma 2.3 and therefore omitted.
Assuming that (3.16) holds for we note that (3.16) is a consequence of
Lemma 3.2 if we have from (3.13)
oeks K
If we write
~
then by (3.9)
and
~
Combining (3.18) and (3.9) yields
Note that by assumption hence by definition (3.6)
Hence, by (3.17),
ks
where, as in x 2
As in the proof of (2.11) we have
and
We apply (3.20), (3.21), and the induction hypothesis to (3.19) to get
ks
verifying (3.16).
Using the definition of uniform linear independence from x 2.2 we may state the
structured analog of Theorem 2.4. The proof is essentially identical to that of Theorem
2.4.
Theorem 3.4. Let Assumptions 2.1 and the hypotheses of Lemma 3.3 hold. Let
ae 2 (0; 1) be given. Then if sufficiently small the SR1 iterates
converge q-linearly to x   with q-factor at most ae.
4. Pointwise Structured Updates for Optimal Control. In order to apply
the convergence results to optimal control problems in the context of pointwise updates,
as a next step, we extend the statements from the previous sections to the case of
pointwise structured updates.
Our nonlinear equations represent the necessary conditions for the optimal control
problem
minimize
over
We set
solves the adjoint equation
We seek to solve the nonlinear system
@
H u (x; u; t)C
A =B
A
for which satisfy the boundary conditions
We use the following assumption
Assumption 4.1. f; L and their first and second partial derivatives with respect
to x and u are continuous on IR N \Theta IR M \Theta [0; T ].
Under the above assumption, F is Fr'echet -differentiable and the Fr'echet -derivative
is given by
@
A =B
@
@
A
with
dt and all other components as multiplication operators.
into two parts F 0 containing all
information from first derivatives
@
A
and A(z) consisting of second order derivatives
@
All entries depend on time t so that A(z) is typically approximated by a family of quasi
Newton updates depending also on time t
@
A
with
We use a pointwise analog of (3.10)
We update B at each t 2 [0; T ] by a structured SR1 update
In order to justify the use of pointwise updates, we state the next lemma.
Lemma 4.1. If B 0 is given of the form (4.3), then all B k defined by (4.6) are also
multiplication operators with
Proof. The proof is via induction and we show the step from B c to B+ . We write
Note that by (4.4)
Since the differentiation operator D appears linearly in F and in C it cancels in
H
This implies with the differentiability assumption on the data that pointwise
holds for some OE 2 L 1 [0; T ]. Since B c is also in L 1 we have
The decision in the update formula (4.6) shows that the components of B+ are measurable
functions. They are also essentially bounded because either
or using the choice of oe in (4.6) and (4.7)
This completes the proof.
The next Lemma gives pointwise estimates on the error in the Jacobian in the
context of pointwise updates which will be used later for uniform estimates.
Lemma 4.2. Assume that for some t 2 [0; T is a multiplication operator
and let is a major step, then E+ (t) is also a
multiplation operator and the following estimates hold:
ks c (t)k
and
ks c (t)k)ks c (t)k:
Proof. Observe that we can rewrite (4.4) pointwise
By assumption, the last term is a multiplication operator and therefore does not contain
the differentiation operator D. In first and the second term in parentheses the D cancels,
so that we can estimate pointwise under the given smoothness assumptions on the data:
ks c
Hence we obtain from (3.13) using (4.12) that pointwise
ks c (t)k ks c (t)k
To estimate kE+ s c k recall that from the secant condition
and therefore (4.9) holds. Furthermore, from (4.11)
and
ks c k 2
The next Lemma describes a linear rate estimate in a uniform norm.
Lemma 4.3. For ae 2 (0; 1) there are ffl 0 and ffi 0 such that if s c is a major step for
all t and B c for the pointwise structured SR1 update satisfies
defined and satisfies
Moreover for some fl; C
ks c k1
ks c k 2(4.15)
and
Proof. The assumptions imply that
is small so that Lemma 2.1 can be invoked to yield (4.13). From this we deduce
ks c k1 . (4.8) gives
ks c k1
which is (4.14). In the same way we use (4.9) and (4.10) to obtain (4.15) and (4.16),
resp.
5. Numerical Results. We present some numerical results which illustrate the
observations from the previous sections. Let us consider the following class of examples:
First we set
Furthermore, we set x . The initial data are given by
@
We did update if
is true. In [14] we used
The discretization parameter comes from the discretization of the two-point
boundary value problem by the trapezoid finite difference scheme used with a
Richardson extrapolation to achieve 4th order accurate results, see e.g. [12]. This
indicates that the termination criterion should be
We approximate the norm in the discrete case also with accuracy of order 4.
The numbers in column [No Upd %] give the percentage of the 121 3 \Theta 3-matrices
which have not been updated at iteration k. The difference in the matrices is computed
as follows:
where kB(t)k F denotes the Frobenius-Norm in R 3\Theta3 .
In

Table

5.1 we report on the results for the SR-1 update where the choice of oe is
based on the truncation error of the discretization scheme (h 4 - 0:6 \Theta 10 \Gamma5 ). Tables 5.2
and 5.3 show the effects of more conservative updating strategies. The analysis in the
preceding sections indicates that a larger value of oe will keep smaller and might
thereby allow for a more monotone iteration. While an increase by a factor of 100 did
reduce the size of kE k k, it did not lead to any improvement in overall performance
(see

Table

5.2). Increasing oe by a factor of 1000 (see Table 5.3) led to a performance
improvement of about 20%.
In

Table

5.2 we used a less stringent requirement for not updating the Hessians. In
this table oe was increased by a factor of 10 2 .
Note the reduced error in the Hessian updates in the early phase of the algorithm.
Table
9 0.72865D-04 0.002 1.7 332.568

Table
Table


--R



Analysis of a symmetric rank-one trust region method
Testing a class of methods for solving minimization problems with simple bounds on the variables

Numerical Methods for Nonlinear Equations and Unconstrained Optimization
Convergence theorems for least change secant update methods
Fast secant methods for the iterative solution of large nonsymmetric linear systems
John Wiley and Sons
An Algorithm for Optimizing Functions with Multiple Minima

Numerical Solution of Two Point Boundary Value Problems
Iterative Methods for Linear and Nonlinear Equations
A pointwise quasi-Newton method for unconstrained optimal control problems
A theoretical and experimental study of the symmetric rank one update
Iterative Solution of Nonlinear Equations in Several Variables
A new approach to the symmetric rank-one updating algorithm
Yield optimization using a GaAs process simulator coupled to a physical device model
On large scale nonlinear least squares calculations

Compact storage of Broyden-class quasi-Newton matrices
--TR

--CTR
P. Spellucci, A Modified Rank One Update Which Converges Q-Superlinearly, Computational Optimization and Applications, v.19 n.3, p.273-296, September 2001
optimal control;SR1 update;pointwise quasi-Newton method