Lipschitzian Stability for State Constrained Nonlinear Optimal Control.
For a nonlinear optimal control problem with state constraints, we give conditions under which the optimal control depends Lipschitz continuously in the  L2 norm on a parameter. These conditions involve smoothness of the problem data, uniform independence of active constraint gradients, and a coercivity condition for the integral functional. Under these same conditions, we obtain a new nonoptimal stability result for the optimal control in the $L^\infty$ norm. And under an additional assumption concerning the regularity of the state constraints, a new tight $L^\infty$ estimate is obtained. Our approach is based on an abstract implicit function theorem in nonlinear spaces.
Introduction
We consider the following optimal control problem involving a parameter:
minimize
subject to
where the state x(t) 2 R
dt x, the control u(t) 2 R m , the parameter p lies
in a metric space, the functions h
Throughout the paper, L ff (J denotes the usual Lebesgue space
of functions equipped with its standard norm
Z
is the Euclidean norm. Of course, corresponds to the space of
essentially bounded functions. Let W m;ff (J ; R n ) be the usual Sobolev space consisting
of vector-valued functions whose j-th derivative lies in L ff for all its norm
is
When either the domain J or the range R n is clear from context, it is omitted. We let
denote the space W m;2 , and Lip denote W 1;1 , the space of Lipschitz continuous
functions. Subscripts on spaces are used to indicate bounds on norms; in particular,
- denotes the set of functions in W m;ff with the property that the L ff norm of the
m-th derivative is bounded by -, and Lip - denotes the space of Lipschitz continuous
functions with Lipschitz constant -. Throughout, c is a generic constant, independent
of the parameter p and time t, and B a (x) is the closed ball centered at x with radius
a. The L 2 inner product is denoted h\Delta; \Deltai, the complement of a set A is A c , and the
transpose of a matrix B is B T . Given a vector y
yA denotes the subvector consisting of components associated with indices in A. And
then YA is the submatrix consisting of rows associated with indices in
A.
We wish to study how a solution to either (1), or to the associated variational
system representing the first-order necessary condition, depends on the parameter p.
We assume that the problem (1) has a local minimizer (x; corresponding
to a reference value of the parameter, and the following smoothness condition
holds:
Smoothness. The local minimizer (x   ; u   ) of (1) lies in W 2;1 \Theta Lip. There exists a
closed set \Delta ae R n \Theta R m and a
The function values and first two derivatives of f p (x; u), g p (x; u), and h p (x; u), and the
third derivatives of g p (x), with respect to x and u, are uniformly continuous relative
to p near p   and (x; u) 2 \Delta. And when either the first two derivatives of f p (x; u) and
or the first three derivatives of g p (x), with respect to x and u, are evaluated
at resulting expression is differentiable in t and the L 1 norm of the time
derivative is uniformly bounded relative to p near p   .
Let A, B, and K be the matrices defined by
Here and elsewhere the * subscript is always associated with p   . Let A(t) be the set
of indices of the active constraints at (x   (t); p   ); that is,
We introduce the following assumption:
Uniform Independence at A. The set A(0) is empty and there exists a scalar ff ? 0
such that
for each t 2 [0; 1] where A(t) 6= ; and for each choice of v.
Uniform Independence implies that the state constraints are first-order (see [12]
for the definition of the order of a state constraint). This condition can be generalized
to higher order state constraints (see Maurer [17]), however, the generalization of the
stability results in this paper to higher order state constraints is not immediate.
It is known (see, for instance, Theorem 7.1 of the recent survey [12] and the regularity
analysis in [8]), that under appropriate assumptions, the first-order necessary
conditions (Pontryagin's minimum principle) associated with a solution (x   ; u   ) of (1)
can be written in the following way: There exist /   2 W 2;1 and -   2 Lip such that
are a solution at of the variational system:
Here H p is the Hamiltonian defined by
and the set-valued map N is defined in the following way: Given a nondecreasing
Lipschitz continuous function -, a continuous function y lies in N(-) if and only if
Defining
where w  be the quadratic form
and let L be the linear and continuous operator from H 1 \Theta L 2 to L 2 defined by
We introduce the following growth assumption for the
quadratic form:
Coercivity. There exists a constant ff ? 0 such that
where
In the terminology of [12], the form of the minimum principle we employ is the
"indirect adjoining approach with continuous adjoint function." A different approach,
found in [13] for example, involves a different choice for the multipliers and for the
Hamiltonian. The multipliers in these two approaches are related in a linear fashion
as shown in [11]. Normally, the multiplier -, associated with the state constraint,
and the derivative of / have bounded variation. In our statement of the minimum
principle above, we are implicitly assuming some additional regularity so that - and
/ are not only of bounded variation, but Lipschitz continuous. This regularity can
be proved under the Uniform Independence and Coercivity conditions (see [8]).
In Section 3 we establish the following result:
Theorem 1.1. Suppose that the problem (1) with has a local minimizer
and that the Smoothness and the Uniform Independence conditions hold. Let
/   and -   be the associated multipliers satisfying the variational system (2)-(5). If the
Coercivity condition holds, then there exist a constant - and neighborhoods V of p   and
U of w  such that for every
is a unique solution U to the first-order necessary conditions (2)-(5)
with the property that ( -
u) is a local minimizer of the problem
(1) associated with p. Moreover, for every is the
corresponding solution of (2)-(5), the following estimate holds:
where
(w
kr
(w
In addition, we have
The proof of Theorem 1.1 is based on an abstract implicit function theorem appearing
in Section 2. In Section 4 we show that the L 1 estimate of Theorem 1.1
can be sharpened if the points where the state constraints change between active and
inactive are separated. In Section 5 we comment briefly on related work.
2. An implicit function theorem in nonlinear spaces
The following lemma provides a generalization of the implicit function theorem
that can be applied to nonlinear spaces. To simplify the notation, we let
denote the distance between the elements x and y of the metric space X.
Lemma 2.1. Let X and \Pi be metric spaces with X complete, let Y be a subset
of \Pi, and let P be a set. Given w   2 X and r ? 0, let W denote the ball B r (w   ) in
X and suppose that T (the subsets of \Pi) have the
following properties:
restricted to Y is single-valued and Lipschitz continuous, with Lipschitz
constant -.
there exists a unique w 2 W
such that T (w; p) 2 F (w). Moreover, for every denotes the w
associated with p i , then we have
Proof. Fix . Observe that
for each w a contraction on W with contraction constant
-ffl. Let w 2 W . Since w
Thus \Phi maps W into itself. By the Banach contraction mapping principle, there
exists a unique w 2 W such that is equivalent to
we conclude that for each there is a unique
have
Rearranging this inequality, the proof is complete.
Let X, Y , and P be metric spaces and let w   2 X. Using the terminology of [3],
strictly stationary at uniformly in p near p   , if for each
with the property that
for all w
Theorem 2.2. Let X be a complete metric space, let \Pi be a linear metric space,
let Y be a subset of \Pi, and let P be a metric space. Suppose that F :
continuous, and that for some w   2 X and
is continuous at p   .
strictly stationary at uniformly in p near p   .
restricted to Y is single-valued and Lipschitz continuous, with Lipschitz
constant -.
maps a neighborhood of (w   ; p   ) into Y .
Then for each -, there exist neighborhoods W of w   and P of p   such that for
each moreover, for every
denotes the w 2 W associated with p i , then we have
Proof. By (Q5) there exist neighborhoods U 0 of w   and P 0 of p   such that
We apply Lemma 2.1 with
the following identifications: X, Y , and \Pi are as defined in the statement of the
follow immediately from (Q1) and (Q4), respectively. Choose ffl ? 0 such that ffl !
that for this choice of ffl, we have ffl-
and By (Q3) and the identity T (w
exist neighborhoods
of w   such that (P3) of Lemma 2.1 holds. Let fi satisfy -fi=(1 \Gamma ffl- r and by (Q2),
choose P smaller if necessary so that (P2) holds. By Lemma 2.1, for each
exists a unique w 2 W such that T (w; p) 2 F (w), and the estimate (8) holds. Since
T (w; p) 2 F (w) if and only if T (w; p) 2 F(w), the proof is complete.
A particular case of Theorem 2.2 corresponds to the well-known Robinson implicit
function theorem [20] in which X is a Banach space, Y is its dual X   ,
N\Omega (w),
\Omega is a closed, convex set in X,
N\Omega (w) is the normal cone to the
set\Omega at the point
differentiable with respect to w, both T and its derivative rwT are continuous
in a neighborhood of (w   ; p   ), and
is the linearization of T . The Robinson framework is applicable to control problems
with control constraints after the range space X   is replaced by a general Banach
space Y (see the discussion in Section 5). However, for problems with state con-
straints, there are difficulties in applying Robinson's theory since stability results for
state constrained quadratic problems, analogous to the results for control constrained
problems, have not been established. In our previous paper [3], we extend Robinson's
work in several different directions. For the solution map of a generalized equation
in a linear metric space, we showed that Aubin's pseudo-Lipschitz property, that
the existence of a Lipschitzian selection, and that local Lipschitzian invertibility are
"robust" under nonlinear perturbations that are strictly stationary at the reference
point. In Theorem 2.2, we focus on the latter property, giving an extension of our
earlier result to nonlinear spaces. In this nonlinear setting, we are able to analyze the
state constrained problem, obtaining a Lipschitzian stability result for the solution.
3. Lipschitzian stability in L 2
To prove Theorem 1.1, we apply Theorem 2.2 using the following identifications.
First, we define
where
- (with the H 1 norm),
(with the L 2 norm), -(1) - 0 and -
An appropriate value for - is chosen later in the analysis. The space X consists of the
collection of functions x, /, u, and - satisfying (10) and (11) with the norm defined
in (10) and (11). Observe that the norms we use are not the natural norms. For
example, the u and - components of elements in X lie in W 1;1 , but we use the L 2
norm to measure distance. Despite the apparent mismatch of space and norm, X is
complete by Lemma 3.2 below.
The functions T and F of Theorem 2.2 are selected in the following way:
r
The continuous operator L is obtained by linearizing the map T (\Delta; p   ) in L 1 at the
reference point w  In particular,
denote the components of -   :
a
r
The space \Pi is the product L 2 \Theta L 2 \Theta L 2 \Theta H 1 while the elements - in Y have the
(with the L 2 norm), b 2 W 2;1 (with the H 1 norm),
ks
where - is a small positive constant chosen so that two related quadratic programs,
(37) and (41), introduced later have the same solution. As we will see, the constant -
associated with the space X must be chosen sufficiently large relative to -. Note that
the inverse is the solution (x; /; u; -) of the linear variational system:
Referring to the assumptions of Theorem 2.2, (Q1) holds by the definition of
X and by the minimum principle, (Q2) follows immediately from the Smoothness
condition. In Lemma 3.3, we deduce (Q3) from the Smoothness condition and a Taylor
expansion. In Lemma 3.6, (Q5) is obtained by showing that for w near w   and p near
its associated derivatives are near those of -
L(w   ). Finally, in a series of lemmas, (Q4) is established through manipulations of
quadratic programs associated with (15)-(18).
To start the analysis, we show that X is complete using the following lemma:
Lemma 3.1. If u 2 Lip - ([0; 1]; R 1 ), then we have
Proof. Since u is continuous, its maximum absolute value is achieved at some
on the interval [0; 1]. Let um the associated value of u. We
consider two cases.
Case 1: um ? -. Let us examine the maximum ratio between 1-norm and the
maximize fkukL 1=kuk
um ? -, the maximum is attained by the linear function v satisfying um
and -
\Gamma-. The 2-norm of this function is readily evaluated:
this interval, we have kvk 2
Taking square roots gives
which establishes the lemma in Case 1.
Case 2: um -. In this case, let us examine the maximum ratio between 1-norm
and the 2-norm to the 2/3-power:
maximize fkukL 1=kuk
The maximum is attained by the piecewise linear function v satisfying
it follows that
which completes the proof of case 2.
Lemma 3.2. The space X of functions w satisfying (9), (10), and (11), is
complete.
Proof. Suppose that w sequence in X. We analyze
the -component of w k . The sequence - k is a Cauchy sequence in L 1 by Lemma
3.1. Since L 1 is complete, there exists a limit point - 2 L 1 . Since the - k converge
pointwise to -
- and since each of the - k is Lipschitz continuous with Lipschitz constant
- is Lipschitz continuous with Lipschitz constant -. Since each of the - k is non-
decreasing, it follows from the pointwise convergence that - is nondecreasing; hence,
for each k, the pointwise convergence implies that -
This shows that the -component of X is complete. The other components can be
analyzed in a similar fashion.
Lemma 3.3. If the Smoothness condition holds, then for T and L defined in (12)
and strictly stationary at w   , uniformly in p near p   .
Proof. Only the first component of T (w; p) \Gamma L(w) is analyzed since the other
components are treated in a similar manner. To establish strict stationarity for the
first component, we need to show that for any given ffl ? 0,
for p near p   and for (x; u) and (y; v) 2 W 2;1
- \Theta Lip - near (x   ; u   ) in the norm of
(y; v) are also near (x   ; u   ) in L 1 . After writing the difference f p (x;
an integral over the line segment connecting (x; u) and (y; v), we have
where is the average of the gradient of f p along the line segment connecting
(x; u) and (y; v). By the Smoothness condition,
as p approaches p   and as both (x; u) and (y; v) approach (x   ; u   ) in L 1 . This
completes the proof.
Lemma 3.4. If the Smoothness condition holds, then for T and L defined in (12)
and (13) respectively, and for any choice of the parameter - ? 0 in (14), there exists
Proof. Again, we focus on the first component of T \Gamma L since the other components
are treated in a similar manner. Referring to the definition of Y , we should
show that
for p near p   and for (x; u) 2 W 2;1
- \Theta Lip - near (x   ; u   ) in the norm of H 1 \Theta L 2 . The
W 1;1 norm in (20) is composed of two norms, the L 1 norm of the function values,
and the L 1 norm of the time derivative. By the same expansion used in Lemma 3.3,
we obtain the bound
for p near p   and for (x; u) near Differentiating the expression within the
norm of (20) gives
d
By the Smoothness condition, -
A and -
lie in L 1 , and by the definition of X, we have
By the triangle inequality and by Lemma 3.1,
for x near x   . Moreover, by Lemma 3.1 and by the Smoothness condition, r x f p (x; u)
approaches A and r u f p (x; u) approaches B in L 1 as p approaches p   and (x; u)
approaches
dt
Analyzing each of the components of T \Gamma L in this same way, the proof is complete.
We now begin a series of lemmas aimed at verifying (Q4). After a technical
result (Lemma 3.5) related to the constraints, a surjectivity property (Lemma 3.6) is
established for the linearized constraint mapping. Then we study a quadratic program
corresponding to the linear variational system (15)-(18). We show that the solution
(Lemma 3.9) and the multipliers (Lemma 3.10) depend Lipschitz continuously on the
parameters. And utilizing the solution regularity derived in [8], the solution and the
multipliers lie in X for - sufficiently large.
To begin, let I be any map from [0; 1] to the subsets of f1; 2; with the
property that the following sets I i are closed for every i:
I
We establish the following decomposition property for the interval [0; 1]:
Lemma 3.5. If Uniform Independence at I holds, then for every ff
there exists sets J 1 , J 2 , \Delta \Delta \Delta, J l , corresponding points
a positive constant ae ! min i (- such that for each t 2 [-
we have I(t) ae J i , and if J i is nonempty, then
for every choice of v. The set J 1 can always be chosen empty.
Proof. For each t 2 (0; 1) with I(t) c 6= ;, there exists an open interval O centered
at t with O ae " i2I(t) cI
c
then we can choose a half-open interval O,
with t the closed end of the interval, such that O ae " i2I(t) cI c
. If I(t) c is empty, take
fixed t 2 [0; 1] with I(t) 6= ;, choose O smaller if necessary so that
for each s 2 O and for each choice of v. Since B and K are continuous, it is possible
to choose O in this way. Observe that by the construction of O, we have I(s) ae I(t)
for each s 2 O and (22) holds if I(t) is nonempty. Given any interval O on (0; 1), let
O 1=2 denote the open interval with the same center, but with half the length; for the
open intervals associated with denote the half-open interval with
the same endpoint, 0 or 1, but with half the length. The sets O 1=2 form an open cover
of [0; 1]. Let O 1 , O 2 , \Delta \Delta \Delta, O l be a finite subcover of [0; 1] and let t 1 ,
the associated centers of interior intervals, and the closed endpoint of the intervals
associated with or 1. It can be arranged so that no O i is contained in the
union of other elements of the subcover (by discarding these extra sets if necessary).
Arrange the indices of the O i so that the left side of O i is to the left of the left side
of O i+1 for each i. Let - 1 denote the successive left sides of the O i , and
let ae be 1/4 of the length of the smallest O i . Defining J
from the construction of the O i that I(t) ae J i and (22) holds for each t in an interval
associated with t i and with length twice that of O i . Since (-
By taking ae smaller if necessary, we can enforce the condition ae ! min i (-
Lemma 3.6. If Uniform Independence at I holds, then for each a 2 L 1 and
there exist x 2 W 1;1 and u 2 L 1 such that L(x; u)
and
This (x; u) pair is an affine function of (a; b), and for each ff - 1, there exists a
constant c ? 0 such that
for every (a is the pair associated with
Proof. We use the decomposition provided by Lemma 3.5 to enforce the equations
holds trivially on [-
that i ? 1, and let us consider (23) on the interval [-
we conclude that any j 2 I(t) is contained in either J
then by (27), (23) holds. If j 2 J i n J then by the construction of
the implies that (23) holds.
Suppose that j 2 J i and let oe j be any given Lipschitz continuous function. Observe
that if
d
dt
then K Carrying out the differentiation in the
second relation of (28) and substituting for -
x using the state equation (25), we obtain
a linear equation for u. By Lemma 3.5, this equation has a solution, and for fixed t
and x, the minimum norm solution can be written:
where
In the special case where J i is empty, we simply set u(t;
These observations show how to construct x and u in order to satisfy (26) and (27).
On the initial interval [0; - 2 ], u is simply 0 and x is obtained from (25). Assuming
x and u have been determined on the interval [0; - i ], their values on [- are
obtained in the following way: The control is given in feedback form by (29), where
For is linear on [-
With this choice for oe, the first equation in (28) is satisfied, and with x and u given
by (25) and (29) respectively, the second equation in (28) is satisfied. Also, by the
choice of oe,
for each
Hence, (26) and (27) hold, which yields (23).
For it follows from the definition of oe that
When u in (29) is inserted in (25) and this bound on j -
oe j (t)j is taken into account,
we obtain by induction that x 2 W 1;1 and u 2 L 1 . By the equations (25) for the
state, (29) for the control, and (31)-(32) for oe, (x; u) is an affine function of (a; b).
Moreover, the change (ffix; ffiu) in the state and control associated with the change
(ffia; ffib) in the parameters satisfies:
for each i where oe is specified in (31)-(32).
To complete the proof, we need to relate the oe term of (33) to the b term of (24).
For
Consequently, for almost every t 2 [-
us proceed by induction and assume that
Combining this with (34) and (33) for
Since jffix(- j+1 )j - kffixk W 1;ff [0;- j+1 ] , the induction step is complete.
In the following lemma, we prove a pointwise coercivity result for the quadratic
form B. See [4] and [7] for more general results of this nature.
Lemma 3.7. If Coercivity holds, then there exists a scalar ff ? 0 such that
xi] for all (x; u) 2 M; (35)
and
Proof. If Hence, the L 2 norm of x
and -
x are bounded in terms of the L 2 norm of u, and (35) follows directly from the
coercivity condition. To establish (36), we consider the control u ffl defined by
Let the state x ffl be the solution to
have
lim ffl!0
Combining this with the coercivity condition gives (36).
Consider the following linear-quadratic problem involving the parameters a, s,
minimize
subject to
If the feasible set for (37) is nonempty, then Coercivity implies the existence of a
unique minimizer over H 1 \Theta L 2 . Using the following lemma, we show that this minimizer
lies in W 1;1 \Theta L 1 , and that it exhibits stability relative to the L 2 norm.
Lemma 3.8. If Coercivity and Uniform Independence at I hold, then (37) has a
unique solution for every a; Moreover, the change (ffix; ffiu)
in the solution to (37) corresponding to a change (ffia; ffib; ffis; ffir) in the parameters
satisfies the estimate
Proof. By Lemma 3.6, Uniform Independence at I implies that the feasible set
for (37) is nonempty while the Coercivity condition implies the existence of a unique
solution From duality theory (for example, see [10]), there exists
with the property that is the minimum with respect to u of the
expression
h-
over all u 2 L 1 . It follows that
and by (36), u   (t) is uniformly bounded in t. From the equations L(x   ; u
x
The estimate (38) can be obtained, as in Lemma 5 in [2], by eliminating the
perturbation in the constraints. Let   be the affine map in Lemma 3.6 relating the
feasible pair (x; u) to the parameters (a; b). By making the substitution (x;
to an equivalent problem of the form
minimize
subject to
Here oe and ae are affine functions of a; b; s and r. Utilizing the Coercivity condition
and the analysis of [9, Sect. 2], we obtain the following estimate for the change
corresponding to the change (ffioe; ffiae):
2:
Hence,
Taking into account the relations between (x; u), (y; v), (oe; ae), and (a; b; s; r), the
proof is complete.
Now let us consider the full linear-quadratic problem where the subscript I on the
state constraint has been removed:
minimize
subject to
The first-order necessary conditions for this problem are precisely (15)-(18). Observe
that x   , u   , /   , and -   satisfy (15)-(18) when -   . Since the first-order necessary
conditions are sufficient for optimality when Coercivity holds, (x   ; u   ) is the unique
solution to (41) at -   . In addition, if Uniform Independence holds, we now show
that the multipliers / and - satisfying (16)-(18) are unique; hence, x   , u   , /   , and
-   are the unique solution to (15)-(18) for -   .
To establish this uniqueness property for the multipliers, we apply Lemma 3.5
to the active constraint map A of Section 1. Let J i be the index sets associated
with the complementary
slackness condition -   (1) T g   associated with the condition (5) of the minimum
principle, implies that (-   ) J c
l
along with (16) and (17)
imply that (-   ) J l
and /   are uniquely determined on [- l ; 1]. Proceeding by induction,
suppose that /   and -   are uniquely determined on the interval [-
is constant on [- it is uniquely determined by the continuity of -   , while (-
and /   on [- are uniquely determined by (21), (16), and (17). This completes
the induction step.
We now use Lemma 3.8 to show that the solution to (41) depends Lipschitz continuously
on the parameters when Coercivity and Uniform Independence at A hold.
We do this by making a special choice for the map I. Again, let J i be the index sets
associated with I = A by Lemma 3.5. Since A(t) ae J i for each t 2 [- the
parameter
is strictly positive for each i. Setting in the case I = A ffl
where A ffl (t) is the index set associated with the ffl-active constraints for the linearized
problem:
Since A ffl (t) ae J i for each t 2 [- implies that Uniform Independence
at A ffl holds.
We now observe that the solution (x   ; u   ) of (41) at -   is the solution of
(37) for I = A ffl and -   . First, (x   ; u   ) is feasible in (37) since there are fewer
constraints than in (41). By the choice I = A ffl , all feasible pairs for (37) near
are also feasible in (41). Since (x   ; u   ) is optimal in (41), it is locally optimal in (37) as
well, and by the Coercivity condition and Lemma 3.7, (x   ; u   ) is the unique minimizer
of (37) for -   . By Lemma 3.8, we have an estimate for the change in the solution
to (37) corresponding to a change in the parameters. Since kffixk L 1 - kffixk H 1, it
follows that for small perturbations in the data, the solution to (37) is feasible, and
hence optimal, for (41). Hence, our previous stability analysis for (37) provides us
with a local stability analysis for (41). We summarize this result in the following way:
Lemma 3.9. If Coercivity and Uniform Independence at A hold, then for s, r,
and a in an L 1 neighborhood of s   , r   , and a   respectively, and for b in a W 1;1
neighborhood of b   , there exists a unique minimizer of (41), and the estimate (38)
holds. Moreover, taking I = A ffl with defined in (42), the
solutions to (37) and (41) are identical in these neighborhoods.
Now let us consider the multipliers associated with (41):
Lemma 3.10 If Coercivity and Uniform Independence at A hold, then for s, r,
and a in an L 1 neighborhood of s   , r   , and a   respectively, and for b in a W 1;1
neighborhood of b   , there exists a unique minimizer of (41) and associated unique
multipliers satisfying the estimate:
Proof. Let A ffl be the ffl-active constraints defined by (43), where
Let J i be the index sets and let ae be the positive number associated with
by Lemma 3.5. Consider -   small enough that the active
constraint set for (41) is a subset of A ffl (t) for each t. By the same analysis used
to establish uniqueness of (/   ; -   ), there exists unique Lagrange multipliers (/;
corresponding to -   + ffi-. We will show that
Combining this with Lemma 3.9 yields Lemma 3.10.
We prove (45) by induction. Let us start with the interval [- l \Gamma ae; 1]. If i 2 J c
l ,
l
Multiplying (17)
by KB, we can solve for ffi- J l
and substitute in (16) to eliminate -. Since
it follows that
for
Proceeding by induction, suppose that (46) holds for we wish to show
that it holds for
is constant on [- and we have
ae
Combining this with (46) for
for multiplying (17) by KB, we solve for ffi- J j and substitute in (16).
the induction bound (46) for coupled with
the bound already established for ffi- i ,
This completes
the induction.
Lemma 3.11. Suppose that Smoothness, Coercivity, and Uniform Independence
at A hold and let - be small enough that Y is contained in the neighborhoods of
Lemmas 3.9 and 3.10. Then for some - ? 0 and for each - 2 Y , there exists a unique
solution (x; u) to (41) and associated multipliers (/; -) satisfying the estimates (38)
and (44), (x; /; u;
Proof. If the first-order
necessary conditions (15)-(18) associated with (41). Lemmas 3.9 and 3.10 tell us
that the unique solution and multipliers for (41) satisfy the estimates (38) and (44)
for - near -   . Since the first-order necessary conditions are sufficient for optimality
when Coercivity holds, the variational system (15)-(18) has a unique solution, for -
near -   , that is identical to the solution and multipliers for (41), and the estimates
(38) and (44) are satisfied.
To complete the proof, we need to show that -
This follows from the regularity results of [8], where it is shown that the
solution to a constant coefficient, linear-quadratic problem satisfying the Uniform
Independence condition and with R positive definite, Q positive semidefinite, and
has the property that the optimal u and associated - are Lipschitz continuous
in time while the derivatives of x and / are Lipschitz continuous in time. Moreover,
the Lipschitz constant in time is bounded in terms of the constant ff in the Uniform
Independence condition and the smallest eigenvalue of R. Exactly the same analysis
applies to a linear-quadratic problem with time-varying coefficients, however, the
bound for the Lipschitz constant of the solution depends on the Lipschitz constant
of the matrices of the problem and of the parameters a, r, s, and -
b, as well as on a
uniform bound for the smallest eigenvalue of R(t) on [0; 1] and for the parameter ff
in the Uniform Independence condition. By Lemma 3.9, and with the choice for I
given in the statement of the lemma, the quadratic programs (37) and (41) have the
same solution for s, r, and a in an L 1 neighborhood of s   , r   , and a   , and for b in
a W 1;1 neighborhood of b   . Hence, for parameters in this neighborhood of -   , the
indices of the active constraints are contained in I(t) for each t, and the independence
condition (21) holds. Lemma 3.7 provides a lower bound for the eigenvalues of R(t).
If (a; s; then the Lipschitz constants for a, s, r, and - b are bounded by those
for a   , s   , r   , and -
b   plus -. Hence, taking - sufficiently large, the proof is complete.
Proof of Theorem 1.1. We apply Theorem 2.2 with the identifications given
at the beginning of this section, and with - chosen sufficiently large in accordance
with Lemma 3.11. The completeness of X is established in Lemma 3.2, (Q1) is
immediate, (Q2) follows from Smoothness, (Q3) is proved in Lemma 3.3, (Q4) follows
from Lemma 3.11, and (Q5) is established in Lemma 3.4. Applying Theorem 2.2, the
estimate (7) is established. Under the Uniform Independence condition, Coercivity is
a second-order sufficient condition for local optimality (see [4], Theorem 1) which is
stable under small changes in either the parameters or the solution of the first-order
optimality conditions. Finally, we apply Lemma 3.1 to obtain the L 1 estimate of
Theorem 1.1.
We note that the Coercivity condition we use here is a strong form of a second-order
sufficient optimality condition; it not only provides optimality, but also guarantees
Lipschitz continuity of the optimal solution and multipliers when Uniform
Independence holds. As recently proved in [6] for finite-dimensional optimization
problems, Lipschitzian stability of the solution and multipliers necessarily requires a
coercivity condition stronger than the usual second-order condition. For the treatment
of second-order sufficient optimality under conditions equivalent to Coercivity,
see [18] and [21]. These sufficient conditions can be applied to state constraints of
arbitrary order. For recent work concerning the treatment of second-order sufficient
optimality in state constrained optimal control, see [16], [19], and [22].
4. Lipschitzian stability in L 1
One way to sharpen the L 1 estimate of Theorem 1.1 involves an assumption
concerning the regularity of the solution to the linear-quadratic problem (41). The
time t is a contact point for the i-th constraint of Kx+ b - 0 if (K(t)x(t)
and there exists a sequence ft k g converging to t with (K(t k )x(t k
each k.
Contact Separation: There exists a finite set I 1 I N of disjoint, closed intervals
contained in (0; 1) and neighborhoods of (a   ; r   ; s   ) in W 1;1 and of b   in W 2;1
with the property that for each a, r, s, and b in these neighborhoods, and for each
solution to (41), all contact points are contained in the union of the intervals I i with
exactly one contact point in each interval and with exactly one constraint changing
between active and inactive at this point.
Observe that if for (1) with there are a finite number of contact points,
at each contact point exactly one constraint changes between active and inactive,
and each contact point in the linear-quadratic problem (41) depends continuously
on the parameters, then Contact Separation holds. The finiteness of the contact set
is a natural condition in optimal control; for example, in [5] it is proved that for a
linear-quadratic problem with time invariant matrices and one state constraint, the
contact set is finite when Uniform Independence and Coercivity hold.
Theorem 4.1. Suppose that the problem (1) with has a local minimizer
that Smoothness, Contact Separation, and Uniform Independence at A
hold. Let /   and -   be the associated multipliers satisfying the first-order necessary
conditions (2)-(5). If the Coercivity condition holds, then there exist neighborhoods
V of p   and U of w  such that for every
there exists a unique solution U to the first-order necessary
conditions (2)-(5) and (x; u) is a local minimizer of the problem (1) associated with
p. Moreover, for every is the corresponding
solution of (2)-(5), the following estimate holds:
To prove this result, we need to supplement the 2-norm perturbation estimates
provided by Lemmas 3.9 and 3.10 with analogous 1-norm estimates.
Lemma 4.2. If Coercivity, Uniform Independence at A, and Contact Separation
hold, then there exist neighborhoods of (a   ; r   ; s   ) in W 1;1 and of b   in W 2;1 such that
for each a in these neighborhoods, the associated solutions
c(kffiak
Proof. Letting A ffl denote the ffl-active set defined in (43), we again choose
defined in (42). We consider parameters a, r, s, and b chosen
within the neighborhoods of the Contact Separation condition, and sufficiently close
to a   , r   , s   , and b   that the active constraint set for the solution of the perturbed
linear-quadratic problem (41) is contained in A ffl (t) for each t. By eliminating the
perturbations in the constraints, as we did in the proof of Lemma 3.8, there is no
loss of generality in assuming that a We refer to the quadratic program
corresponding to the parameters (r Problem 2.
Let (x; u) be either is a time for which K i
for some i, then d
Substituting for -
x using the state equation
for u using the necessary condition (17) yields:
This equation has the form
for suitable choices of the row vectors N i , S i , T i , and U i . Hence, at any time t where
the change in solution and multipliers corresponding to
a change in parameters satisfies the equation
By the Contact Separation condition, Problems 1 and 2 have the same active
set near 1. Since the components of - corresponding to inactive constraints
are constant and since - i
The relation (49) combined with Uniform
Independence, with the L 2 estimates provided in Lemmas 3.9 and 3.10, and with a
bound for the L 1 norm in terms of the H 1 norm, gives
Using the bound (36) of Lemma 3.7 in (17) and applying Gronwall's lemma to (16),
we have
for all t ! 1 in some neighborhood of As t decreases, this estimate is valid until
the first contact point is reached for either Problem 1 or Problem 2. Proceeding by
induction, suppose that we have established (51) up to some contact point; we now
wish to show that (51) holds up to the next contact point.
Again, by the Contact Separation condition, there is precisely one constraint,
say constraint j, that makes a transition between active and inactive at the current
contact point. Suppose that on the interval (ff; fi), the active sets for Problems 1 and
differ by the element j, and let - for the first contact point to the left of ff for either
Problem 1 or Problem 2. If there is no such point, we take By the Contact
Separation condition, the difference ff \Gamma - is uniformly bounded away from zero for
all choices of the parameters s and r near s   and r   . There are essentially two cases
to consider.
Case 1: Constraint j is active in Problem 2 to the left of
active in Problem 1 to the left of
Case 2: Constraint j is active in Problem 2 to the right of
is active in Problem 1 to the right of
Case 1. Since constraint j is active in both Problem 1 and 2 at
from (49) and from the Uniform Independence condition that
is the set of indices of active constraints at
on (ff; fi), the induction hypothesis yields
Hence, we have
is constant in Problem 1 on (ff; fi), and since it is monotone in Problem 2,
the bound (53) coupled with the bound (51) at implies that
Since ffi- i is constant on (ff; fi) for it follow from (51) that
Relation (49), for along with (54) and (55) yield
Combining (54)-(56) gives
On the interval from to the next contact point - , precisely the same
constraints are active in both Problems 1 and 2. Again, the relation (49) combined
with Uniform Independence, with the L 2 estimates provided in Lemmas 3.9 and 3.10,
and with a bound for the L 1 norm in terms of the H 1 norm gives
Relation (50) for along with (57) and (58), give
And combining this with (15)-(17) gives (51) for This completes the induction
step in Case 1.
Case 2. The mean value theorem implies that for some fl 2 (-; ff), we have
d
dt
Hence, even though the derivative of K j x i may not vanish on (-; ff), the derivative
of the change K j ffix is still bound by the perturbation in the parameters at some
d
dt
Since ff and - lie in disjoint closed sets I k associated with the Contact Separation
bounded away from zero by the distance between the closest pair
of sets. Focusing on the left side of (59), we substitute ffi -
substitute for ffiu using (17) to obtain the relation
where denote the set of indices of the
active constraints at Combining (60) with (49) for
The analysis for Case 1 can now be applied, starting with (52), but with ff replaced
by fl.
Remark 4.3. In the proof of Lemma 4.2, we needed to ensure that the difference
appearing in case 2, was bounded away from zero. The Contact Separation
condition ensures that this difference is bounded away from zero since ff and - lie in
disjoint closed intervals I k . On the other hand, any condition that ensures a positive
separation for the contact points ff and - in case 2 can be used in place of the Contact
Separation assumption of Theorem 4.1 and Lemma 4.2.
Proof of Theorem 4.1. The functions T , F , and L and the sets X, \Pi, and Y are
the same as in the proof of Theorem 1.1 except that L 2 is replaced by L 1 and H 1 is
replaced by W 1;1 everywhere. Except for this change in norms, and the replacement
of the L 2 estimates (38) and (44) referred to in Lemma 3.11 by the corresponding
estimate (47) of Lemma 4.2, the same proof used for Theorem 1.1 can be used to
establish Theorem 4.1.
5. Remarks
As mentioned in Section 2, Theorem 2.2 is a generalization of Robinson's implicit
function theorem [20] to nonlinear spaces. His theorem assumes that the nonlinear
term is strictly differentiable and that the inverse of the linearized map is Lipschitz
continuous. In optimal control, the latter condition amounts to Lipschitz continuity in
1 of the solution-multiplier vector associated with the linear-quadratic approxima-
tion. For problems with control constraints, this property for the solution is obtained,
for example, in [1] or [4].
In this paper, we obtain Lipschitzian stability results for state constrained problems
utilizing a new form of the implicit function theorem applicable to nonlinear
spaces. We obtain optimal Lipschitzian stability results in L 2 and nonoptimal stability
results in L 1 under the Uniform Independence and the Coercivity conditions.
And with an additional Contact Separation condition, we obtain a tight L 1 stability
result. These are the first L 1 stability results that have been established for state
constrained control problems.
The Uniform Independence condition was introduced in [8] where it was shown
that this condition together with the Coercivity condition yield Lipschitz continuity
in time of the solution and the Lagrange multipliers of a convex state and control
constrained optimal control problem. Using Hager's regularity result, Dontchev [1]
proved that the solution of this problem has a Lipschitz-type property with respect
to perturbations. Various extensions of these results have been proposed by several
authors. A survey of earlier results is given in [2].
In a series of papers (see [14], [15], and the references therein), Malanowski studied
the stability of optimal control problems with constraints. In [15] he considers an
optimal control problem with state and control constraints. His approach differs
from ours in the following ways: He uses an implicit function theorem in linear spaces
and a compactness argument, and the second-order sufficient condition he uses is
different from our coercivity condition. Although there are some similar steps in the
analysis of L 2 stability, the two approaches mainly differ in their abstract framework.
A prototype of Lemma 3.5 is given in [1], Lemma 2.5. Lemma 3.6 is related to
Lemma 3 in [2], although the analysis in Lemma 3.6 is much simpler since we ignore
indices outside of A(t). In the analysis of the linear-quadratic problem (37), we follow
the approach in [4].

Acknowledgement

. The authors wish to thank both Kazimierz Malanowski
for his comments on an earlier version of this paper, and the reviewers for their
constructive suggestions.



--R


Lipschitzian stability in nonlinear control and optimization
An inverse function theorem for set-valued maps

On regularity of optimal control
Characterizations of strong regularity for variational inequalities over polyhedral convex sets
Variants of the Kuhn-Tucker sufficient conditions in cones of nonnegative functions
Lipschitz continuity for constrained processes
Multiplier methods for nonlinear optimal control
Dual approximations in optimal control
Lagrange duality theory for convex control problems
A survey of the maximum principles for optimal control problems with state constraints
Theory of Extremal Problems

Stability and sensitivity of solutions to nonlinear optimal control problems
Sufficient optimality conditions in optimal control
On the minimum principle for optimal control problems with state constraints
First and second order sufficient optimality conditions in mathematical programming and optimal control
Second order sufficient conditions for optimal control problems with control-state constraints
Strongly regular generalized equations
Sufficient conditions for nonconvex control problems with state constraints
The Riccati equation for optimal control problems with mixed state- control constraints
--TR

--CTR
Stephen J. Wright, Superlinear Convergence of a Stabilized SQP Method to a Degenerate Solution, Computational Optimization and Applications, v.11 n.3, p.253-275, Dec. 1998
Olga Kostyukova , Ekaterina Kostina, Analysis of Properties of the Solutions to Parametric Time-Optimal Problems, Computational Optimization and Applications, v.26 n.3, p.285-326, December
W. Hager, Stabilized Sequential Quadratic Programming, Computational Optimization and Applications, v.12 n.1-3, p.253-273, Jan. 1999
D. Goldfarb , R. Polyak , K. Scheinberg , I. Yuzefovich, A Modified Barrier-Augmented Lagrangian Method for Constrained Minimization, Computational Optimization and Applications, v.14 n.1, p.55-74, July 1999
optimal control;state constraints;lipschitzian stability;implicit function theorem