Uniqueness of extremals for problems with endpoint and control constraints
JAVIER F ROSENBLUETH
IIMAS, Universidad Nacional Aut´onma de M´exico Apartado Postal 20-126, CDMX 01000
MEXICO jfrl@unam.mx
Abstract:In this paper we study the uniqueness of extremals satisfying first order necessary conditions for optimal control problems involving endpoint and control constraints. In particular we show that, for such problems, a strict Mangasarian-Fromovitz type constraint qualification does imply uniqueness of Lagrange multipliers but, contrary to the corresponding equivalence in mathematical programming, the converse in optimal control may not hold.
Key–Words:Optimal control, uniqueness of Lagrange multipliers, normality, constraint qualifications
1 Introduction
It is well-known that, for nonlinear programming problems involving equality and inequality con- straints, a strict version of the Mangasarian-Fromovitz constraint qualification (SMFCQ) is equivalent to the uniqueness of multipliers satisfying the Karush-Kuhn- Tucker conditions (or first order Lagrange multiplier rule). Moreover, that strict constraint qualification im- plies the satisfaction of second order necessary opti- mality conditions on a critical cone which takes into account the sign of the multipliers.
For the statement on uniqueness of multipliers we refer the reader to [1, 3, 4, 6, 9], while the result on necessary conditions can be seen with detail in [2, 6, 8, 9].
The equivalence between uniqueness of multipli- ers and the SMFCQ was first established in [9] and has been widely quoted (see, for example, [1, 3, 4–6, 12–
14] and references therein). The proof of that result, found in [9], is strongly based on yet another equiva- lence between the Mangasarian-Fromovitz constraint qualification (MFCQ) and normality relative to the original set of constraints, a crucial result which has been proved by Hestenes [8] or, as mentioned in [6, 9], by using theorems of alternative (see Motzkin in [6, Theorem 2.4.19]). Here, the notion of normality is used in the sense that, if the cost multiplier vanishes in the Fritz John necessary optimality condition, then the only solution of the corresponding first order system is the null solution. Thus, normality of a local mini- mizer relative to the original set of constraints implies, in the necessary optimality condition, a positive cost multiplier.
Due to this last equivalence, the SMFCQ (which
is really the MFCQ applied to a subset of the set of tangential constraints) is equivalent to normality rela- tive to a subset of the original set of constraints which depends on Lagrange multipliers given beforehand, and includes inequalities when the multipliers vanish and equalities otherwise.
In this paper, we shall deal with an optimal control problem involving endpoint and control con- straints, and pose the question of uniqueness of mul- tipliers satisfying first order necessary conditions as a consequence of a maximum principle.
As we shall see, the notion of normality follows essentially the same principles as in the finite dimen- sional case, and there is a natural correspondence with the sets of constraints mentioned above. However, we shall prove that, for this type of optimal control prob- lems, uniqueness of the Lagrange multipliers and nor- mality relative to the corresponding subset of the set of original constraints are no longer equivalent.
2 Nonlinear programming
In this section, we shall give a brief summary of the main results given in [9] relating the SMFCQ with uniqueness of Lagrange multipliers and second order necessary optimality conditions. This will help us to clearly understand some of the main differences be- tween the finite dimensional case and that of optimal control.
Consider the problem, which we shall label (N), of minimizing f on S, where f, gi: Rn → R (i ∈ A ∪ B) are given C1functions, A = {1, . . . , p}, B =
{p + 1, . . . , m}, and
S = {x ∈ Rn| gα(x) ≤ 0 (α ∈ A), gβ(x) = 0 (β ∈ B)}.
Denote by Λ(f, x0) the set of all λ ∈ Rm (whose components λ1, . . . , λm are the Kuhn-Tucker or Lagrange multipliers) satisfying the Karush-Kuhn- Tucker (KKT) conditions:
i. λα ≥ 0 and λαgα(x0) = 0 (α ∈ A).
ii. If F (x) := f (x) + hλ, g(x)i then F0(x0) = 0.
Here, the function F is the standard Lagrangian, g is the function mapping Rnto Rm whose components are g1, . . . , gm, and h·, ·i is the standard inner product in Rmso that hλ, g(x)i =Pm1 λigi(x).
Under a suitable constraint qualification, the KKT conditions hold at a local minimum x0of (N), that is, if x0 affords a local minimum to f on S and a con- straint qualification holds, then Λ(f, x0) 6= ∅. It is important to mention that, as shown in [6–8], if
I(x) = {α ∈ A | gα(x) = 0}
denotes the set of active indices at x, and
RS(x0) := {h ∈ Rn| g0α(x0; h) ≤ 0 (α ∈ I(x0)), gβ0(x0; h) = 0 (β ∈ B)}
is the set of vectors satisfying the tangential con- straintsat x0(or the linearized tangent cone), then
Λ(f, x0) 6= ∅ ⇔ f0(x0; h) ≥ 0 for all h ∈ RS(x0).
Constraint qualifications can also be seen as con- ditions which assure the positiveness of the cost mul- tiplier λ0 in the Fritz John necessary optimality con- dition which states that, if x0 solves (N) locally, then there exist λ0 ≥ 0 and λ ∈ Rm, not both zero, such that
i. λα ≥ 0 and λαgα(x0) = 0 (α ∈ A).
ii. If F0(x) := λ0f (x)+hλ, g(x)i then F00(x0) = 0.
Based on the theory of augmentability, a simple proof of this result is provided in [10], while the proof given in [6] uses Motzkin theorem of the alternative. It yields in a natural way the following constraint quali- fication.
We shall say that x ∈ S is normal relative to S if λ = 0 is the only solution of
i. λα ≥ 0 and λαgα(x) = 0 (α ∈ A).
ii. Pm1 λig0i(x) = 0.
Clearly, the normality condition is a constraint quali- fication since, in the Fritz John theorem, if x0 is also
a normal point of S, then λ0 > 0 and the multipli- ers can be chosen so that λ0 = 1, thus implying that Λ(f, x0) 6= ∅.
As shown in [6, 8], normality of a point x0 rela- tive to S is equivalent to the Mangasarian-Fromovitz constraint qualification atx0with respect toS, which requires the linear independence of the set
{gβ0(x0) | β ∈ B}
and the existence of h such that
gα0(x0; h) < 0 (α ∈ I(x0)), gβ0(x0; h) = 0 (β ∈ B).
Now, suppose λ ∈ Λ(f, x0). Let S1(λ) := {x ∈ S | F (x) = f (x)}.
Note that, if Γ = {α ∈ A | λα > 0}, then S1[ = S1(λ) ] =
{x ∈ Rn| gα(x) ≤ 0 (α ∈ A, λα = 0), gβ(x) = 0 (β ∈ Γ ∪ B)} = {x ∈ S | gα(x) = 0 (α ∈ Γ)}.
Therefore
RS1(x0) =
{h ∈ Rn| gα0(x0; h) ≤ 0 (α ∈ I(x0), λα= 0), gβ0(x0; h) = 0 (β ∈ Γ ∪ B)} =
{h ∈ RS(x0) | g0α(x0; h) = 0 (α ∈ Γ)} = {h ∈ RS(x0) | f0(x0; h) = 0}.
The strict Mangasarian-Fromovitz constraint qualification at x0 corresponds to MFCQ at x0 with respect to S1(λ). In other words, x0 ∈ Rnsatisfies the SMFCQ if the set
{gβ0(x0) | β ∈ Γ ∪ B}
is linearly independent, and there exists h such that g0α(x0; h) < 0 (α ∈ I(x0), λα= 0),
g0β(x0; h) = 0 (β ∈ Γ ∪ B).
Let us now state and give a (simple) proof of the main result given in [9] relating the SMFCQ with the uniqueness of Lagrange multipliers.
Theorem 1 Suppose λ ∈ Λ(f, x0). Then the follow- ing are equivalent:
a. x0satisfiesSMFCQ.
b. λ is unique in Λ(f, x0).
Proof: As mentioned before, (a) is equivalent to nor- mality of x0 relative to S1(λ), that is, µ = 0 is the only solution of
1. µα≥ 0 and µαgα(x0) = 0 (α ∈ A, λα = 0).
2. Pm1 µigi0(x0) = 0.
(a) ⇒ (b): Let ¯λ ∈ Λ(f, x0) and set µ := ¯λ − λ.
Then µ satisfies (1) and (2) since µα= ¯λα≥ 0,
µαgα(x0) = ¯λαgα(x0) = 0 (α ∈ A, λα = 0) and, if ¯F (x) := f (x) + h¯λ, g(x)i, then
0 = ¯F0(x0) − F0(x0) =
m
X
1
µig0i(x0).
By (a), µ = 0 and so λ = ¯λ.
(b) ⇒ (a): ∼(a) ⇒ ∼(b): Assume x0is not a nor- mal point of S1(λ). Then there exists µ ∈ Rm, µ 6= 0, satisfying (1) and (2) and such that
max{|µα| : α ∈ K} < min{λα: α ∈ K}
where
K = {α ∈ I(x0) | λα> 0}.
Let ˆλ := λ + µ. Let us prove that ˆλ ∈ Λ(f, x0) implying ∼(b) since ˆλ 6= λ. Indeed, if
F (x) := f (x) + hˆˆ λ, g(x)i, then we have
Fˆ0(x0) = F0(x0) +
m
X
1
µigi0(x0) = 0
and so (ii) in the definition of Λ(f, x0) holds. To prove that also (i) holds, let α ∈ A. If gα(x0) = 0 then λˆαgα(x0) = 0. If gα(x0) < 0 then, by (i) with respect to λ, we have λα= 0 and so, by (1),
0 = µαgα(x0) = ˆλαgα(x0).
Finally, if λα = 0, then ˆλα= µα≥ 0. If λα > 0 then λˆα = λα+ µα
≥ min
i∈Kλi+ µα
> max
i∈K |µi| + µα≥ 0.
If we assume that the functions delimiting the problem are C2, second order necessary conditions can be derived under the assumption of SMFCQ (or normality relative to S1) at a local minimum of the problem. A proof of this result can be found in [2, 8].
Theorem 2 Suppose x0 ∈ S and λ ∈ Λ(f, x0). If x0 solves(N) locally and is a normal point of S1(λ), then F00(x0; h) ≥ 0 for all h ∈ RS1(x0).
3 Extremals and normality in opti- mal control
The optimal control problem we shall deal with can be stated as follows. Suppose we are given an interval T := [t0, t1] in R, a point ξ0 ∈ Rn, and functions
(g, h): Rn→ R × Rk(k ≤ n), (L, f ): T × Rn× Rm→ R × Rn,
ϕ: Rm→ Rq(q ≤ m).
Denote by X the space of piecewise C1 functions mapping T to Rn, by Ukthe space of piecewise con- tinuous functions mapping T to Rk(k ∈ N), and set Z := X × Um,
The set of endpoint constraints will be expressed in terms of
C := {x ∈ Rn| h(x) = 0},
and the set of control constraints will be given by U := {u ∈ Rm | ϕα(u) ≤ 0 (α ∈ R),
ϕβ(u) = 0 (β ∈ Q)}
where R = {1, . . . , r} and Q = {r + 1, . . . , q}.
Define the sets
D := {(x, u) ∈ Z | ˙x(t) = f (t, x(t), u(t)) (t ∈ T ), x(t0) = ξ0, x(t1) ∈ C},
S := {(x, u) ∈ D | u(t) ∈ U (t ∈ T )}, and let I: Z → R be given by
I(x, u) := g(x(t1)) + Z t1
t0
L(t, x(t), u(t))dt.
The problem we shall deal with, which we label (P), is that of minimizing I over S.
Elements of Z will be called processes, of S ad- missible processes, and a process (x, u) solves (P) if (x, u) is admissible and I(x, u) ≤ I(y, v) for all ad- missible processes (y, v).
Given (x, u) ∈ Z we shall use the notation (˜x(t)) to represent (t, x(t), u(t)), and the symbol ‘∗’ will de- note transpose.
With respect to the functions delimiting the prob- lem, we assume that, if F := (L, f ), then F (t, ·, ·) is C1 for all t ∈ T and g, h, ϕ are C1; F (·, x, u), Fx(·, x, u) and Fu(·, x, u) are piecewise continuous for all (x, u) ∈ Rn × Rm; and there exists an in- tegrable function α: T → R such that, at any point (t, x, u) ∈ T × Rn× Rm,
|F (t, x, u)| + |Fx(t, x, u)| + |Fu(t, x, u)| ≤ α(t).
These assumptions are standard for the derivation of first order necessary conditions (see, for example, [11]). Also, we assume that h0(x(t1)) (x ∈ X), and the matrix (ϕ0i(u(t))) (i ∈ I(u(t)) ∪ Q, t ∈ T ) are of full rank, where
I(u) := {i ∈ R | ϕi(u) = 0}
denotes the set of active inequality indices.
For any x ∈ Rnlet
N (x) := {p ∈ Rn| p = h0(x)∗γ for some γ ∈ Rk}.
Note that, in view of the full rank assumption on h, the set N (x) corresponds to the normal cone associated to the (adjacent) tangent cone to C at x.
Denote by E, whose elements will be called ex- tremals, the set of all (x, u, p, µ) ∈ Z × X × Uqsatis- fying
i. µα(t) ≥ 0 with µα(t)ϕα(u(t)) = 0 (α ∈ R, t ∈ T );
ii. ˙p(t) = −fx∗(˜x(t))p(t) + L∗x(˜x(t)) (t ∈ T );
iii. p∗(t)fu(˜x(t))) = Lu(˜x(t))) + µ∗(t)ϕ0(u(t)) (t ∈ T );
iv. −[p(t1) + g0(x(t1))∗] ∈ N (x(t1)).
As in the finite dimensional case, we shall impose a normality condition in order to have extremality as a necessary condition for optimality.
An admissible process (x, u) will be said to be normal relative toS if, given (p, µ) ∈ X × Uqsatis- fying
i. µα(t) ≥ 0 and µα(t)ϕα(u(t)) = 0 (α ∈ R, t ∈ T );
ii. ˙p(t) = −fx∗(˜x(t))p(t) (t ∈ T );
iii. fu∗(˜x(t))p(t) = ϕ0∗(u(t))µ(t) (t ∈ T );
iv. −p(t1) ∈ N (x(t1))
then p ≡ 0. Note that, in this event, also µ ≡ 0.
Under normality assumptions, we have the fol- lowing well-known result on first order necessary con- ditions for problem (P) (see, for example, [7]).
Theorem 3 Suppose (x0, u0) solves (P) and is a nor- mal process ofS. Then there exists (p, µ) ∈ X × Uq such that(x0, u0, p, µ) ∈ E .
Let us now introduce the corresponding set S1(µ). Given µ ∈ Uq with µα(t) ≥ 0 (α ∈ R, t ∈ T ), let
S1 := S1(µ) = {(x, u) ∈ D | ϕα(u(t)) ≤ 0
(α ∈ R, µα(t) = 0, t ∈ T ), ϕβ(u(t)) = 0
(β ∈ R with µβ(t) > 0, or β ∈ Q, t ∈ T )}.
Clearly, we have that
S1= {(x, u) ∈ S |
ϕα(u(t)) = 0 (α ∈ R, µα(t) > 0, t ∈ T )}.
Applying the definition of normality to this set of constraints, we obtain the following.
Remark 4 A process (x, u) ∈ S is normal relative to S1(µ) if, given (q, ν) ∈ X × Uqsatisfying
i. να(t) ≥ 0 and να(t)ϕα(u(t)) = 0 (α ∈ R, µα(t) = 0, t ∈ T );
ii. ˙q(t) = −fx∗(˜x(t))q(t) (t ∈ T );
iii. fu∗(˜x(t))q(t) = ϕ0∗(u(t))ν(t) (t ∈ T );
iv. −q(t1) ∈ N (x(t1))
thenq ≡ 0. In this event, we also have ν ≡ 0.
Let us now prove that, given an extremal, normal- ity relative to S1(depending on the extremal) implies uniqueness of the Lagrange multipliers.
Theorem 5 Let (x0, u0) ∈ S and suppose there ex- ists(p, µ) ∈ X × Uq such that(x0, u0, p, µ) ∈ E . If (x0, u0) is normal relative to S1(µ), then (p, µ) is the unique pair inX × Uqsuch that(x0, u0, p, µ) ∈ E . Proof: Suppose (¯p, ¯µ) ∈ X × Uq is such that (x0, u0, ¯p, ¯µ) ∈ E and set
(q, ν) := (¯p − p, ¯µ − µ).
Let us show that (q, ν) satisfies the four conditions of Remark 4. If α ∈ R with µα(t) = 0, then
να(t) = ¯µα(t) ≥ 0,
να(t)ϕα(u0(t)) = ¯µα(t)ϕα(u0(t)) = 0 and so 4(i) holds. Conditions 4(ii) and 4(iii) hold since
˙
q(t) = ˙¯p(t) − ˙p(t) = −fx∗(˜x0(t))q(t) (t ∈ T ), fu∗(˜x0(t))q(t) = fu∗(˜x0(t))(¯p(t) − p(t))
= ϕ0∗(u0(t))ν(t) (t ∈ T ).
Finally, for some ¯γ, γ ∈ Rk,
−q(t1) = −¯p(t1) + p(t1) = h0(x(t1))∗(¯γ − γ) and so −q(t1) ∈ N (x(t1)). Since (x0, u0) is normal relative to S1(µ), (q, ν) ≡ (0, 0).
Let us now provide an example showing that, con- trary to the nonlinear mathematical problem posed in Section 2, the converse of this result may not hold.
Example 6 Consider the problem of minimizing I(x, u) =R−11 tu(t)dt subject to
˙
x(t) = u3(t) (t ∈ [−1, 1]), x(−1) = x(1) = 0, u2(t) ≤ 1 (t ∈ [−1, 1]).
In this case, we have R = {1}, Q = ∅, h(x) = x, f (t, x, u) = u3, L(t, x, u) = tu, ϕ(u) = u2− 1.
Consider the admissible process (x0, u0) ∈ Z given by
x0(t) :=
t + 1 if t ∈ [−1, 0]
1 − t if t ∈ (0, 1].
u0(t) :=
1 if t ∈ [−1, 0]
−1 if t ∈ (0, 1].
Suppose (x0, u0, p, µ) ∈ E . By definition of ex- tremals, we have
µ(t) ≥ 0, p(t) = 0,˙
3p(t) = t + 2u0(t)µ(t) (t ∈ [−1, 1]).
Thus p is a constant satisfying 3p =
t + 2µ(t) if t ∈ [−1, 0]
t − 2µ(t) if t ∈ (0, 1].
Since µ(t) ≥ 0 for all t ∈ [−1, 1], from the first rela- tion we have 3p ≥ 0 and, from the second, 3p ≤ t for all t ∈ (0, 1] and so p ≤ 0. Thus p ≡ 0 and therefore
µ(t) =
−t/2 if t ∈ [−1, 0]
t/2 if t ∈ [0, 1].
This implies that (p, µ) is the only pair such that (x0, u0, p, µ) ∈ E .
Now, consider the pair (q, ν) with q ≡ 2/3 and ν(t) := u0(t) (t ∈ [−1, 1]). It satisfies 4(i) since
ν(t) ≥ 0 and ν(t)ϕ(u0(t)) = 0
for all t ∈ [−1, 1] such that µ(t) = 0, that is, for t = 0. Moreover, ˙q(t) = 0 and
3q(t) = 2u0(t)ν(t) = 2
for all t ∈ [−1, 1] and so also 4(ii) and 4(iii) hold.
Finally, 4(iv) holds since
−q(1) = −2/3 = h0(x0(1))γ = γ
for some γ ∈ R. Since (q, ν) 6≡ (0, 0), (x0, u0) is not normal relative to S1(µ).
References:
[1] J. A. Becerril, K. L. Cortez and J. F. Rosen- blueth, Uniqueness of multipliers in optimal control: the missing piece, IMA J. Math. Control Inform.2018, doi.org/10.1093/imamci/dny033 [2] A. Ben-Tal, Second-order and related extremal-
ity conditions in nonlinear programming, J. Op- tim. Theory Appl.31, 1980, pp. 143–165.
[3] G. Bigi and M. Castellani, Uniqueness of KKT multipliers in multiobjective optimization, Appl.
Math. Lett.17, 2004, pp. 1285–1290.
[4] K. L. Cortez and J. F. Rosenblueth, Normal- ity and uniqueness of Lagrange multipliers, Dis- crete Contin. Dyn. Syst. 38, 2018, pp. 3169–
3188.
[5] K. L. Cortez and J. F. Rosenblueth, The broken link between normality and regularity in the cal- culus of variations, Syst. Cont. Lett. 124, 2019, pp. 27–32.
[6] G. Giorgi, A. Guerraggio and J. Thierfelder, Mathematics of Optimization: Smooth and Non- smooth Case, Elsevier, Amsterdam 2004 [7] M. R. Hestenes, Calculus of Variations and Op-
timal Control Theory, John Wiley, New York 1966
[8] M. R. Hestenes, Optimization Theory, The Finite Dimensional Case, John Wiley, New York 1975 [9] J. Kyparisis, On uniqueness of Kuhn-Tucker multipliers in nonlinear programming, Math.
Program.32, 1985, pp. 242–246.
[10] E. J. McShane, The Lagrange multiplier rule, Amer. Math. Monthly.80, 1973, pp. 922–925.
[11] J. F. Rosenblueth, Convex cones and conju- gacy for inequality control constraints, J. Convex Anal.14, 2007, pp. 361–393.
[12] J. F. Rosenblueth, Normality and quasinormality in nonlinear programming and optimal control, WSEAS Trans. Syst. Control.13, 2018, pp. 510–
513.
[13] A. Shapiro, On uniqueness of Lagrange multi- pliers in optimization problems subject to cone constraints, SIAM J. Optim. 7, 1997, pp. 508–
518.
[14] G. Wachsmuth, On LICQ and the uniqueness of Lagrange multipliers, Oper. Res. Lett. 41, 2013, pp. 78–80.
