Affine Invariant Convergence Analysis for Inexact Augmented Lagrangian-SQP Methods.
An affine invariant convergence analysis for inexact augmented Lagrangian-SQP methods is presented. The theory is used for the construction of an accuracy matching between iteration errors and truncation errors, which arise from the inexact linear system solvers. The theoretical investigations are illustrated numerically by an optimal control problem for the Burgers equation.
Introduction
. This paper is concerned with an optimization problem of the
following type:
minimize J(x) subject to
are su#ciently smooth functions and X , Y are real
Hilbert spaces. These types of problems occur, for example, in the optimal control of
systems described by partial di#erential equations. To solve (P) we use the augmented
(sequential quadratic programming) technique as developed in [11].
In this method the di#erential equation is treated as an equality constraint, which
is enforced by a Lagrangian term together with a penalty functional. We present an
algorithm, which has second-order convergence rate and depends upon a second-order
su#cient optimality condition. In comparison with SQP methods the augmented
Lagrangian-SQP method has the advantage of a more global behavior. For certain
examples we found it to be less sensitive with respect to the starting values, and the
region for second-order convergence rate was reached earlier, see e.g. [11, 15, 17]. We
shall point out that the penalty term of the augmented Lagrangian functional need
not to be implemented but rather that it can be realized by a first-order Lagrangian
update.
Augmented Lagrangian-SQP methods applied to problem (P) are essentially Newton
type methods applied to the Kuhn-Tucker equations for an augmented optimization
problem. Newton methods and their behavior under di#erent linear transformations
were studied by several authors, see [5, 6, 7, 8, 10], for instance. In this paper,
we combine both lines of work and present an a#ne invariant setting for analysis
and implementation of augmented Lagrangian-SQP methods in Hilbert spaces. An
a#ne invariant convergence theory for inexact augmented Lagrangian-SQP methods
is presented. Then the theoretical results are used for the construction of an accuracy
matching between iteration errors and truncation errors, which arise from the inexact
linear system solvers.
The paper is organized as follows. In -2 the augmented Lagrangian-SQP method
is introduced and necessary prerequisites are given. The a#ne invariance is introduced
Karl-Franzens-Universit?t Graz, Institut f?r Mathematik, Heinrichstra-e 36, A-8010 Graz, Austria
Konrad-Zuse-Zentrum f?r Informationstechnik Berlin (ZIB), Takustra-e 7, D- 14195 Berlin,
Germany (weiser@zib.de). The work of this author was supported by Deutsche Forschungsgemeinschaft
(DFG), Sonderforschungsbereich 273.
S. VOLKWEIN AND M. WEISER
in -3. In -4 an a#ne invariant convergence result for the augmented Lagrangian-SQP
method is presented. Two invariant norms for optimal control problems are analyzed
in -5, and the inexact Lagrangian-SQP method is studied in -6. In the last section
we report on some numerical experiments done for an optimal control problem for the
Burgers equation, which is a one-dimensional model for nonlinear convection-di#usion
phenomena.
2. The augmented Lagrangian-SQP method. Let us consider the following
constrained optimal control problem
minimize J(x) subject to
are real Hilbert spaces. Throughout we do
not distinguish between a functional in the dual space and its Riesz representation
in the Hilbert space. The Hilbert space X - Y is endowed with the Hilbert space
product topology and, for brevity, we set
Let us present an example for (P) that illustrates our theoretical investigations
and that is used for the numerical experiments carried out in -7. For more details we
refer the reader to [18].
Example 2.1.
Let# denote the interval (0, 1) and set
-# for given
We define the space W (0, T ) by
which is a Hilbert space endowed with the common inner product. For controls
the state y # W (0, T ) is given by the weak solution of the unsteady
Burgers equation with Robin type boundary conditions, i.e., y satisfies
and
#y x (t, -)# y(t, -)y x (t, - f(t, -) #
denotes the duality pairing
between H 1 and its dual. We suppose that f # L
Recall that W (0, T ) is continuously embedded into the
space of all continuous functions from [0, T ] into L
2(#2 denoted by C([0, T ]; L
see e.g. [3, p. 473]. Therefore, (2.1a) makes sense. With every controls u, v we associate
the cost of tracking type
J(y, u,
where z # L 2 (Q) and # > 0 are fixed. Let
We introduce the bounded operator
whose action is defined by
#-e(y, u, v), # L 2 (0,T ;H
e(y, u,
where for given g # H
1(# the mapping (-#
1(# is the
Neumann solution operator associated with
.
Now the optimal control problem can be written in the form (P). #
For c # 0 the augmented Lagrange functional associated with (P) is
defined by
Y .
The following assumption is rather standard for SQP methods in Hilbert spaces, and
is supposed to hold throughout the paper.
Assumption 1. Let x # X be a reference point such that
a) J and e are twice continuously Fr-echet-di#erentiable, and the mappings J #
and e # are Lipschitz-continuous in a neighborhood of x # ,
b) the linearization e # of the operator e at x # is surjective,
c) there exists a Lagrange multiplier # Y satisfying the first-order necessary
optimality conditions
where the Fr-echet-derivative with respect to the variable x is denoted by a
prime, and
d) there exists a constant # > 0 such that
for all # ker e #
where ker e # denotes the kernel or null space of e #
Remark 2.2. In the context of Example 2.1 we write x
proved in [18] that Assumption 1 holds provided #y # - z# L 2 (Q) is su#ciently small. #
The next proposition follows directly from Assumption 1. For a proof we refer
to [12] and [13], for instance.
Proposition 2.3. With Assumption 1 holding x # is a local solution to (P).
Furthermore, there exists a neighborhood of is the unique
solution of (2.2) in this neighborhood.
The mapping x # L c (x, # ) can be bounded from below by a quadratic func-
tion. This fact is referred to as augmentability of L c and is formulated in the next
proposition. For a proof we refer the reader to [11].
4 S. VOLKWEIN AND M. WEISER
Proposition 2.4. There exist a neighborhood -
U of x # and a constant - c # 0 such
that the mapping x # L # c (x, # ) is coercive on the whole space X for all x # -
U and
Remark 2.5. Due to Assumption 1 and Proposition 2.4 there are convex neighborhoods
of # such that for all (x, #
a) J(x) and e(x) are twice Fr-echet-di#erentiable and their second Fr-echet-deri-
vatives are Lipschitz-continuous in U(x # ),
c) L # 0 (x, #) is coercive on the kernel of e # (x),
d) the point z is the unique solution to (2.2) in U , and
there exist - # > 0 and - c # 0 such that
for all # X and c # - c. # (2.3)
To shorten notation let us introduce the operator
# for all (x, # U.
Then the first-order necessary optimality conditions (2.2) can be expressed as
To find x # numerically we solve (OS) by the Newton method. The Fr-echet-derivative
of the operator F c in U is given by
denotes the adjoint of the operator e # (x).
Remark 2.6. With Assumptions 1 holding there exists a constant C > 0 satisfying
(see e.g. in [9, p. 114]), where B(Z) denotes the Banach space of all bounded linear
operators on Z. #
Now we formulate the augmented Lagrangian-SQP method.
Algorithm 1.
a) Choose
c) Solve for (#x, #) the linear system
d) Set
back to b).
Remark 2.7. Since X and Y are Hilbert spaces, equivalently be
obtained from solving the linear system
and setting #). Equation (2.7) corresponds to a
Newton step applied to (OS). This form of the iteration requires the implementation
of e # c) of Algorithm 1 do not - see [11]. In case of
Example 2.1 this requires at least one additional solve of the Poisson equation. #
3. A#ne invariance. Let -
be an arbitrary isomorphism. We
transform the x variable by
By. Thus, instead of (P) we study the whole class
of equivalent transformed minimization problems
By) subject to e( -
with the transformed solutions -
By Setting
I
# and G c (y,
By, #),
the first-order necessary optimality conditions have the form
Applying Algorithm 1 to (
OS) we get an equivalent sequence of transformed iterates.
Theorem 3.1. Suppose that Assumption 1 holds. Let
be the starting iterates for Algorithm 1 applied to the optimality conditions
(OS) and (
OS), respectively. Then both sequences of iterates are well-defined
and equivalent in the sense of
By
Proof. First note that the Fr-echet-derivative of the operator G c is given by
By, #). (3.3)
To prove (3.2) we use an induction argument. By assumption the identity (3.2) holds
Now suppose that (3.2) is satisfied for k # 0. This implies -
By
Using step b) of Algorithm 1 it follows that -
By
From (3.3),
we conclude that (#y, #)
Utilizing step d) of Algorithm 1 we get
the desired result.
Due to the previous theorem the augmented Lagrangian-SQP method is invariant
under arbitrary transformations -
B of the state space X . This nice property should,
of course, be inherited by any convergence theory and termination criteria. In -4 we
develop such an invariant theory.
Example 3.2. The usual local Newton-Mysovskii convergence theory (cf. [14,
p. 412]) is not a#ne invariant, which leads to an unsatisfactory description of the
domain of local convergence. Consider the optimization problem
subject to #
with unique solution x associated Lagrange multiplier
Note that the Jacobian #F 0 does not depend on # here, but only on
(#). In the context of Remark 2.5 we choose the neighborhood
6 S. VOLKWEIN AND M. WEISER
x
d)
c)
a)
x
x
Fig. 3.1. Illustration for Example 3.2. a) Contour lines of the cost functional, the constraint,
and the areas occupied by the other subplots. b) Neighborhood U(x # ) (gray) and Kantorovich ball of
theoretically assured convergence (white) for the original problem formulation. c) U(x # ) and Kantorovich
ball for the "better" formulation. d) U(x # ) and Kantorovich ball for the "better" formulation
plotted in coordinates of the original formulation.
Defining
the Newton-Mysovskii theory essentially guarantees convergence for all starting points
in the Kantorovich region
Here, # denotes the spectral norm for symmetric matrices and # 2 is the Euclidean
norm. For our choice of U , resulting in # 1.945 and a section of
the Kantorovich region at # is plotted in Figure 3.1-b). A di#erent choice of
coordinates, however, yields a significantly di#erent result. With the transformation
problem (3.4) can be written as
subject to
For the same neighborhood U , the better constants # 1.859 and result.
Again, a section of the Kantorovich region at # is shown in Figure 3.1-c).
Transformed back to (#) space, Figure 3.1-d) reveals a much larger domain of theoretically
assured convergence. This "better" formulation of the problem is, however,
not at all evident. In contrast, a convergence theory that is invariant under linear
transformations, automatically includes the "best" formulation. #
Remark 3.3. The invariance of Newton's method is not limited to transformations
of type (3.1). In fact, Newton's method is invariant under arbitrary transformations
of domain and image space, i.e., it behaves exactly the same for AF c
Because F c has a special gradient structure in the optimization
context, meaningful transformations are coupled due to the chain rule. Meaningful
transformations result from transformations of the underlying optimization problem,
i.e., transformations of the domain space and the image space of the constraints.
Those are of the type
x
# .
For such general transformations there is no possibility to define a norm in an invariant
way, since both the domain and the image space of the constraints are transformed
x). For this reason, di#erent types of transformations have
been studied for di#erent problems, see e.g. [6, 7, 10]. #
4. A#ne invariant convergence theory. To formulate the convergence theory
and termination criteria in terms of an appropriate norm, we use a norm that is
invariant under the transformation (3.1).
Definition 4.1. Let z # U . Then the norms # z : Z # R, z # U , are called
a#ne invariant for (OS), if
#F c (-z)#z# z
for all - z # U and #z # Z. (4.1)
We call {# z } z#U a #-continuous family of invariant norms for (OS), if
for every r, #z # Z and z # U such that z +#z # U . Using a#ne invariant norms
we are able to present an a#ne invariant convergence theorem for Algorithm 1.
Theorem 4.2. Assume that Assumption 1 holds and that there are constants
#-continuous family of a#ne invariant norms {# z } z#U , such
that the operator #F c satisfies
z
for s, # [0, 1], z # U , and #z # Z such that co{z, z +#z} # U , where co A denotes
the convex hull of A. For k # N let h
Suppose that h 0 < 2 and that the level set L(z 0 ) is closed. Then, the iterates stay in
U and the residuals converge to zero at a rate of
k .
8 S. VOLKWEIN AND M. WEISER
Additionally, we have
#F c (z k+1 )# z k #F c (z k )# z k . (4.5)
Proof. By induction, assume that L(z k ) is closed and that h k < 2 for k # 0. Due
to Remark 2.5 the neighborhood U is assumed to be convex, so that z
all # [0, 1]. From #F c (z k )#z we conclude that
ds
ds
for all # [0, 1]. Applying (4.2), (4.3), h
z k ds
holds. If z k +#z k
there exists an -
# [0, 1] such that z k
i.e.,
which is a contradiction. Hence, z k+1
z k /2.
Thus, we have h k+1 # h 2
closed, every Cauchy
sequence in L(z k+1 ) converges to a limit point in L(z k ), which is, by (4.4) and the
continuity of the norm, also contained in L(z k+1 ). Hence, L(z k+1 ) is closed. Finally,
using in (4.6), the result (4.5) is obtained.
Remark 4.3. We choose simplicity over sharpness here. The definition of the
level set L(z) can be sharpened somewhat by a more careful estimate of the term
Theorem 4.2 guarantees that lim k# h To ensure that z k
z # in Z as
k # we have to require that the canonical norm # Z
on Z can be bounded
appropriately by the a#ne invariant norms # z
Corollary 4.4. If, in addition to the assumptions of Theorem 4.2, there exists
a constant -
C > 0 such that
for all # Z and z # U,
then the iterates converge to the solution z
Proof. By assumption and Theorem 4.2 we have
Thus, {z k
} k#N is a Cauchy sequence in L(z 0 ) # U . Since L(z 0 ) is closed, the claim
follows by Remark 2.5-d).
For actual implementation of Algorithm 1 we need a convergence monitor indicating
whether or not the assumptions of Theorem 4.2 may be violated, and a termination
criterion deciding whether or not the desired accuracy has been achieved.
From (4.5), a new iterate z k+1 is accepted, whenever
#F c (z k+1 )# z k < #F c (z k )# z k . (4.7)
Otherwise, the assumptions of Theorem 4.2 are violated and the iteration is considered
as to be non-convergent. The use of the norm # z k for both the old and the new iterate
permits an e#cient implementation. Since in many cases the norm #F c (z k+1 )# z k is
defined in terms of #z derivative need not be evaluated
at the new iterate. If a factorization of #F c (z k ) is available via a direct solver, it can
be reused at negligible cost even if the convergence test fails. If an iterative solver
is used, #z k+1 in general provides a good starting point for computing #z k+1 , such
that the additional cost introduced by the convergence monitor is minor.
The SQP iteration will be terminated with a solution z k+1 as soon as
with a user specified tolerance TOL. Again, the use of the norm # z k allows an
e#cient implementation.
5. Invariant norms for optimization problems. What remains to be done
is the construction of a #-continuous family of invariant norms. In this section we
introduce two di#erent norms.
5.1. First invariant norm. The first norm takes advantage of the parameter c
in the augmented Lagrangian. As we mentioned in Remark 2.5, there exists a - c # 0
such that L # c (z) is coercive on X for all z # U and c # - c. Hence, the operator
belongs to B(Z) for all c # -
c.
Let us introduce the operator
I
# for all z # U and c # 0. (5.1)
Since L # c (z) is self-adjoint for all z # U , S c (z) is self-adjoint as well. Due to (2.3) the
operator S c (z) is coercive for all z # U and c # -
c. Thus, for all z # U
is a norm on Z for c # -
c.
Proposition 5.1. Let c # - c. Then, for every z # U the mapping
S. VOLKWEIN AND M. WEISER
defines an a#ne invariant norm for (2.2).
Proof. Let z # U be arbitrary. Since #S 1/2
defines a norm on Z for c # -
c and
#F c (z) is continuously invertible by Remark 2.6, it follows that # z is a norm on Z.
Now we prove the invariance property (4.1). Let -
L c denote the augmented Lagrangian
associated with the transformed problem (3.1). Then we have -
setting -
#r#
From (3.3) we conclude that
with
# U . Using (5.3) and (5.4) we obtain
which gives the claim.
In order to show the #-continuity (4.2) required for Theorem 4.2, we need the
following lemma.
Lemma 5.2. Suppose that c # - c and that there exists a constant # 0 such that
for all # Z, z # U and #z # Z such that z + #z # U . Then we have
where
Y
Proof. Let
# Z and z # U . From (5.1) and (5.2) we infer
By assumption S c (z) is continuously invertible. Utilizing the Lipschitz assump-
tion (5.5) the second additive term on the right-hand side can be estimated as
#.
Note that
Y
This implies
Inserting (5.7) into (5.6) the claim follows.
Proposition 5.3. Let all hypotheses of Lemma 5.2 be satisfied. Then {# z } z#U
is a #(3 )/2-continuous family of invariant norms with
#F c (z)# z (5.8)
for all # Z and z # U , where -
introduced in (2.3).
Proof. From (5.3) it follows that
We estimate the additive terms on the right-hand side separately. Using Lemma 5.2
we find
Applying (5.3) and (5.5) we obtain
Hence, using
12 S. VOLKWEIN AND M. WEISER
and it follows that {# z } z#U is a #(3 +C e )/2-continuous family of invariant norms.
Finally, from
z
Z
we infer (5.8).
5.2. Second invariant norm. In -5.1 we introduced an invariant norm provided
the augmentation parameter in Algorithm 1 satisfies c # - c. But in many
applications the constant - c is not explicitly known. Thus, L # c (x, #) -1 need not to be
bounded for c # [0, - c), so that S c (x, #) given by (5.1) might be singular. To overcome
these di#culties we define a second invariant norm that is based on a splitting
X , such that at least the coercivity of L # 0 (x, #) on ker e # (x) can be
utilized. Even though the thus defined norm can be used with larger value
of c may improve the global convergence properties - see [16, Section 2.3].
To begin with, let us introduce the bounded linear operator T c
Lemma 5.4. For every (x, # U and c # 0 the operator T c (x, #) is an isomorphism

Proof. Let r # X be arbitrary. Then the equation T c (x,
equivalent with
Due to Remark 2.6 the operator #F c (x, #) is continuously invertible for all (x, # U
and c # 0. Thus, # is uniquely determined by (5.9), and the claim follows.
We define the bounded linear operator R c
I
# for (x, # U and c # 0. (5.10)
Note that R c (x, #) is coercive and self-adjoint. Next we introduce the invariant norm
z
Y
for z # U and (r 1 , r 2 ) T
# Z. To shorten notation, we write #R c (z) 1/2 T c (z)
the first additive term.
Proposition 5.5. For every z # U the mapping given by (5.11) is an a#ne
invariant norm for (OS), which is equivalent to the usual norm on Z.
Proof. Let z # U be arbitrary. Since R c (z) is coercive and T c (z) is continuously
invertible, it follows that # z defines a norm which is indeed equivalent to the usual
norm on Z. Now we prove the invariance property (4.1). For (x,
By, # U we
have
I
# . (5.
Utilizing (3.3), (5.11) and (5.12) the invariance property follows.
The following proposition guarantees that {# z } z#U is a #-continuous family of
invariant norms for (OS).
Proposition 5.6. Suppose that there exists a constant # 0 such that
for all # Z, z # U and #z # Z such that z + #z # U . Then we have
For the proof of the previous proposition, we will use the following lemmas.
Lemma 5.7. With the assumption of Proposition 5.6 holding and z = (x, #) it
follows that
for all # ker e #
Proof. Let
Using (5.10)
and (5.11) we obtain
For all c # 0 the operator R c (z) is continuously invertible. Furthermore, R c (z) is
self-adjoint. Thus, applying (5.13) and
the second additive term on the right-hand side of (5.14) can be estimated as
Inserting this bound in (5.14) the claim follows.
Lemma 5.8. Let the assumptions of Theorem 5.6 be satisfied. Then
# z
for all r # X.
Proof. For arbitrary r # X we set # 1 , Using (5.9) and (5.13)
we estimate
# z
# z
14 S. VOLKWEIN AND M. WEISER
so that the claim follows.
Proof of Proposition 5.6. Let z, z Utilizing (5.11), Lemmas 5.7 and 5.8
we find
# z
# z
and therefore
z .
Hence, {# z } z#U is a 3#/2-continuous family of invariant norms.
Remark 5.9. Note that the Lipschitz constant of the second norm does not involve
C e and hence is independent of the choice of c. In contrast, choosing c too small may
lead to a large Lipschitz constant of the first norm and thus can a#ect the algorithm. #
Example 5.10. Let us return to Example 3.2. Using the second norm with
the theoretically assured, a#ne invariant domain of convergence is shown in Figure 5.1,
to be compared with Figures 3.1 b) and d). Its shape and size is clearly more similar
to the non-invariant domain of convergence for the "better" formulation, and, by
definition, does not change when the coordinates change. #
x
Fig. 5.1. Illustration for Examples 3.2 and 5.10. Neighborhood U(x # ) (gray) and a#ne invariant
domain of theoretically assured convergence (white).
5.3. Computational e#ciency. The a#ne invariance of the two norms developed
in the previous sections does not come for free: the evaluation of the norms is
more involved than the evaluation of some standard norm.
Nevertheless, the computational overhead of the first norm defined in -5.1 is
almost negligible, since it can in general be implemented by one additional matrix
vector multiplication. It requires, however, a su#ciently large parameter c.
On the other hand, the second norm defined in -5.2 works for arbitrary c # 0, but
requires one additional system solve with the same Jacobian but di#erent right hand
side. In case a factorization of the matrix is available, the computational overhead is
negligible - compare the CPU times of the exact Newton method in -7. If, however,
the system is solved iteratively, the additional system solve may incur a substantial
cost, in which case the first norm should be preferred.
5.4. Connection to the optimization problem. When solving optimization
problems of type (P), feasibility optimality are the relevant quan-
tities. This is well reflected by the proposed norms # z . Let z = (x, #) and
Using Taylor's theorem (see [19, p. 148]) and
the continuity of L # 0 , we obtain for the first norm
z
Y
Y
Y
Y
The second norm is based on the partitioning F c (x,
correspondingly on a splitting of the Newton correction into a optimizing direction
tangential to the constraints manifold and a
feasibility direction #F c (x, # 1 , we have for
z
Y
Y
Y
Y
Y
Recall that Thus, in the proximity of the solution, both a#ne
invariant norms measure the quantities we are interested in when solving optimization
problems, in addition to the error in the Lagrange multiplier and the optimizing
direction's Lagrange multiplier component, respectively.
6. Inexact augmented Lagrangian-SQP methods. Taking discretization
errors or truncation errors resulting from iterative solution of linear systems into
account, we have to consider inexact Newton methods, where an inner residual remains

z
Such inexact Newton methods have been studied in a non a#ne invariant setting by
Dembo, Eisenstat, and Steihaug [4], and Bank and Rose [1].
S. VOLKWEIN AND M. WEISER
With slightly stronger assumptions than before and a suitable control of the inner
residual, a similar convergence theory can be established as in -4.
Note that exact a#ne invariance is preserved only in case the inner iteration is
a#ne invariant, too.
Theorem 6.1. Assume that Assumption 1 holds and that there are constants
#-continuous family of a#ne invariant norms {# z } z#U , such
that the operator #F c satisfies
z (6.2)
for s, # [0, 1], z # U , and #z # Z such that z
and define the level sets
Suppose that z 0
# U and that L(z 0 ) is closed. If the inner residual r k resulting from
the inexact solution of the Newton correction (6.1) is bounded by
where
then the iterates stay in U and the residuals converge to zero as k # at a rate of
#F c (z k+1 )# z k+1 #F c (z k )# z k . (6.5)
Proof. Analogously to the proof of Theorem 4.2, one obtains
ds (6.6)
for all # [0, 1]. Using (6.6), (6.2), (4.2), and (6.3), we find for # [0, 1]
z k ds
z k
z k .
From (6.1) and (6.3) we have
and thus, setting # in (6.7) and #F c (z k )#z k
z k and using (6.4) it follows
that
From (6.4) we have #F c (z k )#z k
If z k+1
# U , then there is some # [0, 1] such that co{z k , z k
#/(2#F c (z k )# z k , which contradicts (6.10). Thus, z k+1
# U . Furthermore, inserting
and therefore L(z k+1 ) # L(z k ) is closed.
The next corollary follows analogously as Corollary 4.4.
Corollary 6.2. If, in addition to the assumptions of Theorem 6.1, there exists
a constant -
C > 0 such that
C#F c (z)# z
for all # Z and z # U , then the iterates converge to the solution z
of (OS).
For actual implementation of an inexact Newton method following Theorem 6.1
we need to satisfy the accuracy requirement (6.4). Thus, we do not only need an error
estimator for the inner iteration computing # k , but also easily computable estimates
[#] and [#] for the Lipschitz constants # and # in case no suitable theoretical values
can be derived. Setting in (6.6), we readily obtain
z k
and hence a lower bound
z k
#.
Unfortunately, the norms involve solutions of Newton type systems and therefore
cannot be computed exactly. Assuming the relative accuracy of evaluating the norms
are -
respectively, we define the actually computable estimate
S. VOLKWEIN AND M. WEISER
We would like to select a # k such that the accuracy matching condition (6.4) is
Unfortunately, due to the local sampling of the global Lipschitz constant
# and the inexact computation of the norms, the estimate [#] k is possibly too small,
translating into a possibly too large tolerance for the inexact Newton correction. In
order to compensate for that, we introduce a safety factor # < 1 and require the
approximate accuracy matching condition
to hold. An obvious choice for # would be (1
From Propositions 5.3
and 5.6 we infer that # is of the same order of magnitude as #. Thus we take the
estimate
currently ignoring C e when using the first norm.
Again, the convergence monitor (4.7) can be used to detect non-convergence. In
the inexact setting, however, the convergence monitor may also fail due to # k chosen
too large. Therefore, whenever (4.7) is violated and a reduction of # k is promising
(e.g.
, the Newton
correction should be recomputed with reduced # k .
Remark 6.3. If an inner iteration is used for approximately solving the Newton
equation (6.1) which provides the orthogonality relation (#z k , #z k
in a
scalar product (-) z k that induces the a#ne invariant norm, the estimate (6.11) can
be tightened by substituting
k . Furthermore, the norm #z k
of the exact Newton correction is computationally available, which permits the construction
of algorithms that are robust even for large inaccuracies # k . The application
of a conjugate gradient method that is confined to the null space of the linearized
constraints [2] to augmented Lagrangian-SQP methods can be the focus of future
research. #
7. Numerical experiments. This section is devoted to present numerical tests
for Example 2.1 that illustrate the theoretical investigations of the previous sections.
To solve (P) we apply the so-called "optimize-then-discretize" approach: we compute
an approximate solution by discretizing Algorithm 1, i.e., by discretizing the associated
system (2.6). In the context of Example 2.1 we have x
(#y, To reduce the size of the system we take
advantage of a relationship between the SQP steps #u, #v for the controls and the
SQP step # for the Lagrange multiplier. In fact, from
we infer that
of Algorithm 1. Inserting (7.1) into (2.6) we obtain
a system only in the unknowns (#y, #). Note that the second Fr-echet-derivative of
the Lagrangian is given by
. The solution (#y, #u, #v, #) of (2.6) is
computed as follows: First we solve
#y x (-,
#y x (-,
in# ,
- z in Q,
in# ,
y and #. Then we obtain #u and
#v from (7.1). For more details we refer the reader to [18].
For the time integration we use the backward Euler scheme while the spatial
variable is approximated by piecewise linear finite elements. The programs are written
in MATLAB, version 5.3, executed on a Pentium III 550 MHz personal computer.
Run 7.1 (Neumann control). In the first example we choose
The grid is given by
50 for
50 for
To solve (2.1) for we apply the Newton method at each time step. The
algorithm needs one second CPU time. The value of the cost functional is 0.081.
Now we turn to the optimal control problem. We choose and the
desired state is z(t, In view of the choice of z and the nonlinear
convection term yy x in (2.1b) we can interprete this problem as determining u in such
a way that it counteracts the uncontrolled dynamics which smoothes the discontinuity
at transports it to the left as t increases. The discretization of (7.2) leads
to an indefinite system
# . (7.3)
As starting values for Algorithm 1 we take y
S. VOLKWEIN AND M. WEISER
t-axis
x-axis
optimal
Optimal controls u (t) and v (t)
t-axis
Fig. 7.1. Run 7.1: residuum t #y(t, - z(t, -)# L
2(# and optimal controls.

Table
Run 7.1-(i): decay of #Fc (z k+1 )# z k for the first norm.
(i) First we solve (7.3) by an LU-factorization (MATLAB routine lu) so that
the theory of -4 applies. According to -4 we stop the SQP iteration if
In case #F c (z 0 )# z 0 is very large, the factor 10 -3 on the right-hand side of (7.4) might
be too big. To avoid this situation Algorithm 1 is terminated if (7.4) and, in addition,
holds. The augmented Lagrangian-SQP method stops after four iterations. The CPU
times for di#erent values of c can be found in Tables 7.6 and 7.7. Let us mention that
for the algorithm needs 102.7 seconds and for divergence
of Algorithm 1. As it was proved in [15] the set of admissible starting values reduces
whenever c enlarges. The value of the cost functional is 0.041. In Figure 7.1 the
residuum t #y(t, - z(t, -)# L
2(# for the solution of (2.1) for
as for the optimal state is plotted. Furthermore, the optimal controls are presented.
The decay of #F c (z k+1 )# z k , for the first invariant norm given by (5.3)
and for di#erent values of c is shown in Table 7.1. Recall that the invariant norm is
only defined for c # -
c. Unfortunately, the constant -
c # 0 is unknown. We proceed as
follows: Choose a fixed value for c and compute

Table
Run 7.1-(i): values of [#] k for di#erent c.

Table
Run 7.1-(i): decay of #Fc (z k+1 )# z k for the second norm.
in each level of the SQP iteration. Whenever [#] k is greater than zero, we have
coercivity in the direction of the SQP step. Otherwise, c needs to be increased. In

Table

7.2 we present the values for [#] k . We observed numerically that [#] k is positive
increased if c increased.
Next we tested the second norm introduced in (5.11) for Again, the augmented
method stops after four iterations and needs 97.4 seconds CPU time.
Thus, both invariant norms lead to a similar performance of Algorithm 1. The decay
of #F c (z k+1 )# z k can be found in Table 7.3.
(ii) Now we solve (7.3) by an inexact generalized minimum residual (GMRES)
method (MATLAB routine gmres). As a preconditioner for the GMRES method we
took an incomplete LU-factorization of the matrix
by utilizing the MATLAB function luinc(D,1e-03). Here, the matrix P is the discretization
of the heat operator y t - #y xx with the homogeneous Robin boundary
conditions #y x (-, The same preconditioner
is used for all Newton steps.
We chose # In -6 we introduced estimators for the constants # and
#, denoted by [#] k and [#] k , respectively. Thus, for k # 0 we calculate [#] k and [#] k ,
and then we determine # k+1 as follows:
while
do
For the first norm #F c (z k )#z k
z k is
already determined by the computation of the previous Newton correction. Thus we
have but in case of the second norm, #F c (z k )#z k
z k has to be calculated
with a given tolerance -
# k . In our tests we take -
# k for all k # 0. As starting
values we choose #
We test four strategies for the choice of -
for
It turns out that for -
we obtain the best performance with respect to CPU times. Hence, in the following
22 S. VOLKWEIN AND M. WEISER

Table
Run 7.1-(ii): decay of #Fc (z k )# z k for the first norm with #

Table
Run 7.1-(ii): values of [#] k for #
test examples we take #
The decay of #F (z k )# z k is presented in Table 7.4. Algorithm 1 stops after at most
seven iterations. Let us mention that for c the estimates [#] k for
the coercivity constant are positive. In particular, for the augmented
Lagrangian-SQP method has the best performance. In Table 7.5 the values of the
estimators [#] k are presented. In Table 7.6 the CPU times for the first norm are
presented. It turns out that the performance of the inexact method does not change
significantly for di#erent values of # k . Since we have to solve an additional linear
system at each level of the SQP iteration in order to compute the second norm, the
first norm leads to a better performance of the inexact method with respect to the
CPU time. Compared to part (i) the CPU time is reduced by about 50% if one
takes the first norm. In case of the second norm the reduction is about 45% for
7.7. Finally we test the inexact method
using decreasing # k . We choose # # 1. It turns out
that this strategy speeds up the inexact method for both norms, as can be expected
from the theoretical complexity model developed in [7].
Run 7.2 (Robin control). We choose
-10 in # 0, T
and y
The desired state was taken to be z(t,
(i) First we again solve (7.3) by an LU-factorization. We take the same starting
values and stopping criteria as in Run 7.1. The augmented Lagrangian-SQP method
stops after four iteration and needs 105 seconds CPU time. The discrete optimal
solution is plotted in Figure 7.2. From Table 7.8 it follows that (4.7) is satisfied
exact 97.5 96.8 96.9

Table
Run 7.1-(ii): CPU times in seconds for the first norm.
first norm second norm
exact 97.5 97.4

Table
Run 7.1-(ii): CPU times in seconds for both norms and
numerically. Let us mention that [#] 0 , . , [#] 3 are positive for c
For the needed CPU times we refer to Tables 7.10 and 7.11.
(ii) Now we solve (7.3) by an inexact GMRES method. As a preconditioner we
take the same as in Run 7.1. We choose # k. The decay of #F (z k )# z k is
presented in Table 7.9. As in part (i) we find that [#] k > 0 for all test runs. The needed
CPU times are shown in Tables 7.10 and 7.11. As we can see, the inexact augmented
Lagrangian-SQP method with GMRES is much faster than the exact one using the
LU-factorization. For the first norm the CPU time is reduced by about 55%, and
for the second norm by about 50% for # k # {0.3, 0.4, 0.5, 0.6, 0.7}. Moreover, for our
example the best choice for c is . For smaller values of # k the method does
not speed up significantly. As in Run 7.1 we test the inexact method using decreasing
# k . Again we choose # 1. As in Run 7.1, this
strategy speeds up the inexact method significantly for both norms. The reduction is
about 9% compared to the CPU times for fixed # k , compare Table 7.11.

Table
Run 7.2-(i): decay of #Fc (z k+1 )# z k for di#erent c.
S. VOLKWEIN AND M. WEISER0.501
-0.50.5t-axis
Optimal state y * (t,x)
-113Optimal controls u (t) and v * (t)
t-axis
Fig. 7.2. Run 7.2: optimal state and controls.

Table
Run 7.2-(ii): decay of #Fc (z k )# z k for #
exact 105.1 105.7 105.7

Table
Run 7.2-(ii): CPU times in seconds for the first norm.
first norm second norm
exact 105.1 105.5

Table
Run 7.2-(ii): CPU times in seconds for both norms and



--R

Global approximate newton methods
A subspace cascadic multigrid method for Mortar elements.
Mathematical Analysis and Numerical Methods for Science and Technology

Newton Methods for Nonlinear Problems.

Local inexact Newton multilevel FEM for nonlinear elliptic problems

Finite Element Methods for Navier-Stokes Equations
Inexact Gauss Newton Methods for Parameter Dependent Nonlinear Problems
Augmented Lagrangian-SQP-methods in Hilbert spaces and application to control in the coe#cient problems
Optimization by Vector Space Methods
First and second-order necessary and su#cient optimality conditions for infinite-dimensional programming problems
Iterative solution of nonlinear equations in several variables




Nonlinear Functional Analysis and its Applications
--TR

--CTR
Anton Schiela , Martin Weiser, Superlinear convergence of the control reduced interior point method for PDE constrained optimization, Computational Optimization and Applications, v.39 n.3, p.369-393, April 2008
S. Volkwein, Lagrange-SQP Techniques for the Control Constrained Optimal Boundary Control for the Burgers Equation, Computational Optimization and Applications, v.26 n.3, p.253-284, December
affine invariant norms;burgers' equation;nonlinear programming;multiplier methods