Global Convergence of Trust-region Interior-point Algorithms for Infinite-dimensional Nonconvex Minimization Subject to Pointwise Bounds.
A class of interior-point trust-region algorithms for infinite-dimensional nonlinear optimization subject to pointwise bounds in L p-Banach spaces, $2\le p\le\infty$, is formulated and analyzed. The problem formulation is motivated by optimal control problems with L p-controls and pointwise control constraints. The interior-point trust-region algorithms are generalizations of those recently introduced by Coleman and Li [SIAM J. Optim., 6 (1996), pp. 418--445] for finite-dimensional problems. Many of the generalizations derived in this paper are also important in the finite-dimensional context. All first- and second-order global convergence results known for trust-region methods in the finite-dimensional setting are extended to the infinite-dimensional framework of this paper.
Introduction
. This paper is concerned with the development and analysis
of a class of interior-point trust-region algorithms for the solution of the following
infinite-dimensional nonlinear programming problem:
minimize f(u)
subject to u
ae IR n is a domain with positive and finite Lebesgue measure
Moreover,
denotes the usual Banach space of real-valued measurable functions, and the objective
is continuous on an open neighborhood D ae U of B. All
pointwise statements on measurable functions are meant to hold -almost everywhere.
The lower and upper bound functions a;
are assumed to have a distance of at least - ? 0 from each other. More precisely,
This version was generated June 2, 1997.
y Institut f?r Angewandte Mathematik und Statistik, Technische Universit?t M-unchen, D-80290
M-unchen, Germany, E-Mail: mulbrich@statistik.tu-muenchen.de. This author was supported by
the DFG under Grant Ul157/1-1 and by the NATO under Grant CRG 960945.
z Institut f?r Angewandte Mathematik und Statistik, Technische Universit?t M-unchen, D-80290
M-unchen, Germany, E-Mail: sulbrich@statistik.tu-muenchen.de. This author was supported by
the DFG under Grant Ul158/1-1 and by the NATO under Grant CRG 960945.
x Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005-
This author was supported by the NSF under Grant DMS-
9403699, by the DoE under Grant DE-FG03-95ER25257, the AFSOR under Grant F49620-96-1-0329,
and the NATO under Grant CRG 960945.
M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
Problems of type (P) arise for instance when the black-box approach is applied to
optimal control problems with bound-constrained L p -control. See, e.g., the problems
studied by Burger, Pogu [3], Kelley, Sachs [14], and Tian, Dunn [20].
The algorithms in this paper are extensions of the interior-point trust-region
algorithms for bound constrained problems in IR N introduced by Coleman and Li [6].
Algorithmic enhancements of these methods have been proposed and analyzed in the
finite-dimensional context in Branch, Coleman, Li [2], Coleman, Li [5], and Dennis,
Vicente [11]. Dennis, Heinkenschloss, Vicente [10], and Heinkenschloss, Vicente [13]
extend these methods to solve a class of finite-dimensional constrained optimization
problems with bound constraints on parts of the variables. See also Vicente [23].
The interior-point trust-region methods in [6] are based on the reformulation of the
Karush-Kuhn-Tucker (KKT) necessary optimality conditions as a system of nonlinear
equations using a diagonal matrix D. This affine scaling matrix is computed using the
sign of the gradient components and the distance of the variables to the bounds. See
x 2. The nonlinear system is then solved by an affine-scaling interior-point method
in which the trust-region is scaled by
2 . These methods enjoy strong theoretical
convergence properties as well as a good numerical behavior. The latter is documented
in [2], [6], [10], [11] where these algorithms have been applied to various standard
finite-dimensional test problems and to some discretized optimal control problems.
The present work is motivated by the application of interior-point trust-region
algorithms to optimal control problems with bounds on the controls. Even though
the numerical solution of these problems requires a discretization and allows the application
of the previously mentioned algorithms to the resulting finite-dimensional
problems, it is known that the infinite-dimensional setting dominates the convergence
behavior if the discretization becomes sufficiently small. If the algorithm can
be applied to the infinite-dimensional problem and convergence can be proven in the
infinite-dimensional setting, asymptotically the same convergence behavior can be
expected if the algorithm is applied to the finite-dimensional discretized problems.
Otherwise, the convergence behavior might - and usually does - deteriorate fast as
the discretization is refined.
In the present context, the formulation of the interior-point trust-region algorithms
for the solution of the infinite-dimensional problem (P) requires a careful
statement of the problem and of the requirements on the function f . This will be
done in x 3. The infinite-dimensional problem setting in this paper is similar to the
ones in [12], [14], [15], [20]. The general structure of the interior-point trust-region
algorithms presented here is closely related to the finite-dimensional algorithms in
[6]. However, the statement and analysis of the algorithm in the infinite-dimensional
context is more delicate and has motivated generalizations and extensions which are
also relevant in the finite-dimensional context. The analysis performed in this paper
allows for a greater variety of choices for the affine scaling matrix and the scaling of
the trust-region than those presented previously in [6], [11]. Our convergence analysis
is more comprehensive than the ones in [5], [6], [11], [23]. In particular, we adapt
techniques proposed in Shultz, Schnabel, and Byrd [18] to prove that under mild assumptions
every accumulation point satisfies the second-order necessary optimality
conditions. Moreover, the convergence results proven in this paper extend all the
finite-dimensional ones stated in [17], [18], [19] to our infinite-dimensional context
with bound constraints. In the follow up paper [22] we present a local convergence
analysis of a superlinearly convergent affine-scaling interior-point Newton method
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 3
which is based on equation (13) and prove under appropriate assumptions that in a
neighborhood of the solution the generated trial steps are accepted by our trust-region
algorithms. There a projection onto the set B will be used in the computation of trial
steps. This extension to the finite-dimensional method, which was originally motivated
by the function space framework, has also led to significant improvements of the
finite-dimensional algorithm applied to some standard test problems, not obtained
from the discretization of optimal control problems. See [22].
Trust-region methods for infinite-dimensional problems like (P) have also been
investigated by Kelley, Sachs [15] and Toint [21]. In both papers the constraints are
handled by projections. The paper [21] considers trust-region algorithms for minimization
on closed convex bounded sets in Hilbert space. They are extensions of
the finite-dimensional algorithms by Conn, Gould, Toint [7]. It is proven that the
projected gradient converges to zero. A comprehensive finite-dimensional analysis of
trust-region methods closely related to those introduced by Toint can be found in
Burke, Mor'e, Toraldo [4]. In contrast to the results in [21], our convergence analysis is
also applicable to objective functions that are merely differentiable on a Banach space
which reduces the differentiability requirements substantially compared
to the L 2 -Hilbert space framework. Furthermore, for the problem class under
consideration our convergence results are more comprehensive than the ones in [21].
The infinite-dimensional setting used in [15] fits into the framework of this paper, but
is more restrictive. The formulation of their algorithm depends on the presence of a
penalty term ff
R\Omega in the objective function f and they assume
ae IR is
an interval. Their algorithm also includes a 'post smoothing' step, which is performed
after the trust-region step is computed. The presence of the post smoothing step ensures
that existing local convergence results can be applied. Such a 'post smoothing'
is not needed in the global analysis of this paper.
We introduce the following notations. L(X; Y ) is the space of linear bounded
operators from a Banach space X into a Banach space Y . By k \Delta k q we denote the
norm of the Lebesgue space L
and we write (\Delta; \Delta) 2 for the inner product
of the Hilbert space H
2(\Omega\Gamma2 For (v; w) 2 (L
denoting
the dual space of L
q(\Omega\Gamma9 we use the canonical dual pairing hv; wi
R\Omega v(x)w(x) dx,
for which, if q ! 1, the dual space L
is given by L q 0
(in the
case means q Especially, if
2(\Omega\Gamma and h\Delta; \Deltai
coincides with (\Delta; \Delta) 2 .
Finally, we set U 0
which is the same as U   , if p ! 1.
Moreover, it is easily seen that w 7\Gamma! h\Delta; wi defines a linear norm-preserving injection
from L 1
Therefore, we may always interpret U 0 as subspace of U   .
As a consequence of Lemma 5.1 we get the following chain of continuous imbeddings:
Throughout we will work with differentiability in the Fr'echet-sense. We write
for the gradient and r 2 f(u) 2 L(U; U   ) for the second derivative
of f at exist. The k \Delta k 1 -interior of B is denoted by B
We often
4 M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
This paper is organized as follows. In the next section we review the basics of
the finite-dimensional interior-point trust-region algorithms in [6] and use this to
motivate the infinite-dimensional setting applied in this paper. In x 3 we formulate
the necessary optimality conditions in the framework needed for the interior-point
trust-region algorithms. The interior-point trust-region algorithms are introduced in
x 4. Some basic technical results are collected in x 5. The main convergence results are
given in x 6, which concerns the global convergence to points satisfying the first-order
necessary optimality conditions, and in x 7, which concerns the global convergence to
points satisfying the second-order necessary optimality conditions. These convergence
results extend all the known convergence results for trust-region methods in finite
dimensions to the infinite-dimensional setting of this paper. The local convergence
analysis of these algorithms is given in the follow up paper [22], which also contains
numerical examples illustrating the theoretical findings of this paper.
2. Review of the finite-dimensional algorithm and infinite-dimensional
problem setting. We briefly review the main ingredients of the affine-scaling interior-point
trust-region method introduced in [6]. We refer to that paper for more details.
The algorithm solves finite-dimensional problems of the form
minimize f(u)
subject to u
is a twice continuously differentiable function and a ! b are
given vectors in IR N . (One can allow components of a and b to be \Gamma1 or 1, respec-
tively. This is excluded here to simplify the presentation.) Inequalities are understood
component wise.
The necessary optimality conditions for (PN ) are given by
a -
- a - 0; -
With the diagonal matrix defined by
ii
(1)
, the necessary optimality conditions can be rewritten as
a -
(2)
where the power r ? 0 is applied to the diagonal elements. This form of the necessary
optimality conditions - we choose can now be solved using Newton's method.
The i-th component of the function D(u) is differentiable except at points where
this lack of smoothness is benign since D(u) is multiplied by
rf(u). One can use
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 5
where J(u) is the diagonal matrix
ii
as the approximate derivative of D(u)rf(u). After symmetrization, one obtains
One can show that the standard second-order necessary optimality conditions are
equivalent to (2) and the positive semi-definiteness of -
M(-u). The standard second-order
sufficient optimality conditions are equivalent to (2) and the positive definiteness
of -
M(-u).
A point satisfying the necessary optimality conditions (2) is now computed using
the iteration u b, the trial step
is an approximate solution of
subject to k-sk 2
with -
. The trust-region radius \Delta k is updated
from iteration to iteration in the usual fashion. In (5) the Hessian r 2 f(u k ) might
be replaced by a symmetric approximation B k . If the approximate solution - s k of (5)
satisfies a fraction of Cauchy decrease condition
then under appropriate, standard conditions one can show the basic trust-region convergence
result
lim inf
Stronger convergence results can be proven if the assumptions on the function f and
on the step computation - s k are strengthened appropriately. See [6] and [5], [11].
Coleman and Li [6] show that close to nondegenerate KKT-points one obtains trial
steps -
s k which meet these requirements if one first computes an approximate solution
of (5) ignoring the bound constraints and then satisfies the interior-point condition
by a step-size rule. A careful analysis of the proofs in [6] unveils that
the same holds true for nearly arbitrary trust-region scalings. It becomes apparent
that the crucial role of the affine scaling does not consist in the scaling of the trust-region
but rather in leading to the additional term diag(rf k )J k in the Hessian -
of -
Near nondegenerate KKT-points this positive semi-definite diagonal-matrix
shapes the level sets of -
in such a way that all 'bad' directions - s which allow only
for small step-sizes to the boundary of the box cannot minimize -
/ k on any reasonable
trust-region. The trust-region scaling in (5), (6) tends to equilibrate the distance of
the origin to the bounding box constraints f-s :
g. However, for
this feature the equivalence of 2- and 1-norm is indispensable and thus it does not
carry over to our infinite-dimensional framework. In fact, in the infinite-dimensional
6 M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
setting the affine-scaled trust-region fk-sk no longer enjoys the property of
reflecting the distance to the bounding box constraints. Therefore we will allow for
a very general class of trust-region scalings in our analysis. See also [11]. Since, as
mentioned above, the term diag(rf k )J k in the Hessian -
plays the crucial role in
this affine-scaling interior-point all convergence results in [6] remain valid. It is also
worth mentioning that in our context an approximate solution -
s k of (5) satisfying (6)
can be easily obtained by applying any descent method which starts minimization at
along the steepest descent direction \Gamma -
k . Moreover, we show in [22] that near
an optimizer satisfying suitable sufficiency conditions admissible trial steps can be
obtained from unconstrained minimizers of -
projection onto B. Here
our flexibility in the choice of the trust-region scaling will prove to be valuable.
The finite-dimensional convergence analysis heavily relies on the equivalency of
norms in IR N . This is for example used to obtain pointwise estimates from
estimates. In the infinite-dimensional context the formulation of the algorithm
and the proof of its convergence is more delicate.
We will make use of the following Assumptions:
is differentiable on D with g mapping B ae U continuously into U 0 .
(A2) The gradient g satisfies g(B) ae V .
There exists c 1 ? 0 such that kg(u)k 1 - c 1 for all u 2 B.
f is twice continuously differentiable on D. If
for all u 2 B, and if converges to zero in all spaces L
then r 2 f(u)h k tends to zero in U 0 .
For the assumptions (A1) and (A4) simply say that f is continuously
Fr'echet-differentiable or that f is twice continuously Fr'echet-differentiable, respec-
tively. If then the requirements that g(u); r 2 f(u)h 2 U
is a further condition. It allows us to use estimates like hv; g(u)i -
1. Moreover, since on L
1(\Omega\Gamma the
norms coincide, assumption (A4) implies that r
also for Finally, (A1) ensures that the gradient g(u) is always at least an L 1 -
function which will be essential for many reasons, e.g. to allow the definition of a
function space analogue for the scaling matrix D.
The assumption (A2) is motivated by the choice of the scaling matrix D and the
fraction of Cauchy decrease condition (6) in the finite-dimensional case. The infinite-dimensional
analogue d(u) of the diagonal scaling matrix D(u) will be a function.
Given the definition (1) of D(u) it is to be expected that d(u) 2 L
(\Omega\Gamma8 Hence, the candidate for the Cauchy step
one will in general not be able
to find a scaling - ? 0 so that a ! u b. The assumption (A2) assures
that -
. The uniform boundedness assumption (A3) is, e.g., used
to derive the important estimate (26). We point out that in (A3) the uniform bound
on g(u) has to hold only for which is a bounded set in L
The conditions (A1)-(A4) limit the optimal control problems that fit into this
framework. However, a large and important class of optimal control problems with
these conditions. For example, the conditions imposed in [12,
p. 1270], [20, p. 517] to study the convergence of the gradient projection method
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 7
imply our assumptions (A1), (A2), and (A4). The assumption (A3) can be enforced
by additional requirements on the functions OE and S used in [12], [20]. The boundary
control problems for a nonlinear heat equation in [3] and in [14], [15] also satisfy the
assumptions (A1)-(A4). See [22].
3. Necessary optimality conditions and affine scaling. The problem under
consideration belongs to the class of cone constrained optimization problems in Banach
space for which optimality conditions are available (cf. [16]). But we believe that for
our particular problem an elementary derivation of the necessary optimality conditions
for problem (P) not only is simpler but also more transparent than the application of
the general theory. This derivation also helps us to motivate the choice of the affine
scaling which is used to reformulate the optimality condition and which is the basis
for the interior-point method.
3.1. First-order necessary conditions. The first-order necessary optimality
conditions in Theorem 3.1 are completely analogous to those for finite-dimensional
problems with simple bounds (cf. x 2, [6]). We only have to replace coordinatewise by
pointwise statements and to ensure that the gradient g(-u) is a measurable function.
Theorem 3.1 (First-order necessary optimality conditions). Let -
u be a
local minimizer of problem (P) and assume that f is differentiable at -
u with g(-u) 2 U 0 .
Then
2\Omega with
2\Omega with -
2\Omega with -
are satisfied.
Proof. Condition (O1) is trivially satisfied. To verify (O2), define
and assume that A \Gamma has positive measure is continuous from
below and A k
This yields a contradiction,
because -
d
d-
l
0:
Hence we must have In the same way we can show that -(A+
0g. Finally, we look at
Assume that -(I)
I
we can find l ? 0 with -(I l
8 M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
that - u
d
d-
l
a contradiction to the local optimality of -
u. Hence
means that (O2) holds.
3.2. Affine scaling. Let assumption (A1) hold. Our algorithm will be based on
the following equivalent affine-scaling formulation of (O2):
d r
arbitrary and d(u) 2 V , u 2 B, is a scaling function which is assumed
to satisfy
for all x 2 \Omega\Gamma The equivalence of (O2) and (7) will be stated and proved in Lemma
3.2. Before we do this, we give two examples of proper choices for d. The first choice
I is motivated by the scaling matrices used in [6] (see (1)). Except for points x
with those used in [6] and [11]:
d I (u)(x)
The slight modification in comparison to (1) will enable us to establish the valuable
relation (16) without a nondegeneracy assumption.
While the global analysis could be carried out entirely with this choice, the discontinuous
response of d(u)(x) to sign changes of g(u)(x) raises difficulties for the
design of superlinearly convergent algorithms in infinite dimensions. These can be
circumvented by the choice
and
and
It is easily seen that d = d I and d = d II both satisfy (8). An illustrative example
for the improved smoothness of the scaling function d II (u) will be given in x 4.1.
Lemma 3.2. Let (A1) hold and - u 2 B. Then (O2) is equivalent to (7) for all
r ? 0 and all d satisfying (8).
Proof. Since d r , r ? 0, also satisfies (8), we may restrict ourselves to the case
First assume that (O2) holds. For all x
2\Omega with
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 9
then -
In both cases On the
other hand, let hold. For all x
2\Omega with
2\Omega with -
would yield the contradiction d(-u)(x) ? 0. Analogously,
we see that g(-u)(x) - 0 for all x
2\Omega with - Therefore, (O2) holds.
3.3. Second-order conditions. If assumption (A4) holds, we can derive second-order
conditions which are satisfied at all local solutions of (P). These are also analogous
to the well known conditions for finite-dimensional problems.
Theorem 3.3 (Second-order necessary optimality conditions). Let
(A4) be satisfied and g(-u) 2 U 0 hold at the local minimizer -
u of problem (P). Then
are satisfied, where
2\Omega with - u(x) 2 fa(x); b(x)gg
denotes the tangent space of the active constraints.
Proof. Let the assumptions hold. As shown in Theorem 3.1, (O1) and (O2)
are satisfied. In particular, we have that
u). Now
assume the existence of s 2 T (B; -
I
and define restrictions s
I s, we get ks
1 . Hence, the restrictions s k converge to s in all spaces L
Therefore, tends to zero in U 0 by (A4) and, using the symmetry of
for all sufficiently large k. Let l ? 0 be such that hs l ; r 2 f(-u)s l i - \Gamma"=2. The
observations that s l 2 T (B; - u) and - u now yield the
desired contradiction:
d
d-
This readily shows that (O3) holds.
M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
4. The algorithm.
4.1. A Newton-like iteration. The key idea of the method to be developed
consists in solving the equation by means of a Newton-like method
augmented by a trust-region globalization. The bound constraints on u are enforced
by, e.g., a scaling of the Newton-like step. In particular, all iterates will be strictly
feasible with respect to the bounds: u
In general it is not possible to find a function d satisfying (8) that depends
smoothly on u. For an efficient method, however, we need a suitable substitute for
the derivative of dg. Formal application of the product rule suggests to choose an
approximate derivative of the form
with d u replacing the in general non-existing derivative of
at u. Here and in the sequel the linear operator D r (u), r - 0,
denotes the pointwise multiplication operator associated with d r (u), i.e.
continuously into itself. Moreover,
if the assumption (D2) below is satisfied and defines an automorphism
of L q
In fact, for all there exists
d such that
on\Omega by (D2). If we look at
the special case d = d I , the choice d u
I (u)w with
for
2\Omega seems to be the most natural.
For the general case this suggests the choice
is a multiplication operator, e(u) 2 V , which approximates
d u (u)g(u). Properties of E will be specified below.
We are now able to formulate the following Newton-like iteration for the solution
of
Given compute the new iterate u
(D
denotes a symmetric approximation of (or replacement for) r 2 f(u k ), i.e.
We assume that B k satisfies the following condition:
(A5) The norms kB k k U;U 0 are uniformly bounded by a constant c 2 ? 0.
In the following, we will not restrict our investigations to special choices of d and e.
Rather, we will develop an algorithm that is globally convergent for all affine scalings
d and corresponding e satisfying the assumptions (D1)-(D5):
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 11
(D1) The scaling d satisfies (8) for all u 2 B.
(D2) There exists ffi d ? 0 such that for all
2\Omega with
(D3) The scaling satisfies d(u)(x) - d I (u)(x) for all u 2 B, x
2\Omega and d I given by (9).
In particular, d(u)(x) - c d for some c d ? 0.
(D4) For all the function e(u) satisfies 0 - e(u)(x) - c e for all x
2\Omega and
(D5) The function e(u) is given by
c d 0 for all
We have seen that assumption (D1) is essential for the reformulation of the first-order
necessary optimality conditions and that (D2) ensures the continuous inverta-
bility of the scaling operator D(u) for Furthermore, assumption (D2) will be
used in the second-order convergence analysis. The assumption (D4) together with
(A5) is needed to ensure uniform boundedness of the Hessian approximations -
M k to be
defined later (see Remark 4.2). The assumption (D5) is needed to prove second-order
convergence results.
Obviously, (D1)-(D3) hold for either I and d = d II . The assumption (D4)
is satisfied for
I
(u)g(u), where d 0
I
(u) is given by (12), provided that kg(u)k 1
is uniformly bounded on B, i.e. provided that (A3) holds. The following example
illustrates that the relaxed requirements on the scaling function d can be used to
improve the smoothness of d and the scaled gradient dg substantially
Example 4.1. The quadratic function
is smooth on L 2 ([0; 1]). The gradient and the (strictly positive) Hessian are given by
Z 1v(x) dx:
f assumes its strict global minimum on the box
2g at the lower
bound - u, -
becomes negative for small x. Plot (a) in Figure 1 shows d I
(solid) and jg(u " )j (dotted) for 0:001. Note that d II is continuous at the sign-
change of retains its order of magnitude in contrast to d I . Plot (b) depicts
the remainder terms
dotted. Here d 0
i is as in (12).
Note that the remainder term for d I g does not tend to zero near the sign-change of
in contrast to d II g. In fact, it follows from our investigations in [22] that
for locally Lipschitz
at -
q(\Omega\Gamma is continuously differentiable in a neighborhood
of - u. Our example admits the choice
1 The advantages of the improved smoothness will be seen in the local convergence analysis [22].
M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
(a)
(b)
Fig. 1. Smoothness properties of the scaling functions d I (u) and d II (u)
4.2. New coordinates and symmetrization. Since neither the well-defined-
ness nor the global convergence of the Newton-like iteration (13) can be ensured, we
intend to safeguard and globalize it by means of a closely related trust-region method.
To this end we have to transform (13) into an equivalent quadratic programming
problem. While the iterates are required to stay strictly feasible with respect to the
bound constraints, we want to use an affine-scaling interior-point approach to reduce
the effect of the interfering bound constraints in the quadratic subproblem as far as
possible. The affine scaling can be expressed by a change of coordinates s ; - s and has
to be performed in such a way that we get enough distance from the boundary of the
box B to be able to impose a useful fraction of Cauchy decrease condition on the trial
step. An appropriate change of coordinates s
is arbitrary but fixed throughout the iteration. Performing this transformation and
applying D
k , the multiplication operator associated with d
k , from the left to (13)
leads to the equivalent equation
with
k , and -
k .
Remark 4.2. Assumptions (D4) and (A5) imply that k -
are uniformly
bounded by a constant c 3 ? 0.
M k is symmetric, - s k is a solution of (14) if and only if it is a stationary
point of the quadratic function
We will return to this issue later.
4.3. Second-order necessary conditions revisited. If B
the operator
also plays an important role in the second-order necessary optimality conditions. In
fact, we will show that if conditions (O1), (O2) hold at - u, then (O3) can be equivalently
replaced by
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 13
or even
The proof requires the following two lemmas.
Lemma 4.3. Let (D1) be satisfied, let g(-u) 2 U 0 , and suppose that (O1), (O2)
hold at - u. Then
I
Proof. The inclusion I ae I   is obvious from (8). Now let x 2 I   be given. Then
by (O2) and Lemma 3.2. From (8) we conclude -
Lemma 4.4. Let (D1) and (D4) be satisfied, let g(-u) 2 U 0 , and suppose that (O1),
(O2) hold at -
u. Moreover, assume that f is twice continuously differentiable at - u with
the statements (O3 0 ) and (O3 00 ) are equivalent.
Proof. Obviously ii) implies i). To show the opposite direction, assume that i)
holds. Set A
were I is the set defined in (16). For arbitrary s 2 V we perform
the splitting
4.3 implies that
d r (-u)s and we obtain
M(-u)s I i - 0:
This completes the proof.
Theorem 4.5. Let (D1), (D2), and (D4) be satisfied. Then in Theorem 3:3
condition (O3) can be equivalently replaced by (O3 0 ) or (O3 00 ).
Proof. Since the conditions of Theorem 3:3 and Lemma 4.4 guarantee that (O3 0 )
and (O3 00 ) are equivalent, we only need to show that (O3) can be replaced by (O3 0 ).
Let (O1), (O2) be satisfied. Then for all s 2 T (B; - u) we have To
show that (O3) implies (O3 0 ), let s 2 T (B; - u) be arbitrary. Then
contained in T (B; - u). Therefore, hs; -
To prove the opposite direction, assume that there exist s 2 T (B; -
with hs; r 2 f(-u)si ! \Gamma". As carried out in the proof of Theorem 3.3, we can find l ? 0
such that s
I l as defined in (11), satisfies hs l ; r 2 f(-u)s l i - \Gamma"=2.
Since d(-u) is bounded away from zero on I l by assumption (D2), we obtain that
I l
d \Gammar (-u)s is an element of T (B; - u) that satisfies hh; -
(note that by (D4)). This contradicts (O3 0 ).
with -
M(u) given by (15) and - g(u) (u)g(u). Note that -
. The
previous results show that -
/[-u](-s) is convex and admits a global minimum at -
u is a local solution of (P).
14 M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
4.4. Trust-region globalization. The results on the second-order conditions
in the previous section indicate that the Newton-like iteration (14) can be used locally
under appropriate conditions on B k . To globalize the iteration, we minimize -
the intersection of the ball k -
and the box B which leads to the following
trust-region subproblem:
Compute an approximate solution -
of
subject to k -
Here -
is a positive scaling function for the trust-region, see assumption (W)
below. As noted in x 2, the crucial contributions of the affine scaling are the term
E(u)D(u) in the Hessian -
M(u) and the scaling - g of the gradient. The trust-region
serves as a tool for globalization. Therefore, more general trust-region scalings can
be admitted, as long as they satisfy (W) below. This freedom in the scaling of the
trust-region will be important for the infinite-dimensional local convergence analysis
of this method. See [22].
We will work with the original variables in terms of which the above problem
reads
Compute as an approximate solution of
subject to kw k sk
with
k , and w
The only restriction on the trust-region scaling is that w \Gamma1
k as well as -
are
pointwise bounded uniformly in k:
(W) There exist c w ? 0 and c w 0 ? 0 such that kd r
all k.
Examples for w k are w
which yields a ball in the -
s-variables, and w
which leads to a ball in the s-variables. Both choices satisfy (W) if (D3) holds. See
also [11].
The functions d \Gammar
k and d \Gamma1
are only well defined if u . Therefore, the
condition
on the trial iterate is essential. However, it is important to
remark that the bound constraints do not need to be strictly enforced when computing
s k . For example, in the finite-dimensional algorithms in [6], [11], an approximate
solution of
subject to k -
is computed and then scaled by - k ? 0 so that
also apply in the infinite-dimensional framework. Practical choices for the infinite-dimensional
algorithm will be discussed in [22].
4.5. Cauchy decrease for the trial steps. An algorithm which is based on
the iterative approximate solution of subproblem (18) can be expected to converge to
a local solution of (P) only if the trial steps s k produce a sufficiently large decrease
of / k . A well established way to impose such a condition is the requirement that
the decrease provided by s k should be at least a fraction of the Cauchy decrease.
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 15
Here the Cauchy decrease denotes the maximum possible decrease along the steepest
descent direction of / k at with respect to an appropriate norm (or, equivalently,
appropriate coordinates) inside the feasible region of the subproblem. We will see in
Lemma 6.1 that the new coordinates -
indeed provide enough distance to the
boundary of B to allow the implementation of a useful Cauchy decrease strategy.
Unless in the Hilbert space case 2, the steepest descent direction of -
/ k at
is not given by the negative gradient \Gamma - g k but rather by any -
s d 6= 0 satisfying
h-s
On the other hand, if
k is the
-steepest descent direction of -
/ k at - This is a strong argument for choosing
this direction as basis for the Cauchy decrease condition. Of course this approach is
only useful if we ensure that u
sufficiently small which
can be done by imposing condition (A2) on g which is not very restrictive. Assuming
this, we may take \Gammad r
k as Cauchy decrease direction of / k , and therefore
define the following fraction of Cauchy decrease condition:
There exist fi; (fixed for all k) such that s k is an approximate solution of
(18) in the following sense:
(19a)
k is a solution of the one-dimensional problem
subject to
(19b)
4.6. Formulation of the algorithm. For the update of the trust-region radius
k and the acceptance of the step we use a very common strategy. It is based on the
demand that the actual decrease
ared
should be a sufficiently large fraction of the predicted decrease
pred
promised by the quadratic model. Since the model error is at most O(ks k k 2
p ), the
decrease ratio
ae k
ared
pred
will tend to one for s k ! 0. This suggests the following strategy for the update of the
trust-region radius:
Algorithm 4.6 (Update of the trust-region radius \Delta k ).
1. If ae k - j 1 then choose \Delta
2. If ae k 2 (j
3. If ae k 2 [j
4. If ae k - j 3 then choose \Delta
M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
Remark 4.7. The forms of predicted and actual decrease follow the choices used
in [11], [23] (and [10] for the constrained case). In [6] the decreases and the ratio are
computed as follows:
pred 1
ared
ared 1
pred 1
Since the crucial estimates (25) and (38) also are true for pred 1
the relations
pred 1
pred ared 1
hold, all convergence results presented in this paper remain valid if ae k is replaced by
k . We restrict the presentation to the choice (20), (21).
The algorithm iteratively computes a trial step s k satisfying the fraction of Cauchy
decrease condition. Depending on the decrease ratio ae k the trial step is accepted or
rejected, and the trust-region radius is adjusted.
Algorithm 4.8 (Trust-Region Interior-Point Algorithm).
Algorithm 4.6.
1. Choose u
2. For
2.1. If -
2.2. Compute
2.3. Compute ae k as defined in (22).
2.4. If ae k ? j 1 then set u
2.5. Compute using Algorithm 4.6.
5. Norm estimates. In this section we collect several useful norm estimates for
-spaces. The first lemma states that k \Delta k q 1
is majorizable by a multiple of k \Delta k q 2
if
Lemma 5.1. For all
2(\Omega\Gamma we have
with
Here 1=1 is to be interpreted as zero.
Proof. See e.g. [1, Thm. 2.8].
As a consequence of H-older's inequality we obtain the following result, which
allows us to apply the principle of boundedness in the high- and convergence in the
low-norm.
Lemma 5.2. (Interpolation inequality) Given 1 -
2(\Omega\Gamma the following
is true:
Proof. In the nontrivial cases
apply H-older's inequality:
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 17
The next lemma will be used in the proof of Lemma 7.1.
Lemma 5.3. For v 2 L
Proof.
6. Convergence to first-order optimal points. The convergence of the algorithm
is mainly achieved by two ingredients: A lower bound for the predicted decrease
for trial steps satisfying the fraction of Cauchy decrease condition, and the relation
ared pred k (s k ) which is always satisfied for successful steps s k . The lower
bound on the predicted decrease is established in the following lemma:
Lemma 6.1. Let the assumptions (A1), (A2), (D1)-(D4), and (W) hold. Then
there exists c 4 ? 0 such that for all u
satisfying (19) the
following holds:
pred
c 1\Gamma2r
d
d
Proof. Since C k is obviously positive by (D4), we have
pred
Now we will derive an upper bound for the minimum of OE(-
and
Therefore, using (D3),
\Gammad
d I (u k )(x)
d 1\Gamma2r
c 1\Gamma2r
d
c 1\Gamma2r
d
We have OE(-
M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
and observe
. Let -   be a minimizer for OE on [0; -
then
OE(-
If -
OE(-
If -  the same arguments
show
c 1\Gamma2r
d
The first inequality (24) now follows from these estimates and (19). The second
inequality (25) follows from (24) and the application
of Lemma 5.1. Note that p - 2 and 1=p 2.
Remark 6.2. The sequence of inequalities for the estimation of - B uses the
inequality d
d . This is where we need the restriction to r - 1=2.
Let the assumptions of Lemma 6.1 hold. If the kth iteration of Algorithm 4.8
is successful, i.e. ae k ? j 1 (or equivalently u k+1 6= u k ), then Lemma 6.1 provides an
estimate for the actual decrease:
d
If in addition the assumptions (A3) and (A5) hold, Remark 4.2 and the previous
inequality imply the existence of c 5 ? 0 with
d
The next statement is trivial:
Lemma 6.3. Let generated by Algorithm 4:8. If ae k - j 2 for
sufficiently large k then bounded away from zero.
Now we can prove a first global convergence result.
Theorem 6.4. Let assumptions (A1)-(A3), (A5), (D1)-(D4), and (W) hold. Let
the sequence (u k ) be generated by Algorithm 4:8. Then
lim inf
kd r
Even more:
lim inf
kd r
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 19
Proof. Assume that there are K ?
First we will show that this implies
1. If there is only a finite number
of successful steps then \Delta k+1 - large k and we are done. Otherwise, if the
sequence steps does not terminate, we conclude from f k # and the
boundedness of f that
For all use (26) and obtain, since k-g k i
tends to zero and, moreover, obeys the inequality
for all k i sufficiently large. This shows
! 1. Since for all successful steps
In a second step we will show that jae k \Gamma 1j ! 0. Due to
ks
and (27), (u k ) is a Cauchy sequence in U . Furthermore,fi fi fi fi / k
ks
The mean value theorem yields
jpred
converges in the closed set B, g is continuous, and
(see (28)) tend to zero, the first factor in the last expression converges to zero, too.
Lemma 6.1 garantees that jpred k (s k )j=\Delta k is uniformly bounded away from zero for
since by assumption k-g k k p 0 - ". This shows jae
yields a contradiction to Therefore, the assumption is wrong and the first
part of the assertion holds.
The second part follows from Lemma 5.1 for 1 - q - p 0 and from (A3) and the
interpolation inequality (23) for
Now we will show that if - g is uniformly continuous the limites inferiores in Theorem
6.4 can be replaced by limites.
We introduce the following assumptions:
(A6) The scaled gradient - uniformly continuous.
M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
uniformly continuous and d = d I or d = d II .
Condition (A6) is not so easy to verify for most choices of d. With Lemma 6.5,
however, we provide a very helpful tool to check the validity of (A6). Moreover, we
show in Lemma 6.6 that (A6 0 ) implies (A6). The proofs of both lemmas can be found
in the appendix. As a by-product of our investigations we get the valuable result
that - g inherits the continuity of g if we choose d = d I or d = d II . We will derive the
results concerning continuity and uniform continuity of -
simultaneously. Additional
requirements for the uniform continuity are written in parentheses.
Lemma 6.5. Let (A1)-(A3), (D3) hold and
continuous. Assume that k- fg(u)g(~u)?0g tends to zero (uniformly in
continuous.
Proof. See appendix.
The previous lemma is now applicable to the choices I and
Lemma 6.6. Let (A1)-(A3) hold and d = d I or d = d II . Then -
U \Gamma! U 0 is continuous. If, in addition, g is uniformly continuous, then the same is
true for -
g.
Proof. See appendix.
Now we state the promised variant of Theorem 6.4.
Theorem 6.7. Let assumptions (A1)-(A3), (A5), (D1)-(D4), (W), and (A6) or
the sequence (u k ) generated by Algorithm 4:8 satisfies
lim
kd r
Even more:
lim
kd r
Proof. Since, due to Lemma 6.6, - is uniformly continuous, it suffices to
show that under the assumption k-g k k p for an infinite number of iterations
there exists a sequence of index pairs (m
which is a contradiction to the uniform continuity of -
g.
us assume that (29) does not hold. Then there is " 1 ? 0 and a sequence (m i )
Theorem 6.4 yields a sequence
arbitrary
thus find a sequence (l i ) such that
and one has for all successful iterations
d
The left hand side converges to zero, because (f k ) is nonincreasing and bounded from
below, i.e. is a Cauchy sequence. We conclude that \Delta k tends to zero for successful
steps get with (28) that
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 21
which is clearly true also for unsuccessful iterations. Summing and using the triangle
inequality yields
Since (f k ) is a Cauchy sequence, the left hand side converges to zero for i !1. Hence,
l i
This is a contradiction to the uniform continuity of -
g. The second assertion follows as
in the proof of Theorem 6.4.
7. Convergence to second-order optimal points. The first-order convergence
results in the previous section could be shown under rather weak conditions on
the trust-region step s k and for arbitrary symmetric and bounded Hessian 'approxi-
mations'. If stronger assumptions are imposed on B k and on s k , then it can be shown
that every accumulation point of (u k ) satisfies the second-order necessary optimality
conditions. This will be done in this section. We need the following assumption on
the Hessian approximation:
(A7) For all accumulation points - u 2 U of (u k ) and all " ? 0 there is
such that ku
Obviously (A7) is satisfied if holds. However, (A7) also
applies in other important situations. For example, (A7) applies if f is a least squares
is the Gauss-Newton approximation of the Hessian.
The fraction of Cauchy decrease condition does not take into account any properties
of the quadratic part of / k . Apparently, this condition is too weak to guarantee the
positivity of -
M(-u) at accumulation points of (u k ). The decrease condition has to be
strengthened in such a way that for -
satisfying (O1) and (O2) but not (O3 00 ) there are
for all iterates u k with ku
For the finite-dimensional problem one can establish such an inequality near nondegenerate
points -
u by using techniques similar to those of Coleman and Li [6] if the s k
satisfy a finite-dimensional fraction of optimal decrease condition of the form
solves
subject to kw k sk 2 -
This approach is not directly transferable to our setting because the example
Z 1ts 2 (t) dt subject to ksk 2 - \Delta
shows that even in a Hilbert space s
k may not exist. Moreover, the proofs in [6] use
extensively a convenient characterization of s
k derived from the Karush-Kuhn-Tucker
conditions (cf. [19]) and the equivalence of 2- and 1-norm in IR N . Since, as shown by
(32), in Banach space the quadratic subproblem may not have a solution, this is not
applicable in our framework. Our convergence proof requires that the trial steps yield
22 M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
a fraction of the Cauchy decrease, and, moreover, a fraction of the decrease achievable
along directions of negative curvature of / k at convenience and simplicity of
notation, however, we favor a more intuitive but stronger fraction of optimal decrease
There exist fi; (fixed for all k) such that
(33a)
where
subject to
In the next lemma we show that in a neighborhood of an accumulation point -
u of
k ) at which (O1), (O2), but not (O3 00 ) hold, one can find a direction of negative
curvature h n of / k such that u k \Sigma h n 2 B.
Lemma 7.1. Let assumptions (A1), (A2), (A5), (A7), (D1)-(D5) hold and let the
sequence generated by Algorithm 4:8. Assume that -
is an accumulation
point of and that there are -
Then there exist "; ff; - ? 0 such that for all u k with ku
Proof. Since -
are satisfied due to Lemma 3.2.
Lemma 4.3 yields I
as in (D2). We first show that (34) implies the existence of ~ h 2 V with k ~ hk
From -
we see that I . We write v
for measurable functions v and measurable sets A ae \Omega\Gamma Then
holds for - h I instead of - h. Furthermore, using the symmetry
of -
M(-u) and the identity - h
Since the measure of I n I ffi can be made arbitrarily small by reducing
tends to zero for
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 23
Then (35) holds with ~
. Obviously, f ~ h 6= 0g ae I ffi . For " ? 0 and u k
with
~ h(x) d r (-u)(x)
d r
We have I h
I ffi and conclude from assumptions (D2) and (D3) that
c d on I h and " d (ffi=4) - d(-u)(x) - c d on I ffi , which implies that
d
From
I
Otherwise, due to Lemma 5.3, we can
make k ~ h I ffi nI h
-(I arbitrarily small by making " ? 0 small. Hence, in
all cases we can reduce " such that
By the definition of h and the fact that I h we get
d k- I h
M(-u) ~ hi
In the derivation of the last inequality we have used (35), (36), (37), and k ~ hk
We have already shown that k ~ h I ffi nI h
can be made arbitrarily small by making
small. By continuity the same is true for by (A7) for
"). Hence, there exist " ? 0 and - ? 0 such
that for all u k with ku
" we can carry out the above construction to obtain
M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
only depends on ffi , we get
In addition, we have by construction I h ae fx
and consequently
d
d r
Setting
d
and renorming h to unity completes the proof.
Now we establish the required decrease estimate.
Lemma 7.2. Let assumption (W) hold and s k satisfy (33). If for u k there exist
then
pred
Proof. The first inequality is obvious. Now let -; ff ? 0 be given. For all u k which
and choose the sign such that h-s n
assumption (W)
and
k is admissible for (33b) and can be used to get an upper
bound for / k (s k ): The fraction of optimal decrease condition (33) gives
-min
For a large class of trust-region algorithms for unconstrained finite-dimensional
problems Shultz, Schnabel, and Byrd [18] proposed a very elegant way to prove that
all accumulation points of the iterates satisfy the second-order necessary optimality
conditions. The key idea is to increase the trust-region radius after exceedingly successful
steps (case 4. in Algorithm 4.6). The following convergence theorem is an
analogue to [18, Thm 3.2].
Theorem 7.3. Let assumptions (A1)-(A7), (D1)-(D5), and (W) hold. Moreover,
let the sequence (u k ) be generated by the Algorithm 4:8 and let all s k satisfy (33). Then
every accumulation point -
satisfies the second-order necessary conditions
(O1)-(O3).
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 25
Proof. Let -
U be an accumulation point of u k . Then -
since
Theorem 6.7. Using Lemma 3.2, this
implies (O1) and (O2).
Now assume that (O3) does not hold at -
u. Then due to Theorem 4.5 there are
. Lemmas 7.1 and 7.2 yield
pred
choosing we achieve that for all k with
pred
Using this estimate, (A4), (A7), and ks k k p - fi 0 c w 0 \Delta k (see (28)) we find - possibly
after reducing " - with appropriate - k 2 [0; 1]
pred
ks
This shows ae k - j 3 for all k with
For all K ? 0 there is l ? K with In fact, since
u is an accumulation point of
eventually satisfies
. Hence, there is l - l 0 ? K with
\Delta, it is easily seen
that
1.
2. \Delta l - \Delta and there is m ? l such that ku
and
2.1
2.2
In case 1. we get
For 2.1. we have
26 M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
In case 2.2. we get \Delta k+1 -
and
k=l
k=l
ks
k=l
k=l
This yields
Therefore, we get for infinitely many steps k a decrease f of at least a constant
value which yields f k ! \Gamma1. This contradicts the boundedness of f on B, which
follows from (A1)-(A3). Thus, (O3) must hold at -
u.
8. Conclusions and future work. We have introduced and analyzed a globally
convergent class of interior-point trust-region algorithms for infinite-dimensional non-linear
optimization subject to pointwise bounds in function space. The methods are
generalizations of those presented by Coleman and Li [6] for finite-dimensional prob-
lems. We have extended all first- and second-order global convergence results that
are available for the finite-dimensional setting to our infinite-dimensional L p -Banach
space framework. The analysis was carried out in a unified way for
The lack of the equivalence of norms required the development of new proof tech-
niques. This is also a valuable contribution to the finite-dimensional theory because
our results are derived completely without using norm equivalences and hence are almost
independent of the problem dimension. In this sense our convergence theory can
be considered to be mesh-independent. Moreover, we have carried out our analysis
for a very general class of affine scaling operators, and almost arbitrary scaling of
the trust-region. This is new also from the finite-dimensional viewpoint. Numerical
results for optimal control problems governed by a nonlinear parabolic PDE which
prove the efficiency of our algorithms can be found in the forthcoming paper [22].
Furthermore, we present therein results for finite-dimensional standard test-examples
compiled in [8] which verify that a combination of the findings in this work and [22]
yield improvements also for finite-dimensional problems. Our investigations suggest
to incorporate a projection onto the box in the computation of approximate solutions
of the trust-region subproblems. This new technique was tested in an implementation
of the methods described in [10], [13], and [23], and proved to be superior to other
choices.
The results of this paper and [22] represent a first important step towards a
rigorous justification why trust-region interior-point and trust-region interior-point
SQP methods perform so well on discretized control problems. See [10], [13], and [22]
for applications. The extension of our theory to methods with additional equality
constraints is in progress.

Acknowledgements

. This work was done while the first and second author were
visiting the Department of Computational and Applied Mathematics and the Center
for Research on Parallel Computation, Rice University. They are greatly indebted
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 27
to John Dennis for giving them the opportunity to work in this excellent research
environment.
We would like to thank Richard Byrd, Colorado State University, and Philippe
Toint, Facult'es Universitaires Notre-Dame de la Paix, for pointing us to the second-order
convergence result in [18] which led to an improvement of generality and elegance
in our presentation. We also are grateful to John Dennis, Rice University, and Lu'is
Vicente, Universidade de Coimbra, for their helpful suggestions.
9.

Appendix

. In this section we present proofs of Lemma 6.5 and 6.6. These
proofs require the following three technical results:
Lemma 9.1. For
the following
holds:
Proof. For the assertion is trivial. For ff; fi - 0, use the
estimate
This estimate can be seen as follows. Due to symmetry we may assume that ff - fi - 0.
The function
and, thus, h(ff) - 0 for all ff - fi.
In the case the assertion follows immediately from (40). For
we use Lemma 5.1 to get
'Z\Omega
r dx
'Z\Omega
This completes the proof.
Lemma 9.2. For r the following inequality
holds:
Proof. In the case there is nothing to show. First we prove that for all
In fact, we
may assume ff - fi and compute
Therefore,
2\Omega
which immediately implies (41).
28 M. ULBRICH, S. ULBRICH, AND M. HEINKENSCHLOSS
Lemma 9.3. Let ff be arbitrary real numbers. Then
Proof. Without restriction, let fi g. Then
the assertion follows from
9.1. Proof of Lemma 6.5. We
ae\Omega measurable.
For arbitrary u; ~
0g. The triangle inequality
gives the following estimate
;\Omega nN
We use the fact that jg(u) \Gamma g(~u)j - jg(~u)j
on\Omega n N and obtain
Now the (uniform) continuity of - g follows from Lemma 9.1, Lemma 9.2, the (uniform)
continuity of g, and the assumption k-N (uniformly in u) on
the scaling.
9.2. Proof of Lemma 6.6. We restrict ourselves to the more complicated case
. The result follows from Lemma 6.5 if we verify that
(uniformly in u):
Let u; ~ arbitrary. Using symmetries, it is easily seen that we are done if
we are able to establish appropriate upper bounds for for the three
cases that g(u)(x) ? 0, g(~u)(x) ? 0 and
a) d II (u)(x) and d II (~u)(x) are both determined by the second case in (10),
b) d II (u)(x) and d II (~u)(x) are both determined by the else-case in (10),
c) d II (u)(x) is determined by the second and d II (~u)(x) by the else-case in (10).
We will use Lemma 9.3 several times.
Case a):
GLOBAL CONVERGENCE OF TRUST-REGION INTERIOR-POINT METHODS 29
Case b):
Case c): From
d II
d II
Therefore, we obtain
Otherwise, if g(~u)(x) -
u(x), we have in the case d II (u)(x) - d II (~u)(x) that
and for d II (u)(x) ! d II (~u)(x) we get
u(x)j:
Taking all cases together, this shows that
Now, the application of Lemma 6.5 shows that -
inherits the (uniform) continuity
of g.



--R

New York

Functional and numerical solution of a control problem originating from heat transfer

On the convergence of interior-reflective Newton methods for non-linear minimization subject to bounds

Global convergence of a class of trust region algorithms for optimization with simple bounds




On l 2 sufficient conditions and the gradient projection method for optimal control problems
Analysis of inexact trust-region interior-point SQP algorithms
Multilevel algorithms for constrained compact fixed point problems

First and second-order necessary and sufficient optimality conditions for infinite-dimensional programming problems

A family of trust region based algorithms for unconstrained minimization with strong global convergence properties
Newton's method with a model trust region modification
On the gradient projection method for optimal control problems with nonnegative L 2 inputs
Global convergence of a class of trust-region methods for nonconvex minimization in Hilbert space
Superlinear convergence of affine-scaling interior-point Newton methods for infinite-dimensional nonlinear problems with pointwise bounds

--TR

--CTR
Christian Kanzow , Andreas Klug, On Affine-Scaling Interior-Point Newton Methods for Nonlinear Minimization with Bound Constraints, Computational Optimization and Applications, v.35 n.2, p.177-197, October   2006
Matthias Heinkenschloss , Lus N. Vicente, An interface optimization and application for the numerical solution of optimal control problems, ACM Transactions on Mathematical Software (TOMS), v.25 n.2, p.157-190, June 1999
Christian Kanzow , Andreas Klug, An interior-point affine-scaling trust-region method for semismooth equations with box constraints, Computational Optimization and Applications, v.37 n.3, p.329-353, July      2007
optimal control;global convergence;interior-point algorithms;affine scaling;nonlinear programming;trust-region methods;infinite-dimensional optimization;bound constraints