# The Natural Gas Cash-Out Problem: A Bilevel Optimal Control Approach

Authors: Vyacheslav V. Kalashnikov; Francisco Benita; Patrick Mehlitz
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The aim of this paper is threefold: first, it formulates the natural gas cash-out problem
as a bilevel optimal control problem (BOCP); second, it provides interesting theoretical
results about Pontryagin-type optimality conditions for a general BOCP where the upper
level boasts a Mayer-type cost function and pure state constraints, while the lower level is a
finite-dimensional mixed-integer programming problem with exactly one binary variable;
and third, it applies these theoretical results in order to find possible local minimizers of the
natural gas cash-out problem.


---

## Body

## 1. Introduction

Bilevel programs are hierarchical optimization problems in the sense that their constraints are defined in part by a second parametric optimization problem. Hierarchical structures can be found in diverse scientific disciplines including environmental studies, classification theory, databases, network design, transportation, game theory, economics, and new applications, such as the gas cash-out problem. In its turn, this stimulates the development of both new theoretical results and efficient algorithms to solve bilevel programming problems.A particular case of the bilevel programming problem is presented by the following optimal control problem arising in the natural gas industry. This problem has been formulated as a mixed-integer model [1–3] arising from the minimization of cash-out penalty costs of a natural gas shipping company. In this study, we formulate the gas cash-out problem as abilevel optimal control problem (BOCP) where the upper level is equipped with a Mayer-type cost function and pure state constraints, whereas the lower level is formulated as a finite-dimensional mixed-integer programming problem (MIP) with only one binary variable.One of the main goals of this paper is to provide a maximum principle for this problem and to present a detailed discussion. The rest of the paper is organized as follows. Section2 specifies the model and describes the system’s behavior. Section 3 is the core of our whole approach: it contains the general formulation of the cash-out model, lists the assumptions we accept, reformulates the model as a single-level problem, provides Pontryagin-type optimality conditions, and illustrates the theory by means of a small example. Section 4 presents the results of application of the optimality conditions to the cash-out problem. Finally, Section 5 presents conclusions and possible items of the future research.


## 2. The Natural Gas Cash-Out Problem

Let us consider a system consisting of a single natural gas shipping company (NGSC) engaged in business with a Pipeline Operating Company (POC). The NGSC intends to transport the natural gas it buys from the wells to several consumption points (pool zones). The operative process is defined within a certain time frame[
0
,
T
], for example, a month. In every t
∈
[
0
,
T
], the NGSC buys gas at the wells, injects it into the pipeline at its string point, and extracts the amount of gas to sell it at the pool zones down the pipeline. The NGSC is required to book capacity in every pool zone before the operative period starts, so that the nominal extraction amounts are known by the POC beforehand, so that the pipeline’s operations could be planned. However, the NGSC is allowed, within certain limits, to extract a different amount of fuel more than planned/booked originally, thus creating certainimbalances. An imbalance is formally defined as the difference between the booked capacity and the extracted amount. The gas extracted at every pool zone is then sold during each period of time, t
∈
[
0
,
T
], to the Local Distribution Companies (LDCs) to fulfill prearranged contracts, with any unsold amounts marketed at different prices to external LDCs with no binding contracts to the NGSC.To prevent the NGSC from generating large unjustified imbalances, the POC will limit the levels of imbalances, positive or negative, on each period of time in every pool zone, as well as the possible change, or “swing” of those imbalances fromt to t
+
ε. At the end of the operative period, T, the POC will analyse the existing imbalances in its pipeline and redistribute them among the pool zones moving gas from zones with positive imbalances to zones with negative (and only negative!) imbalances, until only nonnegative or nonpositive imbalances exist at all pool zones (the same sign of the imbalances as the result of balancing procedure is also required). At this point, a cash-out will be arranged between the parties, with the pipeline charging high costs for the taken extra gas and paying low prices for the bought gas so that arbitrage on part of the NGSC be discouraged.The natural gas cash-out problem has been modeled as anoptimistic bilevel optimization problem in finite-dimensional spaces (cf. [1–3]). In these formulations the upper level corresponds to the decision of a single NGSC regarding its capacity booking, extraction levels, and imbalances whereas the lower level deals with the decision of the POC to come up with a balancing scheme that would please both parties. This optimization modeling is intended to be a tool for NGSCs to better manage the created imbalances in their continuous-time business. Therefore, we will interchangeably refer to the NGSC’s (POC’s) problem as the upper level (lower level) problem. Previous studies were focused on numerical solutions; however, in this work we formulate the problem as a BOCP where the aim of the paper is to provide optimality conditions for such formulation.


### 2.1. Problem Statement

Following the studies of Dempe et al. [1] and Kalashnikov and Ríos-Mercado [3], the decision making process for the NGSC is to determine how to carry out its daily imbalances such that the penalty that will be imposed by the POC is minimized. The following notation is used to describe the model.Indices and Sets
i
,
j are zone pool indices; i
,
j
∈
N
=
{
1
,
…
,
n
}.
t is time index; t
∈
[
0
,
T
].Parameters
x
i
L
(
t
)
,
x
i
U
(
t
) are lower and upper bounds on imbalances at time t
∈
[
0
,
T
] in zone i
∈
N.
x
L
(
t
)
,
x
U
(
t
) are lower and upper bounds for the sum of imbalances at time t
∈
[
0
,
T
].
u
i
L
(
t
)
,
u
i
U
(
t
) are lower and upper bounds on balance swings at time t
∈
[
0
,
T
] in zone i
∈
N.
a
i
j is percentage of fuel retained for moving one unit of gas from zone i to zone j; i
<
j, i
,
j
∈
N.
b
i
j is transportation change for moving one unit of gas from zone i to zone j; i
<
j, i
,
j
∈
N.
c
i
j is backward haul credit for moving one unit of gas from zone j to zone i; i
<
j, i
,
j
∈
N.
d
i is imbalance penalization parameter, i
∈
N.
x
i
(
0
) is initial imbalance at t
=
0 in zone i; i
∈
N.Controls and States (Upper Level)
u
i
(
t
) is imbalance swing at time t
∈
[
0
,
T
] in zone i; i
∈
N.
x
i
(
t
) is imbalance at time t
∈
[
0
,
T
] in zone i; i
∈
N.Decision Variables (Lower Level)
y
1 is total cash-out cost for the NGSC.
y
2
,
i is final imbalance at zone i; i
∈
N.
y
3
,
i
j is forward haul volume moved from zone i to zone j; i
<
j, i
,
j
∈
N.
y
4
,
i
j is backward haul volume moved from zone j to zone i; i
<
j, i
,
j
∈
N.
y
5 is auxiliary variable for linearization.Auxiliary Variables
q is binary variable equal to 1 (
0
) if final imbalances are nonnegative (nonpositive). In the special case when all the imbalances are zeros, we accept q
=
1.Let us postulate a quite natural assumption that x
L
,
x
1
L
,
…
,
x
n
L
,
x
U
,
x
1
U
,
…
,
x
n
U
:
[
0
,
T
]
→
R and the u
1
L
,
…
,
u
n
L
,
u
1
U
,
…
,
u
n
U
:
[
0
,
T
]
→
R are measurable functions which satisfy x
i
L
(
t
)
<
x
i
U
(
t
), x
L
(
t
)
<
x
U
(
t
), ∑
i
∈
N
‍
x
i
L
(
t
)
<
x
L
(
t
), x
U
(
t
)
<
∑
i
∈
N
‍
x
i
U
(
t
), and u
i
L
(
t
)
<
u
i
U
(
t
) for any t
∈
[
0
,
T
]. Furthermore, we introduce(1)
y
2
≔
y
2,1
…
y
2
,
n
⊤
,
y
l
≔
y
l
,
12
…
y
l
,
1
n
y
l
,
23
…
y
l
,
2
n
…
y
l
,
n
-
1
n
⊤
l
=
3,4
.The NGSC’s problem is given by(2a)
y
1
⟶
m
i
n
x
,
u
,
y
,
q
(2b)
x
˙
i
t
=
u
i
t
a.e.
t
∈
0
,
T
,
i
∈
N
(2c)
u
i
L
t
≤
u
i
t
≤
u
i
U
t
a.e.
t
∈
0
,
T
,
i
∈
N
(2d)
x
i
L
t
≤
x
i
t
≤
x
i
U
t
∀
t
∈
0
,
T
,
i
∈
N
(2e)
x
L
t
≤
∑
i
∈
N
x
i
t
≤
x
U
t
∀
t
∈
0
,
T
(2f)
x
i
0
=
0
n
,
i
∈
N
(2g)
y
1
,
y
2
,
y
3
,
y
4
,
y
5
,
q
∈
Ψ
x
T
.The objective function of the NGSC (2a) is to minimize the total cash-out cost, given the control system (2b) and some initial conditions (2f). Constraints (2c)–(2e) reflect the bounds on the imbalances and imbalance swings. Note that constraints (2d)-(2e) involve only state variables. Moreover, the objective function variable y
1 depends on the POC’s response to this upper level model; this is not a leader’s decision variableper se. In the latter problem the NGSC’s objective function is minimized with respect to x, u, y, and q; thus this formulation is adopting theoptimistic approach where the upper level decision maker is able to influence the POC so that the latter select his/her reaction in the leader’s favor. Finally, Ψ
(
x
(
T
)
) is the solution set of the POC’s problem for fixed x
(
T
). Hence, considering the vector of the imbalances in all zones at the final time moment x
(
T
)
∈
R
n as given, the POC’s problem can be formulated as follows: (3a)
y
5
⟶
m
i
n
y
1
,
y
2
,
y
3
,
y
4
,
y
5
,
q
(3b)
∑
j
:
i
<
j
y
3
,
i
j
+
∑
k
:
k
<
i
y
4
,
k
i
≤
m
a
x
0
,
x
i
T
,
i
∈
N
(3c)
y
3
,
i
j
≤
x
i
T
if
x
i
T
>
0
,
x
j
T
<
0
0
otherwise
,
i
,
j
∈
N
,
i
<
j
(3d)
y
4
,
i
j
≤
x
j
T
if
x
j
T
>
0
,
x
i
T
<
0
0
o
t
h
e
r
w
i
s
e
,
i
,
j
∈
N
,
i
<
j
(3e)
min
⁡
0
,
x
i
T
≤
y
2
,
i
≤
max
⁡
0
,
x
i
T
,
i
∈
N
(3f)
y
2
,
j
=
x
j
T
+
∑
i
:
i
<
j
1
-
a
i
j
y
3
,
i
j
-
y
4
,
i
j
+
∑
k
:
k
>
j
y
4
,
j
k
-
y
3
,
j
k
,
j
∈
N
(3g)
y
1
=
-
∑
i
∈
N
d
i
y
2
,
i
-
∑
i
,
j
:
i
<
j
c
i
j
y
4
,
i
j
+
∑
i
,
j
:
i
<
j
b
i
j
1
-
a
i
j
y
3
,
i
j
,
(3h)
-
y
5
≤
y
1
≤
y
5
,
(3i)
-
M
1
1
-
q
≤
y
2
,
i
≤
M
1
q
,
i
∈
N
(3j)
y
5
≥
0
,
y
3
,
i
j
,
y
4
,
i
j
≥
0
,
i
,
j
∈
N
,
i
<
j
(3k)
q
∈
0,1
,where M
1
∈
R
+ is a large enough scalar value, whose lower bound can be easily calculated, making use of duality theory, due to the compactness of the feasible set in states x
i
(
T
)
∈
R (see, e.g., [2]). Constraint (3e) arises from the business rule saying that when being rearranged by the POC, the imbalances cannot change their signs. Constraints (3b)–(3e) imply that the pipeline can haul forward or backward an amount of gas from one zone to another that does not exceed (i) the positive imbalance in the source zone and (ii) the absolute value of the negative imbalance one has in the target pool zone. Constraint (3f) explains the relationship between the last moment imbalances x
(
T
)
∈
R
n, the final imbalances y
2, and the forward/backward haul variables y
3, y
4. Constraints (3g)-(3h) define the cash-out variable y
1 and show how the objective function variable y
5 is related to y
1 via linear inequalities (the latter linear inequalities help reduce the nonlinear original lower level objective function to a linear one). Restriction (3i) reflects the requirement that all the final imbalances must be of the same sign, and it is exactly where the binary variable q appears.In [2], the mixed-integer nonlinear program (3a)–(3k) was reduced to an “almost” linear formulation. Indeed, only the presence of the binary variable q prevents the modified problem from being a linear program. Hence, for a given vector x
(
T
)
∈
R
n, we have the equivalent mixed-integer programming problem:(4a)
y
5
+
M
2
∑
i
∈
N
y
6
,
i
+
y
7
,
i
⟶
m
i
n
y
1
,
y
2
,
y
3
,
y
4
,
y
5
,
y
6
,
y
7
,
q
(4b)
1
-
a
i
j
y
3
,
i
j
≤
y
6
,
i
,
i
,
j
∈
N
,
i
<
j
(4c)
1
-
a
i
j
y
3
,
i
j
≤
y
7
,
j
,
i
,
j
∈
N
,
i
<
j
(4d)
y
4
,
i
j
≤
y
6
,
j
,
i
,
j
∈
N
,
i
<
j
(4e)
y
4
,
i
j
≤
y
7
,
i
,
i
,
j
∈
N
,
i
<
j
(4f)
-
y
7
,
i
≤
y
2
,
i
≤
y
6
,
i
,
i
∈
N
(4g)
y
6
,
i
≥
x
i
T
,
i
∈
N
(4h)
y
7
,
i
≥
-
x
i
T
,
i
∈
N
(4i)
y
6
,
i
,
y
7
,
i
≥
0
,
i
∈
N
,
(4j)
3f
–
3k
,where M
2
∈
R
+ is a large enough scalar value, and from (4a), (4g)–(4i) we have y
6
,
i
=
m
a
x
{
x
i
(
T
)
,
0
} and y
7
,
i
=
m
a
x
{
-
x
i
(
T
)
,
0
}. Note that (4a)–(4j) is a linear programming problem involving a single binary variable. Moreover, (4a)–(4j) is a linear program for each value of q, and it was shown in [1] (for M
2
=
0) that this problem is solvable for at least one of the two possible values of q
=
0 or q
=
1. Then duality theory guarantees that there exists a finite penalty value of M
2
>
0 such that constraints (4g) and (4h) are active at any optimal solution of the program in question. From now on, without loss of generality, we will use Ψ
(
x
(
T
)
) in order to denote the solution set of (4a)–(4j) for a fixed parameter x
(
T
). Based upon that, we replace the last constraint (2g) with the inclusion (
y
1
,
y
2
,
y
3
,
y
4
,
y
5
,
y
6
,
y
7
,
q
)
∈
Ψ
(
x
(
T
)
), where(5)
y
k
≔
y
k
,
1
…
y
k
,
n
⊤
,
k
=
6,7
.Due to the fact that the lower level problem is purely linear, it seems to be convenient to represent it in a matrix form. Therefore, we introduce some extra notation for vectors and matrices. Namely, byI
k
∈
R
k
×
k we denote the identity matrix of dimension k
×
k; O
k
×
l denotes the zero matrix of dimension k
×
l; and the zero-vector of dimension k is denoted by 0
k
∈
R
k. Let e
l
k
∈
R
k be the lth unity vector of dimension k and s
k
∈
R
k the all-ones vector of dimension k. We introduce the natural number n
¯
≔
1
/
2
(
n
2
-
n
) and use d
i
a
g
(
z
) in order to define (for any z
∈
R
k) a matrix in R
k
×
k whose main diagonal is given by z, while all its other entries are zero. For two vectors z
1
,
z
2
∈
R
k, the product z
1
·
z
2
∈
R
k will be understood as the componentwise product; that is, (
z
1
·
z
2
)
j
≔
z
1
j
z
2
j, j
=
1
,
…
,
k.Next, we define the lower level variable component vectory and some auxiliary vectors:(6)
y
≔
y
1
y
2
⊤
y
3
⊤
y
4
⊤
y
5
y
6
⊤
y
7
⊤
⊤
,
a
≔
a
1,2
⋯
a
1
,
n
a
2,3
⋯
a
2
,
n
⋯
a
n
-
1
,
n
⊤
,
b
≔
b
1
⋯
b
n
⊤
,
c
≔
c
1,2
⋯
c
1
,
n
c
2,3
⋯
c
2
,
n
⋯
c
n
-
1
,
n
⊤
,
d
≔
d
1
⋯
d
n
⊤
.Let us introduce the matricesH
1
,
H
2
∈
R
n
¯
×
n and H
3
,
H
4
∈
R
n
×
n
¯ as follows:(7)
H
1
≔
-
s
n
-
1
0
n
-
1
⋯
0
n
-
1
0
n
-
1
0
n
-
2
-
s
n
-
2
0
n
-
2
0
n
-
2
⋮
⋱
⋮
0
0
-
1
0
;
H
2
≔
0
n
-
1
-
e
1
n
-
1
-
e
2
n
-
1
⋯
-
e
n
-
1
n
-
1
0
n
-
2
0
n
-
2
-
e
1
n
-
2
⋯
-
e
n
-
2
n
-
2
⋮
⋮
⋱
0
0
0
-
1
;
H
3
≔
-
s
n
-
1
1
-
a
1,2
e
1
n
-
1
1
-
a
1,3
e
2
n
-
1
⋯
1
-
a
1
,
n
e
n
-
1
n
-
1
0
n
-
2
-
s
n
-
2
1
-
a
2,3
e
1
n
-
2
⋯
1
-
a
2
,
n
e
n
-
2
n
-
2
⋮
⋱
⋮
0
0
0
1
-
a
n
-
1
,
n
⊤
;
H
4
≔
s
n
-
1
-
e
1
n
-
1
-
e
2
n
-
1
⋯
-
e
n
-
1
n
-
1
0
n
-
2
s
n
-
2
-
e
1
n
-
2
⋯
-
e
n
-
2
n
-
2
⋮
⋱
⋮
0
0
0
-
1
⊤
,and use the latter ones to compose the overall system’s matrices. In order to do that, we define A
1
∈
R
(
3
n
2
+
5
n
+
2
)
×
n, A
2
∈
R
(
n
+
1
)
×
n, B
1
∈
R
(
3
n
2
+
5
n
+
2
)
×
(
n
2
+
2
n
+
2
), B
2
∈
R
(
n
+
1
)
×
(
n
2
+
2
n
+
2
), C
1
,
D
1
∈
R
3
n
2
+
5
n
+
2, C
2
,
D
2
∈
R
n
+
1, and w
∈
R
n
2
+
2
n
+
2 as follows:(8)
A
1
≔
O
n
¯
×
n
O
n
¯
×
n
O
n
¯
×
n
O
n
¯
×
n
O
n
×
n
O
n
×
n
I
n
-
I
n
O
n
×
n
O
n
×
n
0
0
O
n
×
n
O
n
×
n
O
n
¯
×
n
O
n
¯
×
n
;
C
1
≔
0
n
¯
0
n
¯
0
n
¯
0
n
¯
0
n
0
n
0
n
0
n
0
n
0
n
0
0
M
1
s
n
-
M
1
s
n
0
n
¯
0
n
¯
;
D
1
≔
0
n
¯
0
n
¯
0
n
¯
0
n
¯
0
n
0
n
0
n
0
n
0
n
0
n
0
0
M
1
s
n
0
n
0
n
¯
0
n
¯
;
A
2
≔
I
n
O
1
×
n
;
C
2
≔
0
n
0
;
D
2
≔
0
n
0
;
B
1
≔
0
n
¯
O
n
¯
×
n
diag
⁡
s
n
¯
-
a
O
n
¯
×
n
¯
0
n
¯
H
1
O
n
¯
×
n
0
n
¯
O
n
¯
×
n
diag
⁡
s
n
¯
-
a
O
n
¯
×
n
¯
0
n
¯
O
n
¯
×
n
H
2
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
¯
I
n
¯
0
n
¯
H
2
O
n
¯
×
n
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
¯
I
n
¯
0
n
¯
O
n
¯
×
n
H
1
0
n
-
I
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
-
I
n
0
n
I
n
O
n
×
n
¯
O
n
×
n
¯
0
n
-
I
n
O
n
×
n
0
n
O
n
×
n
O
n
×
n
¯
O
n
×
n
¯
0
n
-
I
n
O
n
×
n
0
n
O
n
×
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
-
I
n
0
n
O
n
×
n
O
n
×
n
¯
O
n
×
n
¯
0
n
-
I
n
O
n
×
n
0
n
O
n
×
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
-
I
n
-
1
O
1
×
n
O
1
×
n
¯
O
1
×
n
¯
-
1
O
1
×
n
O
1
×
n
1
O
1
×
n
O
1
×
n
¯
O
1
×
n
¯
-
1
O
1
×
n
O
1
×
n
0
n
-
I
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
O
n
×
n
0
n
I
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
O
n
×
n
0
n
¯
O
n
¯
×
n
-
I
n
¯
O
n
¯
×
n
¯
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
¯
-
I
n
¯
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
;
B
2
≔
0
n
-
I
n
H
3
H
4
0
n
O
n
×
n
O
n
×
n
1
d
⊤
b
·
a
-
s
n
¯
⊤
c
⊤
0
O
1
×
n
O
1
×
n
;
w
≔
0
0
n
⊤
0
n
¯
⊤
0
n
¯
⊤
1
M
2
·
s
n
⊤
M
2
·
s
n
⊤
⊤
.Hence, we can rewrite (4a)–(4j) as(9)
w
⊤
y
⟶
m
i
n
y
,
q
s
u
b
j
e
c
t
t
o
A
1
x
T
+
B
1
y
+
C
1
q
≤
D
1
,
A
2
x
T
+
B
2
y
+
C
2
q
=
D
2
,
q
∈
0,1
.


## 2.1. Problem Statement

Following the studies of Dempe et al. [1] and Kalashnikov and Ríos-Mercado [3], the decision making process for the NGSC is to determine how to carry out its daily imbalances such that the penalty that will be imposed by the POC is minimized. The following notation is used to describe the model.Indices and Sets
i
,
j are zone pool indices; i
,
j
∈
N
=
{
1
,
…
,
n
}.
t is time index; t
∈
[
0
,
T
].Parameters
x
i
L
(
t
)
,
x
i
U
(
t
) are lower and upper bounds on imbalances at time t
∈
[
0
,
T
] in zone i
∈
N.
x
L
(
t
)
,
x
U
(
t
) are lower and upper bounds for the sum of imbalances at time t
∈
[
0
,
T
].
u
i
L
(
t
)
,
u
i
U
(
t
) are lower and upper bounds on balance swings at time t
∈
[
0
,
T
] in zone i
∈
N.
a
i
j is percentage of fuel retained for moving one unit of gas from zone i to zone j; i
<
j, i
,
j
∈
N.
b
i
j is transportation change for moving one unit of gas from zone i to zone j; i
<
j, i
,
j
∈
N.
c
i
j is backward haul credit for moving one unit of gas from zone j to zone i; i
<
j, i
,
j
∈
N.
d
i is imbalance penalization parameter, i
∈
N.
x
i
(
0
) is initial imbalance at t
=
0 in zone i; i
∈
N.Controls and States (Upper Level)
u
i
(
t
) is imbalance swing at time t
∈
[
0
,
T
] in zone i; i
∈
N.
x
i
(
t
) is imbalance at time t
∈
[
0
,
T
] in zone i; i
∈
N.Decision Variables (Lower Level)
y
1 is total cash-out cost for the NGSC.
y
2
,
i is final imbalance at zone i; i
∈
N.
y
3
,
i
j is forward haul volume moved from zone i to zone j; i
<
j, i
,
j
∈
N.
y
4
,
i
j is backward haul volume moved from zone j to zone i; i
<
j, i
,
j
∈
N.
y
5 is auxiliary variable for linearization.Auxiliary Variables
q is binary variable equal to 1 (
0
) if final imbalances are nonnegative (nonpositive). In the special case when all the imbalances are zeros, we accept q
=
1.Let us postulate a quite natural assumption that x
L
,
x
1
L
,
…
,
x
n
L
,
x
U
,
x
1
U
,
…
,
x
n
U
:
[
0
,
T
]
→
R and the u
1
L
,
…
,
u
n
L
,
u
1
U
,
…
,
u
n
U
:
[
0
,
T
]
→
R are measurable functions which satisfy x
i
L
(
t
)
<
x
i
U
(
t
), x
L
(
t
)
<
x
U
(
t
), ∑
i
∈
N
‍
x
i
L
(
t
)
<
x
L
(
t
), x
U
(
t
)
<
∑
i
∈
N
‍
x
i
U
(
t
), and u
i
L
(
t
)
<
u
i
U
(
t
) for any t
∈
[
0
,
T
]. Furthermore, we introduce(1)
y
2
≔
y
2,1
…
y
2
,
n
⊤
,
y
l
≔
y
l
,
12
…
y
l
,
1
n
y
l
,
23
…
y
l
,
2
n
…
y
l
,
n
-
1
n
⊤
l
=
3,4
.The NGSC’s problem is given by(2a)
y
1
⟶
m
i
n
x
,
u
,
y
,
q
(2b)
x
˙
i
t
=
u
i
t
a.e.
t
∈
0
,
T
,
i
∈
N
(2c)
u
i
L
t
≤
u
i
t
≤
u
i
U
t
a.e.
t
∈
0
,
T
,
i
∈
N
(2d)
x
i
L
t
≤
x
i
t
≤
x
i
U
t
∀
t
∈
0
,
T
,
i
∈
N
(2e)
x
L
t
≤
∑
i
∈
N
x
i
t
≤
x
U
t
∀
t
∈
0
,
T
(2f)
x
i
0
=
0
n
,
i
∈
N
(2g)
y
1
,
y
2
,
y
3
,
y
4
,
y
5
,
q
∈
Ψ
x
T
.The objective function of the NGSC (2a) is to minimize the total cash-out cost, given the control system (2b) and some initial conditions (2f). Constraints (2c)–(2e) reflect the bounds on the imbalances and imbalance swings. Note that constraints (2d)-(2e) involve only state variables. Moreover, the objective function variable y
1 depends on the POC’s response to this upper level model; this is not a leader’s decision variableper se. In the latter problem the NGSC’s objective function is minimized with respect to x, u, y, and q; thus this formulation is adopting theoptimistic approach where the upper level decision maker is able to influence the POC so that the latter select his/her reaction in the leader’s favor. Finally, Ψ
(
x
(
T
)
) is the solution set of the POC’s problem for fixed x
(
T
). Hence, considering the vector of the imbalances in all zones at the final time moment x
(
T
)
∈
R
n as given, the POC’s problem can be formulated as follows: (3a)
y
5
⟶
m
i
n
y
1
,
y
2
,
y
3
,
y
4
,
y
5
,
q
(3b)
∑
j
:
i
<
j
y
3
,
i
j
+
∑
k
:
k
<
i
y
4
,
k
i
≤
m
a
x
0
,
x
i
T
,
i
∈
N
(3c)
y
3
,
i
j
≤
x
i
T
if
x
i
T
>
0
,
x
j
T
<
0
0
otherwise
,
i
,
j
∈
N
,
i
<
j
(3d)
y
4
,
i
j
≤
x
j
T
if
x
j
T
>
0
,
x
i
T
<
0
0
o
t
h
e
r
w
i
s
e
,
i
,
j
∈
N
,
i
<
j
(3e)
min
⁡
0
,
x
i
T
≤
y
2
,
i
≤
max
⁡
0
,
x
i
T
,
i
∈
N
(3f)
y
2
,
j
=
x
j
T
+
∑
i
:
i
<
j
1
-
a
i
j
y
3
,
i
j
-
y
4
,
i
j
+
∑
k
:
k
>
j
y
4
,
j
k
-
y
3
,
j
k
,
j
∈
N
(3g)
y
1
=
-
∑
i
∈
N
d
i
y
2
,
i
-
∑
i
,
j
:
i
<
j
c
i
j
y
4
,
i
j
+
∑
i
,
j
:
i
<
j
b
i
j
1
-
a
i
j
y
3
,
i
j
,
(3h)
-
y
5
≤
y
1
≤
y
5
,
(3i)
-
M
1
1
-
q
≤
y
2
,
i
≤
M
1
q
,
i
∈
N
(3j)
y
5
≥
0
,
y
3
,
i
j
,
y
4
,
i
j
≥
0
,
i
,
j
∈
N
,
i
<
j
(3k)
q
∈
0,1
,where M
1
∈
R
+ is a large enough scalar value, whose lower bound can be easily calculated, making use of duality theory, due to the compactness of the feasible set in states x
i
(
T
)
∈
R (see, e.g., [2]). Constraint (3e) arises from the business rule saying that when being rearranged by the POC, the imbalances cannot change their signs. Constraints (3b)–(3e) imply that the pipeline can haul forward or backward an amount of gas from one zone to another that does not exceed (i) the positive imbalance in the source zone and (ii) the absolute value of the negative imbalance one has in the target pool zone. Constraint (3f) explains the relationship between the last moment imbalances x
(
T
)
∈
R
n, the final imbalances y
2, and the forward/backward haul variables y
3, y
4. Constraints (3g)-(3h) define the cash-out variable y
1 and show how the objective function variable y
5 is related to y
1 via linear inequalities (the latter linear inequalities help reduce the nonlinear original lower level objective function to a linear one). Restriction (3i) reflects the requirement that all the final imbalances must be of the same sign, and it is exactly where the binary variable q appears.In [2], the mixed-integer nonlinear program (3a)–(3k) was reduced to an “almost” linear formulation. Indeed, only the presence of the binary variable q prevents the modified problem from being a linear program. Hence, for a given vector x
(
T
)
∈
R
n, we have the equivalent mixed-integer programming problem:(4a)
y
5
+
M
2
∑
i
∈
N
y
6
,
i
+
y
7
,
i
⟶
m
i
n
y
1
,
y
2
,
y
3
,
y
4
,
y
5
,
y
6
,
y
7
,
q
(4b)
1
-
a
i
j
y
3
,
i
j
≤
y
6
,
i
,
i
,
j
∈
N
,
i
<
j
(4c)
1
-
a
i
j
y
3
,
i
j
≤
y
7
,
j
,
i
,
j
∈
N
,
i
<
j
(4d)
y
4
,
i
j
≤
y
6
,
j
,
i
,
j
∈
N
,
i
<
j
(4e)
y
4
,
i
j
≤
y
7
,
i
,
i
,
j
∈
N
,
i
<
j
(4f)
-
y
7
,
i
≤
y
2
,
i
≤
y
6
,
i
,
i
∈
N
(4g)
y
6
,
i
≥
x
i
T
,
i
∈
N
(4h)
y
7
,
i
≥
-
x
i
T
,
i
∈
N
(4i)
y
6
,
i
,
y
7
,
i
≥
0
,
i
∈
N
,
(4j)
3f
–
3k
,where M
2
∈
R
+ is a large enough scalar value, and from (4a), (4g)–(4i) we have y
6
,
i
=
m
a
x
{
x
i
(
T
)
,
0
} and y
7
,
i
=
m
a
x
{
-
x
i
(
T
)
,
0
}. Note that (4a)–(4j) is a linear programming problem involving a single binary variable. Moreover, (4a)–(4j) is a linear program for each value of q, and it was shown in [1] (for M
2
=
0) that this problem is solvable for at least one of the two possible values of q
=
0 or q
=
1. Then duality theory guarantees that there exists a finite penalty value of M
2
>
0 such that constraints (4g) and (4h) are active at any optimal solution of the program in question. From now on, without loss of generality, we will use Ψ
(
x
(
T
)
) in order to denote the solution set of (4a)–(4j) for a fixed parameter x
(
T
). Based upon that, we replace the last constraint (2g) with the inclusion (
y
1
,
y
2
,
y
3
,
y
4
,
y
5
,
y
6
,
y
7
,
q
)
∈
Ψ
(
x
(
T
)
), where(5)
y
k
≔
y
k
,
1
…
y
k
,
n
⊤
,
k
=
6,7
.Due to the fact that the lower level problem is purely linear, it seems to be convenient to represent it in a matrix form. Therefore, we introduce some extra notation for vectors and matrices. Namely, byI
k
∈
R
k
×
k we denote the identity matrix of dimension k
×
k; O
k
×
l denotes the zero matrix of dimension k
×
l; and the zero-vector of dimension k is denoted by 0
k
∈
R
k. Let e
l
k
∈
R
k be the lth unity vector of dimension k and s
k
∈
R
k the all-ones vector of dimension k. We introduce the natural number n
¯
≔
1
/
2
(
n
2
-
n
) and use d
i
a
g
(
z
) in order to define (for any z
∈
R
k) a matrix in R
k
×
k whose main diagonal is given by z, while all its other entries are zero. For two vectors z
1
,
z
2
∈
R
k, the product z
1
·
z
2
∈
R
k will be understood as the componentwise product; that is, (
z
1
·
z
2
)
j
≔
z
1
j
z
2
j, j
=
1
,
…
,
k.Next, we define the lower level variable component vectory and some auxiliary vectors:(6)
y
≔
y
1
y
2
⊤
y
3
⊤
y
4
⊤
y
5
y
6
⊤
y
7
⊤
⊤
,
a
≔
a
1,2
⋯
a
1
,
n
a
2,3
⋯
a
2
,
n
⋯
a
n
-
1
,
n
⊤
,
b
≔
b
1
⋯
b
n
⊤
,
c
≔
c
1,2
⋯
c
1
,
n
c
2,3
⋯
c
2
,
n
⋯
c
n
-
1
,
n
⊤
,
d
≔
d
1
⋯
d
n
⊤
.Let us introduce the matricesH
1
,
H
2
∈
R
n
¯
×
n and H
3
,
H
4
∈
R
n
×
n
¯ as follows:(7)
H
1
≔
-
s
n
-
1
0
n
-
1
⋯
0
n
-
1
0
n
-
1
0
n
-
2
-
s
n
-
2
0
n
-
2
0
n
-
2
⋮
⋱
⋮
0
0
-
1
0
;
H
2
≔
0
n
-
1
-
e
1
n
-
1
-
e
2
n
-
1
⋯
-
e
n
-
1
n
-
1
0
n
-
2
0
n
-
2
-
e
1
n
-
2
⋯
-
e
n
-
2
n
-
2
⋮
⋮
⋱
0
0
0
-
1
;
H
3
≔
-
s
n
-
1
1
-
a
1,2
e
1
n
-
1
1
-
a
1,3
e
2
n
-
1
⋯
1
-
a
1
,
n
e
n
-
1
n
-
1
0
n
-
2
-
s
n
-
2
1
-
a
2,3
e
1
n
-
2
⋯
1
-
a
2
,
n
e
n
-
2
n
-
2
⋮
⋱
⋮
0
0
0
1
-
a
n
-
1
,
n
⊤
;
H
4
≔
s
n
-
1
-
e
1
n
-
1
-
e
2
n
-
1
⋯
-
e
n
-
1
n
-
1
0
n
-
2
s
n
-
2
-
e
1
n
-
2
⋯
-
e
n
-
2
n
-
2
⋮
⋱
⋮
0
0
0
-
1
⊤
,and use the latter ones to compose the overall system’s matrices. In order to do that, we define A
1
∈
R
(
3
n
2
+
5
n
+
2
)
×
n, A
2
∈
R
(
n
+
1
)
×
n, B
1
∈
R
(
3
n
2
+
5
n
+
2
)
×
(
n
2
+
2
n
+
2
), B
2
∈
R
(
n
+
1
)
×
(
n
2
+
2
n
+
2
), C
1
,
D
1
∈
R
3
n
2
+
5
n
+
2, C
2
,
D
2
∈
R
n
+
1, and w
∈
R
n
2
+
2
n
+
2 as follows:(8)
A
1
≔
O
n
¯
×
n
O
n
¯
×
n
O
n
¯
×
n
O
n
¯
×
n
O
n
×
n
O
n
×
n
I
n
-
I
n
O
n
×
n
O
n
×
n
0
0
O
n
×
n
O
n
×
n
O
n
¯
×
n
O
n
¯
×
n
;
C
1
≔
0
n
¯
0
n
¯
0
n
¯
0
n
¯
0
n
0
n
0
n
0
n
0
n
0
n
0
0
M
1
s
n
-
M
1
s
n
0
n
¯
0
n
¯
;
D
1
≔
0
n
¯
0
n
¯
0
n
¯
0
n
¯
0
n
0
n
0
n
0
n
0
n
0
n
0
0
M
1
s
n
0
n
0
n
¯
0
n
¯
;
A
2
≔
I
n
O
1
×
n
;
C
2
≔
0
n
0
;
D
2
≔
0
n
0
;
B
1
≔
0
n
¯
O
n
¯
×
n
diag
⁡
s
n
¯
-
a
O
n
¯
×
n
¯
0
n
¯
H
1
O
n
¯
×
n
0
n
¯
O
n
¯
×
n
diag
⁡
s
n
¯
-
a
O
n
¯
×
n
¯
0
n
¯
O
n
¯
×
n
H
2
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
¯
I
n
¯
0
n
¯
H
2
O
n
¯
×
n
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
¯
I
n
¯
0
n
¯
O
n
¯
×
n
H
1
0
n
-
I
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
-
I
n
0
n
I
n
O
n
×
n
¯
O
n
×
n
¯
0
n
-
I
n
O
n
×
n
0
n
O
n
×
n
O
n
×
n
¯
O
n
×
n
¯
0
n
-
I
n
O
n
×
n
0
n
O
n
×
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
-
I
n
0
n
O
n
×
n
O
n
×
n
¯
O
n
×
n
¯
0
n
-
I
n
O
n
×
n
0
n
O
n
×
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
-
I
n
-
1
O
1
×
n
O
1
×
n
¯
O
1
×
n
¯
-
1
O
1
×
n
O
1
×
n
1
O
1
×
n
O
1
×
n
¯
O
1
×
n
¯
-
1
O
1
×
n
O
1
×
n
0
n
-
I
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
O
n
×
n
0
n
I
n
O
n
×
n
¯
O
n
×
n
¯
0
n
O
n
×
n
O
n
×
n
0
n
¯
O
n
¯
×
n
-
I
n
¯
O
n
¯
×
n
¯
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
¯
-
I
n
¯
0
n
¯
O
n
¯
×
n
O
n
¯
×
n
;
B
2
≔
0
n
-
I
n
H
3
H
4
0
n
O
n
×
n
O
n
×
n
1
d
⊤
b
·
a
-
s
n
¯
⊤
c
⊤
0
O
1
×
n
O
1
×
n
;
w
≔
0
0
n
⊤
0
n
¯
⊤
0
n
¯
⊤
1
M
2
·
s
n
⊤
M
2
·
s
n
⊤
⊤
.Hence, we can rewrite (4a)–(4j) as(9)
w
⊤
y
⟶
m
i
n
y
,
q
s
u
b
j
e
c
t
t
o
A
1
x
T
+
B
1
y
+
C
1
q
≤
D
1
,
A
2
x
T
+
B
2
y
+
C
2
q
=
D
2
,
q
∈
0,1
.


## 3. General Setting and Optimality Conditions

This section deals with the theoretical results providing optimality conditions for the bilevel program in general, with an aim to apply them to our gas cash-out problem in Section4.


### 3.1. Preliminaries and Further Notation

Throughout this paper, we denote byR, R
n, R
m
×
n, R
+
n, and R
¯
≔
R
∪
{
-
∞
,
∞
} the set of real numbers, the space of all real vectors with n components, the space of all real matrices with m rows and n columns, the nonnegative orthant of R
n, and the extended real line, respectively. For any matrix X
∈
R
m
×
n, let X
⊤
∈
R
n
×
m denote its transpose. Next, for an arbitrary subset M
⊆
R
n, we use i
n
t
(
M
), r
i
(
M
), and c
o
n
v
(
M
) in order to denote the interior, the relative interior, and the convex hull of M, respectively. For x
∗
∈
M, we define theFréchet normal cone
N
^
M
(
x
∗
) to M at x
∗ by means of(10)
N
^
M
x
∗
≔
d
∈
R
n
∣
limsup
x
→
x
∗
,
x
∈
M
⁡
x
-
x
∗
⊤
d
x
-
x
∗
≤
0
. Here, · is an arbitrary norm in R
n. Furthermore, thebasic normal cone (sometimes referred to asMordukhovich normal cone) N
M
B
(
x
∗
) to M at x
∗ is given by(11)
N
M
B
x
∗
≔
limsup
x
→
x
∗
,
x
∈
M
⁡
N
^
M
x
,where the upper limit has to be interpreted in the sense of Painlevé-Kuratowski (cf. [4]). If M is a convex set, then N
^
M
(
x
∗
) and N
M
B
(
x
∗
) both coincide with the normal cone of convex analysis, which we denote by N
M
(
x
∗
). Let us denote by U
R
n and B
R
n the open and closed unit balls in R
n, and, for any ɛ
>
0
,
x
∗
∈
R
n, we define U
R
n
ɛ
(
x
∗
)
≔
{
x
∗
}
+
ɛ
U
R
n and B
R
n
ɛ
(
x
∗
)
≔
{
x
∗
}
+
ɛ
B
R
n, respectively. Given a differentiable function F
:
R
n
→
R
m, its Jacobian at x
∈
R
n is represented by ∇
F
(
x
)
∈
R
m
×
n. Next, we denote by C and C
∗ the space of scalar continuous functions defined over the interval [
0
,
T
] and the dual space of C, respectively. The set of elements in C
∗ taking nonnegative values at nonnegative functions in C is denoted by C
⊕. Given a nonnegative measure μ
∈
C
⊕, its norm μ
C
∗ coincides with the total variation of μ defined as ∫
0
T
‍
μ
(
d
s
) and the support of the measure μ; written s
u
p
p
(
μ
) is the smallest closed set A
⊆
[
0
,
T
] such that for any relatively open subset B
⊆
[
0
,
T
]
∖
A one has μ
(
B
)
=
0. The Euclidean norm of a vector x
∈
R
n is denoted by x, the space of all Lebesgue-integrable functions w such that w
:
[
0
,
T
]
→
R
n is described by L
n
1, and by W
n
1,1 we represent the Sobolev space that contains all absolutely continuous R
n-valued functions on [
0
,
T
], whose weak derivatives belong to L
n
1. By L
n
∞ we denote the Banach space of all vector-functions with n essentially bounded components defined over [
0
,
T
]. Furthermore, by L
×
B
n we express the product σ-algebra generated by the Lebesgue set L and the Borel subsets of R
n.For a lower semicontinuous functionalf
:
R
n
→
R
¯, we introduce its domain as d
o
m
(
f
)
≔
{
x
∈
R
n
∣
f
x
<
+
∞
}. Suppose that x
∗
∈
d
o
m
(
f
) is fixed. Then we define theFréchet subdifferential
∂
^
f
(
x
∗
) of f at x
∗ as(12)
∂
^
f
x
∗
≔
a
∈
R
n
∣
liminf
x
→
x
∗
⁡
f
x
-
f
x
∗
-
x
-
x
∗
⊤
a
x
-
x
∗
≥
0
.Furthermore, we make use of thesingular subdifferential
∂
∞
f
(
x
∗
) of f at x
∗, which is defined as stated below:(13)
∂
∞
f
x
∗
≔
limsup
x
→
x
∗
,
α
↘
0
⁡
α
·
∂
^
f
x
.Note that ∂
∞
f
(
x
∗
)
=
{
0
n
} holds if and only if f is locally Lipschitz continuous at x
∗ (cf. [5]). In the latter case ∂
c
f
(
x
∗
), the Clarke subdifferential of f at x
∗ is a nonempty, compact, and convex set (cf. [6]) and consequently we have x
∗
∈
i
n
t
(
d
o
m
(
f
)
). Suppose that f is a convex functional and x
∗
∈
r
i
(
d
o
m
(
f
)
) is chosen arbitrarily. Then ∂
^
f
(
x
∗
) and ∂
c
f
(
x
∗
) both coincide with the classical subdifferential of f at x
∗, the latter being denoted by ∂
f
(
x
∗
). For further information on these concepts of variational analysis, we refer the interested reader to [7].LetΘ
:
R
n
⇉
R
m be an arbitrary set-valued mapping. The domain and graph of Θ are denoted, respectively, by d
o
m
(
Θ
) and g
r
a
p
h
(
Θ
). We say that Θ is apolyhedral mapping provided that its graph is the union of a finite collection of polyhedra. The mapping Θ is calledlocally Lipschitz continuous at x
∗
∈
R
n whenever there exist scalars L
Θ
,
ε
Θ
>
0 such that for all x
,
x
′
∈
U
R
n
ε
Θ
(
x
∗
) the following condition is satisfied:(14)
Θ
x
⊆
Θ
x
′
+
L
Θ
x
-
x
′
B
R
n
.If the above inclusion holds only when x
′
≔
x
∗ is fixed, then Θ is calledlocally upper Lipschitz continuous at x
∗. We call Θ
upper (lower)semicontinuous at x
∗ provided that for any open set O
⊆
R
m satisfying Θ
(
x
∗
)
⊆
O (Θ
(
x
∗
)
∩
O
≠
∅) we find ɛ
>
0 such that Θ
(
x
)
⊆
O (Θ
(
x
)
∩
O
≠
∅) holds true for all x
∈
U
R
n
ɛ
(
x
∗
). Now choose an arbitrary point (
x
∗
,
y
∗
)
∈
g
r
a
p
h
(
Θ
). We say that Θ isinner semicontinuous at (
x
∗
,
y
∗
) if for any sequence {
x
k
}
⊆
R
n converging to x
∗ we find a sequence {
y
k
}
⊆
R
m converging to y
∗ and k
0
∈
N such that y
k
∈
Θ
(
x
k
) is true for all k
∈
N greater than k
0. Obviously, if Θ is locally Lipschitz continuous at x
∗, then it is inner semicontinuous at any point (
x
∗
,
y
¯
) with y
¯
∈
Θ
(
x
∗
). Thenormal coderivative
D
∗
Θ
(
x
∗
,
y
∗
)
:
R
m
⇉
R
n of Θ at (
x
∗
,
y
∗
) is defined as stated below for any y
∈
R
m:(15)
D
∗
Θ
x
∗
,
y
∗
y
≔
x
∈
R
n
∣
x
,
-
y
∈
N
graph
Θ
B
x
∗
,
y
∗
.Finally, we recall some helpful calculation rules concerning the Minkowski sum of sets. Due to its simplicity the corresponding proof is omitted here.Lemma 1.
LetA
,
B
,
C
,
D
⊆
R
n be arbitrary sets. Then the following statements hold:(i)
(
A
+
B
)
∪
(
C
+
D
)
⊆
(
A
∪
C
)
+
(
B
∪
D
);
(ii)
A
⊆
B
+
C
⇒
A
×
D
⊆
(
B
×
D
)
+
(
C
×
{
0
n
}
).


### 3.2. General Setting

In order to derive optimality conditions for the natural gas cash-out problem (2a)–(2g) where the lower level problem (3a)–(3k) is replaced with (4a)–(4j), we are going to develop a general formulation. The idea is to derive general optimality conditions, and by applying those theoretical results one can easily provide optimality conditions to the original problem of interest.Let us rewrite problem (2a)–(2g) as anoptimistic BOCP such that(16)
F
x
T
,
y
,
q
⟶
m
i
n
x
,
u
,
y
,
q
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
y
,
q
∈
Ψ
x
T
,where(17)
Ψ
x
T
≔
Argmin
y
,
q
⁡
w
⊤
y
∣
y
,
q
∈
Γ
x
T
.The problem’s data comprise an interval[
0
,
T
] for a fixed final time moment T
>
0, given initial conditions x
0
∈
R
n
x, functions F
:
R
n
x
×
R
m
y
×
{
0,1
}
→
R, ϕ
:
[
0
,
T
]
×
R
n
x
×
R
n
u
→
R
n
x, G
:
[
0
,
T
]
×
R
n
x
→
R
n
G, and a multivalued mapping U
:
[
0
,
T
]
⇉
R
n
u that is measurable on [
0
,
T
]. The feasible set of control functions is U
≔
{
u
:
[
0
,
T
]
→
R
n
u
∣
u
∈
L
n
u
1
,
u
(
t
)
∈
U
(
t
)
a
.
e
.
t
∈
[
0
,
T
]
}. The state trajectory x
∈
W
n
x
1,1 is an absolutely continuous function that satisfies the differential equation and the initial conditions for some control function u
∈
L
n
u
1. Finally, Ψ
:
R
n
x
⇉
R
m
y
×
{
0,1
} denotes the solution set mapping of the lower level problem, while w
∈
R
m
y is a fixed vector and Γ
:
R
n
x
⇉
R
m
y
×
{
0,1
} is a set-valued mapping that will be specified below.In other words, problem (16) is an optimistic BOCP with final-state-dependent finite-dimensional lower level. Moreover, the upper level problem boasts a Mayer-type cost function and state constraints. This formulation is notably interesting due to the parametric optimization problem at the lower level, whose parameter is nothing else but the final state of the upper level state variable. Hence, the natural gas cash-out problem specified by (2a)–(2g) fits into the formulation of problem (16).Taking into account the POC’s problem (4a)–(4j) one can define the set Γ as follows:(18)
Γ
x
T
≔
y
,
q
∈
R
m
y
×
0,1
∣
A
1
x
T
+
B
1
y
+
C
1
q
≤
D
1
,
A
2
x
T
+
B
2
y
+
C
2
q
=
D
2
,where A
1
∈
R
m
g
×
n
x, A
2
∈
R
m
h
×
n
x, B
1
∈
R
m
g
×
m
y, B
2
∈
R
m
h
×
m
y, C
1
,
D
1
∈
R
m
g, and C
2
,
D
2
∈
R
m
h are given matrices. When comparing the original problem (2a)–(2g) and the general formulation in (16), it is not difficult to see that we have n
x
=
n
u
=
n, n
G
=
2
n
+
2, m
y
=
n
2
+
2
n
+
2, m
g
=
3
n
2
+
5
n
+
2, and m
h
=
n
+
1.Let us consider the spaceW
≔
W
n
x
1,1
×
L
n
u
1
×
R
m
y
×
{
0,1
}. Then the process (
x
,
u
,
y
,
q
)
∈
W is said to befeasible for (16) if it satisfies the dynamical system, the initial condition, and the pure state constraints, while (
y
,
q
) is a global optimal solution for the corresponding lower level problem. Now we introduce the definition of a local minimizer.Definition 2.
Take a feasible process(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W. Then (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a local minimizer of problem (16) if there exists ɛ
>
0 such that(19)
F
x
T
∗
,
y
∗
,
q
∗
≤
F
x
T
,
y
,
q
∗holds provided that (
x
,
y
)
∈
U
W
n
x
1,1
×
R
m
y
ε
(
x
∗
,
y
∗
), and (
x
,
u
,
y
,
q
∗
) is feasible for (16).Clearly, the optimality conditions for local minimizers automatically hold for strong and hence for global minimizers. By following the approach in Vinter [8], the above definition respects our desire to focus on the state variables of (16) while ignoring somehow the control function’s behavior. Additionally, fixing the binary variable q proposes a strategy about how to deal with (16). We compute possible minimizers for the problems that arise when setting q
=
0 and q
=
1 and then compare the resulting points. Note that assuming q to be free in the definition of local optimal solutions is another idea we are not going to examine here.For an arbitrary local minimum point(
x
∗
,
u
∗
,
y
∗
,
q
∗
) of (16), we accept the following assumptions:(A
1)
(i)
For a fixedq
≔
q
∗, the function F is continuously differentiable with respect to all their arguments.
(ii)
The function(
t
,
u
)
↦
ϕ
(
t
,
x
,
u
) is L
×
B
n
u-measurable for each x
∈
R
n
x.
(iii)
There exist aL
×
B
n
u-measurable function ζ
:
R
n
u
→
R and a constant δ
>
0 such that t
↦
ζ
(
u
∗
(
t
)
) is integrable and (20)
ϕ
t
,
x
,
u
-
ϕ
t
,
x
′
,
u
≤
ζ
x
-
x
′
.
Forx
,
x
′
∈
U
R
n
x
δ
(
x
∗
(
t
)
), u
∈
U
(
t
) a.e. t
∈
[
0
,
T
].
(iv)
The setg
r
a
p
h
(
U
) is L
×
B
n
u measurable.
(v)
The component functionsG
1
,
…
,
G
n
G
:
[
0
,
T
]
×
R
n
x
→
R of G are continuously differentiable with respect to all their arguments. Furthermore, for any t
∈
[
0
,
T
] the set {
∇
x
G
l
(
t
,
x
∗
(
t
)
)
∣
l
∈
I
(
t
,
x
∗
(
t
)
)
} is positive linearly independent; therein, for any s
′
∈
[
0
,
T
] and x
∈
R
n
x we define(21)
I
s
′
,
x
≔
l
∈
1
,
…
,
n
G
∣
G
l
s
′
,
x
=
max
⁡
G
1
s
′
,
x
;
…
;
G
n
G
s
′
,
x
.
(A
2)
(i)
IfG
l
(
0
,
x
0
)
=
0 holds true for some l
∈
{
1
,
…
,
n
G
}, then there exist constants ε
1
,
ε
2
>
0 such that the set {
ϕ
(
s
′
,
x
,
v
)
∈
R
n
x
∣
v
∈
U
(
s
′
)
} is convex for any s
′
∈
[
0
,
ε
1
) and any x
∈
U
R
n
x
ε
2
(
x
0
).
(ii)
IfG
l
(
0
,
x
0
)
=
0 holds true for some l
∈
{
1
,
…
,
n
G
}, then there exist constants C
,
δ
¯
,
δ
1
,
δ
2
>
0 and a control u
~
∈
U such that for almost every s
′
,
t
∈
[
0
,
δ
1
) and x
∈
U
R
n
x
δ
2
(
x
0
) the following conditions hold:(22)
ϕ
t
,
x
0
,
u
∗
t
≤
C
,
ϕ
t
,
x
0
,
u
~
t
≤
C
,
∇
x
G
i
s
′
,
x
ϕ
t
,
x
0
,
u
~
t
-
ϕ
t
,
x
0
,
u
∗
t
≤
-
δ
¯
,
∀
i
∈
I
s
′
,
x
.The assumptions stated in (A
1) are typical hypotheses in optimal control. Recall that, in assumption (A
1-(v)), I
(
s
′
,
x
) represents the set of active inequalities at (
s
′
,
x
)
∈
[
0
,
T
]
×
R
n
x. On the other hand, the assumptions in (A
2) are essential to ensure a nondegenerated maximum principle. The reader is referred to [9, 10] for a detailed discussion of these constraint qualifications.It is not difficult to check that assumption (A
1) holds for the natural gas cash-out problem (2a)–(2g) at any feasible point. Finally, this general formulation allows us to deal with a smaller problem whose theoretical properties will be useful for further discussion on the gas cash-out problem. Our approach consists in reformulating problem (16) as a locally equivalent single-level problem. On the other hand, the presence of one binary variable at the lower level problem brings some additional difficulties. As mentioned earlier, we deal with that problem by considering the different cases q
=
0 and q
=
1.


### 3.3. Single-Level Reformulation

In this subsection, we replace problem (16) by an equivalent single-level optimal control problem. One typical approach in bilevel programming in finite-dimensional spaces consists in substituting the follower’s problem by its Karush-Kuhn-Tucker conditions. They are necessary and sufficient for optimality as long as the program’s functions are continuously differentiable and convex with respect to y for a fixed parameter, and some constraint qualification (such as Slater’s condition or Mangasarian-Fromovitz constraint qualification (MFCQ)) is satisfied. Hence, if the lower level problem is differentiable, convex, and a regularity condition holds, the resulting problem would be equivalent to the original one in the sense of global optimal solutions. However, from [11] it is well-known that the surrogate problem may have local optimal solutions that do not correspond to local optimal solutions of the original bilevel programming problem. Similar difficulties may appear when using this approach to tackle problem (16).In line with the above arguments, this study uses the lower level optimal value function, which allows us to derive a problem completely equivalent to (16). The resulting modified problem usually lacks differentiability and regularity [12]. Because of that, the optimal value approach has been discussed in many publications concerning bilevel programming both in the finite- and in infinite-dimensional case; compare, for instance, [13, 14]. The latter papers develop efficient realizations of the (lower level) optimal value method in optimistic bilevel programming by making use of formulas for the limiting/basic and singular subdifferential derived by Mordukhovich for the marginal/value functions (see Mordukhovich’s book [7]).In application to our case of the BOCP with the lower level represented by a conventional problem of parametric programming, the advanced techniques proposed in [13, 14] could be employed in order to find constructive (explicit) conditions to guarantee the required local Lipschitz continuity of the (lower level) objective function’s optimal value, that is, of the functions φ and φ
r, r
=
1,2, by means of vanishing their singular subdifferentials. Moreover, necessary optimality conditions for our bilevel optimal control program could be developed through the basic subdifferential of the optimal value functions. However, these prospective targets will be postponed for our future research, since, in this paper, we make use of the concept ofpartial calmness introduced in [15].Namely, we define the lower level optimal value functionφ
:
R
n
x
→
R
¯ by means of (23)
φ
x
T
≔
+
∞
if
Γ
x
T
=
∅
i
n
f
y
,
q
w
⊤
y
∣
y
,
q
∈
Γ
x
T
if
Γ
x
T
≠
∅for any x
(
T
)
∈
R
n
x and deduce(24)
Ψ
x
T
=
y
,
q
∈
Γ
x
T
∣
w
⊤
y
-
φ
x
T
≤
0from the definition of φ. Hence, we can use the latter function to replace (16) by the following equivalent single-level optimal control problem:(25)
F
x
T
,
y
,
q
⟶
m
i
n
x
,
u
,
y
,
q
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
w
⊤
y
-
φ
x
T
≤
0
y
,
q
∈
Γ
x
T
.There are three issues that need to be especially addressed when using this approach. First, it is well-known that, in general, the value functionφ may not be differentiable. Secondly, common constraint qualifications such as MFCQ, the linear independence constraint qualification, or at least their nonsmooth counterparts are too strong to hold at the boundary conditions of (25). Finally, the binary variable q could cause some problems in applying a proper constraint qualification. Hence, we have to expect that a nonsmooth maximum principle via (25) is likely to be degenerated (in certain sense).In order to cope with the above-mentioned obstacles, we follow the ideas of Ye and Zhu [15] where the authors use apartial penalization to reach a proper constraint qualification. This partial penalization is often calledpartial calmness condition, which is frequently used for theoptimal value reformulation of an optimistic bilevel programming problem (i.e., problem (25) in our case). This constraint qualification turns out to be closely related to thecalmness of a nonlinear optimization problem at a certain point (cf. [6] for the definition). Calmness for multifunctions (for perturbations of the lower level solution set) might be considered as well. Therefore, one could introduce a multifunction Δ
:
R
⇉
R
n
x
×
R
m
y
×
{
0,1
} such that we get(26)
Δ
κ
≔
x
T
,
y
,
q
∈
R
n
x
×
R
m
y
×
0,1
∣
y
,
q
∈
Γ
x
T
,
w
⊤
y
-
φ
x
T
≤
κfor any point (
x
,
u
,
y
,
q
)
∈
W and any κ
∈
R. Observe that Δ
(
κ
) is empty for any κ
<
0 while Δ
(
0
)
=
g
r
a
p
h
(
Ψ
) is valid. Results from Henrion and Surowiec [16] suggest that the calmness of Δ at (
0
,
x
∗
(
T
)
,
y
∗
,
q
∗
) for an arbitrary feasible point (
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W of (16) (referred to asvalue function constraint qualification or VFCQ for short) is more restrictive than the partial calmness condition given in Definition 3. In [17], the authors generalize the aforementioned results from [16] to bilevel programs where the upper level is an optimal control problem. Note that Henrion and Surowiec criticize (cf. [16]) the fact that optimality conditions derived from partial calmness (or VFCQ) only contain first order information. However, this is justified enough since any subdifferential of the optimal value function is a tool offirst-order analysis. They recommend representing the lower level problem by means of a generalized equation and consider the calmness of some corresponding perturbation mapping in order to obtain optimality conditions containing second-order information of the lower level as well. Observe that the lower level problem in this paper is purely linear; that is, it makes use of no second-order information and hence it makes little sense to exploit this idea here. That is why we deal with a modification of the original concept of partial calmness, and it will turn out later that our problem of interest (16) possesses this partial calmness property at any of its local optimal solutions. We want to mention here that in [18] the author already made use of partial calmness to derive necessary optimality conditions for general optimal control problems but omitted a detailed discussion on when this condition holds in optimal control (apart from the situation where minimax problems are considered).In order to define the partial calmness condition for (16), we need to consider a partially perturbed version of problem (25) given below for some real number κ:(27)
F
x
T
,
y
,
q
⟶
m
i
n
x
,
u
,
y
,
q
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
w
⊤
y
-
φ
x
T
≤
κ
y
,
q
∈
Γ
x
T
.Note that the feasible set of (27) is empty for any κ
<
0. For the purpose of a space-saving notation we introduce the Banach space X
≔
W
n
x
1,1
×
R
m
y
×
R.Definition 3.
Problem (25) is called partially calm at one of its local minimizers (
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W if there exist scalars ɛ
>
0 and η
>
0 such that for any feasible point (
x
,
u
,
y
,
q
∗
,
κ
)
∈
W
×
R of (27) satisfying the condition (
x
,
y
,
κ
)
∈
U
X
ɛ
(
x
∗
,
y
∗
,
0
) the following inequality holds:(28)
F
x
T
,
y
,
q
∗
-
F
x
∗
T
,
y
∗
,
q
∗
+
η
κ
≥
0
.Adapting a result from [9] it becomes clear that partial calmness can be characterized equivalently via partial penalization provided the optimal value function φ is locally Lipschitz continuous in a certain neighborhood of the reference point.Proposition 4.
Let(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W be a local minimizer of (25) such that φ is locally Lipschitz continuous at x
∗
(
T
). Then (25) is partially calm at (
x
∗
,
u
∗
,
y
∗
,
q
∗
) if and only if there exists a scalar η
>
0 such that (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a local minimizer of(29)
η
w
⊤
y
-
φ
x
T
+
F
x
T
,
y
,
q
⟶
m
i
n
x
,
u
,
y
,
q
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a
.
e
.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a
.
e
.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
y
,
q
∈
Γ
x
T
.In order to apply the above result, we have to find a criterion which ensures the postulated Lipschitz-property ofφ. Hence, we start a deeper analysis of the lower level problem by decomposing the lower level problem with respect to q. Let us introduce two additional set-valued mappings Γ
r
:
R
n
x
⇉
R
m
y and functions φ
r
:
R
n
x
→
R
¯, r
=
0,1, such that, for all x
(
T
)
∈
R
n
x, we get (30)
Γ
r
x
T
≔
y
∈
R
m
y
∣
A
1
x
T
+
B
1
y
+
C
1
r
≤
D
1
,
A
2
x
T
+
B
2
y
+
C
2
r
=
D
2
,
φ
r
x
T
≔
+
∞
if
Γ
r
x
T
=
∅
;
i
n
f
y
w
⊤
y
∣
y
∈
Γ
r
x
T
if
Γ
r
x
T
≠
∅
.The following lemma summarizes our results on the continuity ofΓ
0, Γ
1, and Γ.Lemma 5.
For anyx
(
T
)
∈
R
n
x, the following statements hold true: (i)
Γ
(
x
(
T
)
)
=
Γ
0
(
x
(
T
)
)
×
{
0
}
∪
Γ
1
(
x
(
T
)
)
×
{
1
}.
(ii)
The mappingΓ is polyhedral, closed, and locally upper Lipschitz continuous, as well as upper semicontinuous at any x
∗
(
T
)
∈
d
o
m
(
Γ
). Furthermore, it is locally Lipschitz continuous and lower semicontinuous at any x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
Γ
0
)
∩
d
o
m
(
Γ
1
)
).Proof.
(i) This relationship follows directly from the definitions ofΓ, Γ
0, and Γ
1.
(ii) From (i) we deduce(31)
graph
Γ
=
graph
Γ
0
×
0
∪
graph
Γ
1
×
1
.Since g
r
a
p
h
(
Γ
0
) and g
r
a
p
h
(
Γ
1
) are polyhedra by the definition, g
r
a
p
h
(
Γ
) is a polyhedral set; that is, Γ is a polyhedral mapping. Hence, it is locally upper Lipschitz continuous at any point x
∗
(
T
)
∈
d
o
m
(
Γ
) (cf. [19]). It follows from the definition of upper Lipschitz continuity that any mapping boasting this property is upper semicontinuous. The closedness of Γ follows from its being polyhedral. Now fix x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
Γ
0
)
∩
d
o
m
(
Γ
1
)
). Hence, Γ
0 and Γ
1 are locally Lipschitz continuous at x
∗
(
T
); that is, we can find scalars L
r
,
ε
r
>
0 such that for all x
(
T
)
,
x
′
(
T
)
∈
U
R
n
x
ε
r
(
x
∗
(
T
)
) one yields(32)
Γ
r
x
T
⊆
Γ
r
x
′
T
+
L
r
x
T
-
x
′
T
B
R
m
y
,for r
=
0,1. Now we apply Lemma 1 twice. First, we note that for all x
(
T
)
,
x
′
(
T
)
∈
U
R
n
x
ε
r
(
x
∗
(
T
)
)
(33)
Γ
r
x
T
×
r
⊆
Γ
r
x
′
T
×
r
+
L
r
x
T
-
x
′
T
B
R
m
y
×
0
,for r
=
0,1. Next, by defining ɛ
≔
m
i
n
{
ε
0
;
ε
1
} and L
≔
m
a
x
{
L
0
;
L
1
} we derive for all x
(
T
)
,
x
′
(
T
)
∈
U
R
n
x
ɛ
(
x
∗
(
T
)
) the following inclusion:(34)
Γ
x
T
⊆
Γ
x
′
T
+
L
x
T
-
x
′
T
B
R
m
y
+
1
,from statement (i) and Lemma 1. The above formula implies the local Lipschitz continuity of Γ at x
∗
(
T
). Finally, it follows from the definition of local Lipschitz continuity that Γ is lower semicontinuous at x
∗
(
T
) as well. Thus, the proof is complete.Lemma 6.
(i) Forr
=
0,1, the function φ
r is convex, piecewise affine, and locally Lipschitz continuous on its domain.
(ii) The optimal value function can be represented by the formulaφ
(
x
(
T
)
)
=
m
i
n
{
φ
0
(
x
(
T
)
)
;
φ
1
(
x
(
T
)
)
} for any point x
(
T
)
∈
R
n
x.
(iii) The functionφ is piecewise affine and lower semicontinuous on d
o
m
(
φ
). If x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
) holds true, that φ is locally Lipschitz continuous at x
∗
(
T
).
(iv) Forr
=
0,1, the function φ
r is subdifferentiable in the classical sense (i.e., its subdifferential is nonempty) at any point x
∗
(
T
)
∈
d
o
m
(
φ
r
), and the following formula holds:(35)
∂
φ
r
x
∗
T
=
A
1
⊤
λ
+
A
2
⊤
ν
∈
R
n
x
∣
∃
y
∗
∈
Γ
r
x
∗
T
:
w
+
B
1
⊤
λ
+
B
2
⊤
ν
=
0
m
y
,
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0
.
(v) Forr
=
0,1, the following criterion can be used to check whether x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
r
)
). Suppose that x
∗
(
T
)
∈
d
o
m
(
φ
r
) and y
∗
∈
Γ
r
(
x
∗
(
T
)
) satisfy φ
r
(
x
∗
(
T
)
)
=
w
⊤
y
∗. If the set(36)
A
1
⊤
λ
+
A
2
⊤
ν
∈
R
n
x
∣
B
1
⊤
λ
+
B
2
⊤
ν
=
0
m
y
,
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0only contains 0
n, then x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
r
)
) holds true.
(vi) The functionφ is Clarke subdifferentiable everywhere on its domain (i.e., its Clarke subdifferential is nonempty at the point x
∗
(
T
)
∈
d
o
m
(
φ
)). Introducing the set of active indices of the optimal value function I
(
x
∗
(
T
)
)
≔
{
r
∈
{
0,1
}
∣
φ
(
x
∗
(
T
)
)
=
φ
r
(
x
∗
(
T
)
)
}, the following formulas are correct: (a)
IfI
(
x
∗
(
T
)
)
=
{
r
}, then(37)
∂
c
φ
x
∗
T
=
∂
φ
r
x
∗
T
.
(b)
IfI
(
x
∗
(
T
)
)
=
{
r
,
1
-
r
}, then(38)
∂
c
φ
x
∗
T
⊆
c
o
n
v
∂
φ
r
x
∗
T
∪
∂
φ
1
-
r
x
∗
T
.Proof.
(i) This statement is well-known from linear parametric optimization (cf. [20]).
(ii) We deduce this representation directly from statement (i) of Lemma5:(39)
φ
x
T
=
inf
y
,
q
⁡
w
⊤
y
∣
y
,
q
∈
Γ
x
T
=
i
n
f
y
,
q
w
⊤
y
∣
y
,
q
∈
Γ
0
x
T
×
0
∪
Γ
1
x
T
×
1
=
min
⁡
inf
y
,
q
⁡
w
⊤
y
∣
y
,
q
∈
Γ
0
x
T
×
0
;
inf
y
,
q
⁡
w
⊤
y
∣
y
,
q
∈
Γ
1
x
T
×
1
=
min
⁡
inf
y
⁡
w
⊤
y
∣
y
∈
Γ
0
x
T
;
inf
y
⁡
w
⊤
y
∣
y
∈
Γ
1
x
T
=
min
⁡
φ
0
x
T
;
φ
1
x
T
.
(iii) We already know from statement (i) thatφ
0 and φ
1 are piecewise affine and lower semicontinuous functions, being also locally Lipschitz continuous on the interior of their domains. Due to the fact that φ is the pointwise minimum of these two functions (cf. statement (ii) of this lemma), it is piecewise affine as well.
Now, from assertion (ii) of Lemma5 we know that Γ is upper semicontinuous, which yields that φ is a lower semicontinuous function (cf. [20]). On the other hand, at any point x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
) the functions φ
0 and φ
1 are locally Lipschitz continuous, so the same holds true for φ.
(iv) One may apply the results from [21] for fully convex parametric optimization problems to the given linear optimization problems using the duality of linear programming. Note that the classical subdifferentialis not bounded at the boundary points of the domain of the optimal value function.
(v) For any fixedr
∈
{
0,1
}, the parametric optimization problem(40)
min
y
⁡
w
⊤
y
∣
y
∈
Γ
r
x
∗
Tis completely linear and hence its solution set mapping is inner semicontinuous, while the singular subdifferential of its objective function reduces to {
0
n
+
m
} (cf. [22]). Note that y
∗ is a solution of (40). We apply Theorem 7 [5] to derive(41)
∂
∞
φ
r
x
∗
T
⊆
D
∗
Γ
r
x
∗
T
,
y
∗
0
m
.In order to evaluate the above coderivative, we have to compute the basic normal cone(42)
N
graph
Γ
r
B
x
∗
T
,
y
∗
.
Observe thatg
r
a
p
h
(
Γ
r
) is a polyhedron; that is, it is closed and convex. Hence, this cone coincides with the corresponding (classical) normal cone defined as(43)
N
graph
Γ
r
x
∗
T
,
y
∗
=
A
1
⊤
λ
+
A
2
⊤
ν
B
1
⊤
λ
+
B
2
⊤
ν
∈
R
n
x
+
m
y
∣
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0
,since at least Abadie Constraint Qualification holds at any feasible point of a purely linear optimization problem. It follows from (41) and the definition of the normal coderivative D
∗
Γ
r
(
x
∗
(
T
)
,
y
) that the inclusion(44)
∂
∞
φ
r
x
∗
T
⊆
A
1
⊤
λ
+
A
2
⊤
ν
∈
R
n
x
∣
B
1
⊤
λ
+
B
2
⊤
ν
=
0
m
y
,
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0is true; that is, the criterion from statement (v) implies ∂
∞
φ
r
(
x
∗
(
T
)
)
=
{
0
n
}. Consequently, φ
r is Lipschitz continuous in a neighborhood of x
∗
(
T
), which is only possible if x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
r
)
).
(vi) These formulas follow from the calculation rules of the Clarke subdifferential stated in [6].Note that the criterion from statement (v) of the above lemma always holds if, for a fixedx
∗
(
T
), the linear problem (40) is solvable, while Γ
(
x
∗
(
T
)
) possesses an interior point. In order to make this clear, recall that, in the latter case, the Slater condition holds true for problem (40) and the set of singular Lagrange multipliers(45)
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
∣
B
1
⊤
λ
+
B
2
⊤
ν
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0reduces to {
(
0
m
g
,
0
m
h
)
}. In general, one may use statement (
v
) as a criterion to check whether x
∗
(
T
) comes from i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
)
=
i
n
t
(
d
o
m
(
φ
0
)
)
∩
i
n
t
(
d
o
m
(
φ
1
)
), that is, whether φ is locally Lipschitz continuous in a neighborhood of x
∗
(
T
). This condition will play an important role in our main results, that is, Theorems 7, 8, and 10.In order to present our next result, we need to introduce two surrogate single-level optimal control problems that arise from (25) and its partially perturbed version (27) by fixing the binary variable value q either to 0 or to 1. Hence, for any r
∈
{
0,1
} we define(46)
F
x
T
,
y
,
r
⟶
m
i
n
x
,
u
,
y
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
w
⊤
y
-
φ
r
x
T
≤
0
y
∈
Γ
r
x
T
,
(47)
F
x
T
,
y
,
r
⟶
m
i
n
x
,
u
,
y
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
w
⊤
y
-
φ
r
x
T
≤
κ
y
∈
Γ
r
x
T
.The following theorem reveals that (16) isalways partially calm in the sense of Definition 3.Theorem 7.
Let(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W be a feasible point of (16) satisfying x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
). Then (16) is partially calm at this point. In particular, if (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a local minimizer of (16), then there exists an η
>
0 such that (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a local minimizer of (29), too.Proof.
Denote byW
′
≔
W
n
x
1,1
×
L
n
u
1
×
R
m
y. Since (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a feasible point of (16), (
y
∗
,
q
∗
) is a global optimal solution for the lower level problem with the fixed parameter x
∗
(
T
). Hence, we have φ
(
x
∗
(
T
)
)
=
φ
q
∗
(
x
∗
(
T
)
)
=
w
⊤
y
∗. That is why (
x
∗
,
u
∗
,
y
∗
) is feasible for problem (46) with r
=
q
∗. The function φ
q
∗ appearing therein is the optimal value function of a purely linear parametric optimization problem. Therefore, we may apply the results of Section  3 in [9] in order to find an ε
>
0 and a scalar η
′
>
0 such that, for any feasible point (
x
,
u
,
y
,
κ
)
∈
W
′
×
R of (47) with (
x
,
y
,
κ
)
∈
U
X
ε
(
x
∗
,
y
∗
,
0
) (and r
=
q
∗), we have(48)
F
x
T
,
y
,
q
∗
-
F
x
∗
T
,
y
∗
,
q
∗
+
η
′
κ
≥
0
.Now choose an arbitrary feasible point (
x
,
u
,
y
,
q
∗
,
κ
)
∈
W
×
R of (27) satisfying (
x
,
y
,
κ
)
∈
U
X
ε
(
x
∗
,
y
∗
,
0
). Then (
x
,
u
,
y
,
κ
) is feasible for problem (47) for r
=
q
∗ since from Lemma 6 we have(49)
κ
≥
w
⊤
y
-
φ
x
T
=
w
⊤
y
-
min
⁡
φ
0
x
T
;
φ
1
x
T
≥
w
⊤
y
-
φ
q
∗
x
T
.For any such point (48) holds true; that is, (16) is partially calm at (
x
∗
,
u
∗
,
y
∗
,
q
∗
) in the sense of Definition 3. The second part of the statement follows now easily taking Proposition 4 and Lemma 6 into account.General classes of bilevel programming problems that are partially calm can be found in Ye and Zhu [15], Dempe and Zemkoho [23], and more recently Benita and Mehlitz [17] and Benita et al. [9]. Furthermore, any minimax problem is partially calm at its local optimal solutions. Apart from these classes, there are two well-known conditions ensuring the partial calmness, namely, (i) the property of the lower level problem to have a so-calleduniformly weak sharp minimum (cf. [15]) and (ii) the above-mentioned condition VFCQ. In [9, 17], it is asserted that a BOCP with a finite-dimensional linear lower level problem is always partially calm since its lower level boasts a uniformly weak sharp minimum. Recall that we implicitly used this result when proving Theorem 7.


### 3.4. Optimality Conditions

In this subsection, we present an appropriate formulation of the maximum principle for problem (16). Since, in our notion of local optimality, we consider the binary variable to be fixed, it is possible to proceed as in [9]. We postulate assumptions that allow us to transform (16) into the single-level nonsmooth optimal control problem (29) by means of Theorem 7. Afterwards, we apply a maximum principle (cf. [8, 9]) to (29) and exploit the subdifferential formulas for φ we introduced in Lemma 6. We omit the proof here and refer the interested reader to the recent paper [9].Theorem 8.
Let(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W be a local minimizer of (16), assume that (A
1)-(A
2) hold, and let x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
) be satisfied. (a)
Suppose thatI
(
x
∗
(
T
)
)
=
{
q
∗
} holds (recall Lemma 6 for the definition of this set). Then there exist a function θ
∈
W
n
x
1,1, vectors λ
1
,
λ
2
∈
R
0
m
g
,
+, ν
1
,
ν
2
∈
R
m
h, measures μ
1
,
…
,
μ
n
G
∈
C
⊕, and scalars τ
≥
0, η
>
0 such that the we have (for almost every t
∈
[
0
,
T
]) the following:
(i)
The nontriviality condition is(50)
τ
+
p
L
n
u
∞
+
∑
l
=
1
n
G
μ
l
0
,
T
>
0
.
(ii)
The adjoint equation is(51)
-
θ
˙
t
⊤
=
p
t
⊤
∇
x
ϕ
t
,
x
∗
t
,
u
∗
t
.
(iii)
The Weierstrass-Pontryagin condition is(52)
p
t
⊤
ϕ
t
,
x
∗
t
,
u
∗
t
=
max
v
∈
U
t
⁡
p
t
⊤
ϕ
t
,
x
∗
t
,
v
.
(iv)
The transversality condition is(53)
-
p
T
=
τ
·
∇
x
F
x
∗
T
,
y
∗
,
q
∗
⊤
+
A
1
⊤
λ
1
-
τ
η
·
λ
2
+
A
2
⊤
ν
1
-
τ
η
·
ν
2
.
(v)
The support condition is(54)
supp
⁡
μ
l
⊆
t
∈
0
,
T
∣
G
l
t
,
x
∗
t
=
0
,
l
∈
1
,
…
,
n
G
.
(vi)
The lower level optimality condition is(55)
w
+
B
1
⊤
λ
2
+
B
2
⊤
ν
2
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
q
∗
-
D
1
⊤
λ
2
=
0
.
(vii)
The complementarity condition is(56)
A
1
x
∗
T
+
B
1
y
∗
+
C
1
q
∗
-
D
1
⊤
λ
1
=
0
.
(viii)
The multiplier condition is(57)
τ
·
∇
y
F
x
∗
T
,
y
∗
,
q
∗
⊤
+
η
·
w
+
B
1
⊤
λ
1
+
B
2
⊤
ν
1
=
0
m
y
.
Here, the functionp is defined as follows for almost every t
∈
[
0
,
T
]:(58)
p
t
≔
θ
t
+
∫
0
,
t
∑
l
=
1
n
G
∇
x
G
l
ξ
,
x
∗
ξ
⊤
μ
l
d
ξ
,
i
f
t
<
T
;
θ
T
+
∫
0
,
T
∑
l
=
1
n
G
∇
x
G
l
ξ
,
x
∗
ξ
⊤
μ
l
d
ξ
,
i
f
t
=
T
.
(b)
Suppose thatI
(
x
∗
(
T
)
)
=
{
q
∗
,
1
-
q
∗
} holds. Then we find a function θ
∈
W
n
x
1,1, vectors λ
1
,
λ
2
,
λ
3
∈
R
0
m
g
,
+, ν
1
,
ν
2
,
ν
3
∈
R
m
h, y
¯
∈
R
m
y, measures μ
1
,
…
,
μ
n
G
∈
C
⊕, constants τ
≥
0, η
>
0, and α
∈
[
0,1
] such that conditions (i), (ii), (iii), (v), (vii), and (viii) hold true, together with relationships (ix) and (x) listed below:
(ix)
The modified transversality condition(59)
-
p
T
=
τ
·
∇
x
F
x
∗
T
,
y
∗
,
q
∗
⊤
+
A
1
⊤
λ
1
-
τ
η
·
α
λ
2
+
1
-
α
λ
3
+
A
2
⊤
ν
1
-
τ
η
·
α
ν
2
+
1
-
α
ν
3
.
(x)
The modified lower level optimality condition(60)
w
+
B
1
⊤
λ
2
+
B
2
⊤
ν
2
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
q
∗
-
D
1
⊤
λ
2
=
0
,
w
+
B
1
⊤
λ
3
+
B
2
⊤
ν
3
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
¯
+
C
1
1
-
q
∗
-
D
2
⊤
λ
3
=
0
,
A
1
x
∗
T
+
B
1
y
¯
+
C
1
1
-
q
∗
≤
D
1
,
A
2
x
∗
T
+
B
2
y
¯
+
C
2
1
-
q
∗
=
D
2
.
Here, the functionp is defined as given in (58).Now we illustrate the above theory by means of an example. Observe that it is an adaptation of the BOCP that the second and third authors already discussed in [9]. Here we modify the upper level objective function and the lower level problem in order to fit the settings of this paper.Example 9.
Consider the bilevel optimal control problem(61)
x
2
3
+
1
2
y
1
-
2
2
+
1
2
y
2
+
1
2
⟶
min
⁡
x
,
u
,
y
,
q
⟶
subject  to
x
˙
1
t
=
u
t
a.e.
t
∈
0,3
,
⟶
subject  to
x
˙
2
t
=
x
1
t
a.e.
t
∈
0,3
,
⟶
subject  to
x
1
0
=
1
,
⟶
subject  to
x
2
0
=
0
,
⟶
subject  to
u
t
∈
-
1,1
a.e.
t
∈
0,3
,
⟶
subject  to
-
x
1
t
≤
0
∀
t
∈
0,3
,
⟶
subject  to
y
,
q
∈
Ψ
x
3
,where(62)
Ψ
x
3
≔
Argmin
y
,
q
⁡
-
y
1
-
2
y
2
∣
-
x
1
3
+
y
1
+
y
2
≤
1
,
y
1
+
3
q
≤
3
,
y
2
-
q
≤
0
,
-
y
1
≤
0
,
-
y
2
≤
0
,
q
∈
0,1
.
A similar argumentation as presented in [9] reveals that its global minimizer (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is given as stated below (for almost every t
∈
[
0,3
]):(63)
x
1
∗
t
=
1
-
t
,
if
t
∈
0,1
;
0
,
if
t
∈
1,2
;
t
-
2
,
if
t
∈
2,3
,
x
2
∗
t
=
1
2
-
1
2
t
-
1
2
,
if
t
∈
0,1
;
1
2
,
if
t
∈
1,2
;
1
2
+
1
2
t
-
2
2
,
if
t
∈
2,3
,
u
∗
t
=
-
1
,
if
t
∈
0,1
;
0
,
if
t
∈
1,2
;
1
,
if
t
∈
2,3
,
y
1
∗
=
2
,
y
2
∗
=
0
,
q
∗
=
0
.It is easy to see that the assumptions of Theorem8 hold for problem (61). Now we demonstrate that the corresponding necessary optimality conditions are satisfied.Observe that the optimal value functionsφ
0
,
φ
1
:
R
2
→
R
¯ of the lower level problem (62) take the following values for an arbitrary (terminal) point x
(
3
)
∈
R
2:(64)
φ
0
x
3
=
+
∞
,
if
x
1
3
∈
-
∞
,
-
1
;
-
x
1
3
-
1
,
if
x
1
3
∈
-
1,2
;
-
3
,
if
x
1
3
∈
2
,
+
∞
,
φ
1
x
3
=
+
∞
,
if
x
1
3
∈
-
∞
,
-
1
;
-
2
x
1
3
-
2
,
if
x
1
3
∈
-
1,0
;
-
2
,
if
x
1
3
∈
0
,
+
∞
.Thenx
∗
(
3
) is an interior point of d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
), and I
(
x
∗
(
3
)
)
=
{
0,1
} holds true. Due to Theorem 8, there exist a function θ
∈
W
2
1,1, vectors λ
1
,
λ
2
,
λ
3
∈
R
0
5
,
+, y
¯
∈
R
2, a measure μ
∈
C
⊕, constants τ
≥
0, η
>
0, and α
∈
[
0,1
] which satisfy the following set of conditions (for almost every t
∈
[
0,3
]):(i)
The nontriviality condition is(65)
τ
+
p
L
2
∞
+
μ
0,3
>
0
.
(ii)
The adjoint equation is(66)
-
θ
˙
1
t
=
p
2
t
,
-
θ
˙
2
t
=
0
.
(iii)
The Weierstrass-Pontryagin Condition is(67)
p
1
t
·
u
∗
t
+
p
2
t
·
x
1
∗
t
=
max
v
∈
-
1,1
⁡
p
1
t
·
v
+
p
2
t
·
x
1
∗
t
.
(v)
The support condition is(68)
supp
⁡
μ
⊆
1,2
.
(vii)
The complementarity condition is(69)
λ
1,2
=
0
,
λ
1,4
=
0
.
(viii)
The multiplier condition is(70)
-
τ
η
+
λ
1,1
+
λ
1,2
-
λ
1,4
=
0
,
τ
-
2
τ
η
+
λ
1,1
+
λ
1,3
-
λ
1,5
=
0
.
(x)
The modified transversality condition is(71)
-
p
1
3
=
-
λ
1,1
-
τ
η
α
λ
2,1
+
1
-
α
λ
3,1
,
-
p
2
3
=
τ
.
(xi)
The modified lower level optimality condition is(72)
-
1
+
λ
2,1
+
λ
2,2
-
λ
2,4
=
0
,
λ
2,2
=
0
,
λ
2,4
=
0
,
-
2
+
λ
2,1
+
λ
2,3
-
λ
2,5
=
0
,
-
1
+
λ
3,1
+
λ
3,2
-
λ
3,4
=
0
,
λ
3,1
=
0
,
λ
3,5
=
0
,
-
2
+
λ
3,1
+
λ
3,3
-
λ
3,5
=
0
,
y
¯
1
=
0
,
y
¯
2
=
1
.Here, the function p
∈
L
2
∞ is defined as follows for almost every t
∈
[
0,3
]:(73)
p
1
t
=
θ
1
t
-
∫
0
,
t
μ
d
ξ
,
if
t
<
3
;
θ
1
3
-
∫
0,3
μ
d
ξ
,
if
t
=
3
,
p
2
t
=
θ
2
t
.Note that we already computed the lower level solution y
¯ for the fixed x
∗
(
3
) and 1
-
q
∗ in (xi) to make the latter condition more convenient. As a consequence, (xi) yields λ
2,1
=
1, λ
2,3
=
λ
2,5
+
1, λ
3,3
=
2, and λ
3,2
=
λ
3,4
+
1. Taking (vi) and (vii) together we obtain λ
1,1
=
τ
η and λ
1,3
=
λ
1,5
+
τ
(
η
-
1
). Substituting these representations into (x) leads to p
1
(
3
)
=
τ
η
(
1
-
α
) and p
2
(
3
)
=
-
τ.Taking into account (ii) and the definition ofp, we derive θ
2
≡
-
τ, p
2
≡
-
τ, and θ
1
(
t
)
=
τ
·
t
+
c for some constant c
∈
R and almost every t
∈
[
0,3
]. We evaluate (iii) to obtain(74)
t
∈
0,1
⟹
p
1
t
≤
0
,
t
∈
1,2
⟹
p
1
t
=
0
,
t
∈
2,3
⟹
p
1
t
≥
0
.In order to satisfy the latter condition, as well as the definition of p, we choose c
≔
-
τ and μ
≔
τ
·
(
l
∘
I
[
1,2
]
), where l denotes the Lebesgue measure and I
[
1,2
] represents the intersection mapping with the interval [
1,2
]; that is, I
[
1,2
]
(
M
)
=
M
∩
[
1,2
] for all M
⊆
R. This leads to the following representation of θ
1 and p
1 for almost every t
∈
[
0,3
]:(75)
θ
1
t
=
τ
·
t
-
τ
,
p
1
t
=
τ
·
t
-
τ
,
if
t
∈
0,1
;
0
,
if
t
∈
1,2
;
τ
·
t
-
2
τ
,
if
t
∈
2,3
.In order to satisfy the terminal condition p
1
(
3
)
=
τ
η
(
1
-
α
) we derived earlier, we finally fix α
≔
1
-
1
/
η for an arbitrary η
≥
1 to guarantee α
∈
[
0,1
].Resuming the above calculations while taking into account (i), the following multipliers satisfy the necessary optimality conditions postulated in Theorem8 (definitions hold for almost every t
∈
[
0,3
] when necessary) for any choice of η
≥
1:(76)
θ
1
t
=
τ
·
t
-
τ
,
θ
2
t
=
-
τ
,
λ
1
=
τ
η
0
τ
η
-
1
0
0
,
λ
2
=
1
0
1
0
0
,
λ
3
=
0
1
2
0
0
,
y
¯
=
0
1
,
μ
=
τ
·
l
∘
I
1,2
,
τ
>
0
,
α
=
1
-
1
η
.This result underlines that the partial calmness property (that we used to derive these optimality conditions) theoretically is closely related to partial penalization. One may interpret η as penalization parameter and observe that the necessary optimality conditions above hold for any η which is greater than or equal to some lower bound (which is 1 in this example).


## 3.1. Preliminaries and Further Notation

Throughout this paper, we denote byR, R
n, R
m
×
n, R
+
n, and R
¯
≔
R
∪
{
-
∞
,
∞
} the set of real numbers, the space of all real vectors with n components, the space of all real matrices with m rows and n columns, the nonnegative orthant of R
n, and the extended real line, respectively. For any matrix X
∈
R
m
×
n, let X
⊤
∈
R
n
×
m denote its transpose. Next, for an arbitrary subset M
⊆
R
n, we use i
n
t
(
M
), r
i
(
M
), and c
o
n
v
(
M
) in order to denote the interior, the relative interior, and the convex hull of M, respectively. For x
∗
∈
M, we define theFréchet normal cone
N
^
M
(
x
∗
) to M at x
∗ by means of(10)
N
^
M
x
∗
≔
d
∈
R
n
∣
limsup
x
→
x
∗
,
x
∈
M
⁡
x
-
x
∗
⊤
d
x
-
x
∗
≤
0
. Here, · is an arbitrary norm in R
n. Furthermore, thebasic normal cone (sometimes referred to asMordukhovich normal cone) N
M
B
(
x
∗
) to M at x
∗ is given by(11)
N
M
B
x
∗
≔
limsup
x
→
x
∗
,
x
∈
M
⁡
N
^
M
x
,where the upper limit has to be interpreted in the sense of Painlevé-Kuratowski (cf. [4]). If M is a convex set, then N
^
M
(
x
∗
) and N
M
B
(
x
∗
) both coincide with the normal cone of convex analysis, which we denote by N
M
(
x
∗
). Let us denote by U
R
n and B
R
n the open and closed unit balls in R
n, and, for any ɛ
>
0
,
x
∗
∈
R
n, we define U
R
n
ɛ
(
x
∗
)
≔
{
x
∗
}
+
ɛ
U
R
n and B
R
n
ɛ
(
x
∗
)
≔
{
x
∗
}
+
ɛ
B
R
n, respectively. Given a differentiable function F
:
R
n
→
R
m, its Jacobian at x
∈
R
n is represented by ∇
F
(
x
)
∈
R
m
×
n. Next, we denote by C and C
∗ the space of scalar continuous functions defined over the interval [
0
,
T
] and the dual space of C, respectively. The set of elements in C
∗ taking nonnegative values at nonnegative functions in C is denoted by C
⊕. Given a nonnegative measure μ
∈
C
⊕, its norm μ
C
∗ coincides with the total variation of μ defined as ∫
0
T
‍
μ
(
d
s
) and the support of the measure μ; written s
u
p
p
(
μ
) is the smallest closed set A
⊆
[
0
,
T
] such that for any relatively open subset B
⊆
[
0
,
T
]
∖
A one has μ
(
B
)
=
0. The Euclidean norm of a vector x
∈
R
n is denoted by x, the space of all Lebesgue-integrable functions w such that w
:
[
0
,
T
]
→
R
n is described by L
n
1, and by W
n
1,1 we represent the Sobolev space that contains all absolutely continuous R
n-valued functions on [
0
,
T
], whose weak derivatives belong to L
n
1. By L
n
∞ we denote the Banach space of all vector-functions with n essentially bounded components defined over [
0
,
T
]. Furthermore, by L
×
B
n we express the product σ-algebra generated by the Lebesgue set L and the Borel subsets of R
n.For a lower semicontinuous functionalf
:
R
n
→
R
¯, we introduce its domain as d
o
m
(
f
)
≔
{
x
∈
R
n
∣
f
x
<
+
∞
}. Suppose that x
∗
∈
d
o
m
(
f
) is fixed. Then we define theFréchet subdifferential
∂
^
f
(
x
∗
) of f at x
∗ as(12)
∂
^
f
x
∗
≔
a
∈
R
n
∣
liminf
x
→
x
∗
⁡
f
x
-
f
x
∗
-
x
-
x
∗
⊤
a
x
-
x
∗
≥
0
.Furthermore, we make use of thesingular subdifferential
∂
∞
f
(
x
∗
) of f at x
∗, which is defined as stated below:(13)
∂
∞
f
x
∗
≔
limsup
x
→
x
∗
,
α
↘
0
⁡
α
·
∂
^
f
x
.Note that ∂
∞
f
(
x
∗
)
=
{
0
n
} holds if and only if f is locally Lipschitz continuous at x
∗ (cf. [5]). In the latter case ∂
c
f
(
x
∗
), the Clarke subdifferential of f at x
∗ is a nonempty, compact, and convex set (cf. [6]) and consequently we have x
∗
∈
i
n
t
(
d
o
m
(
f
)
). Suppose that f is a convex functional and x
∗
∈
r
i
(
d
o
m
(
f
)
) is chosen arbitrarily. Then ∂
^
f
(
x
∗
) and ∂
c
f
(
x
∗
) both coincide with the classical subdifferential of f at x
∗, the latter being denoted by ∂
f
(
x
∗
). For further information on these concepts of variational analysis, we refer the interested reader to [7].LetΘ
:
R
n
⇉
R
m be an arbitrary set-valued mapping. The domain and graph of Θ are denoted, respectively, by d
o
m
(
Θ
) and g
r
a
p
h
(
Θ
). We say that Θ is apolyhedral mapping provided that its graph is the union of a finite collection of polyhedra. The mapping Θ is calledlocally Lipschitz continuous at x
∗
∈
R
n whenever there exist scalars L
Θ
,
ε
Θ
>
0 such that for all x
,
x
′
∈
U
R
n
ε
Θ
(
x
∗
) the following condition is satisfied:(14)
Θ
x
⊆
Θ
x
′
+
L
Θ
x
-
x
′
B
R
n
.If the above inclusion holds only when x
′
≔
x
∗ is fixed, then Θ is calledlocally upper Lipschitz continuous at x
∗. We call Θ
upper (lower)semicontinuous at x
∗ provided that for any open set O
⊆
R
m satisfying Θ
(
x
∗
)
⊆
O (Θ
(
x
∗
)
∩
O
≠
∅) we find ɛ
>
0 such that Θ
(
x
)
⊆
O (Θ
(
x
)
∩
O
≠
∅) holds true for all x
∈
U
R
n
ɛ
(
x
∗
). Now choose an arbitrary point (
x
∗
,
y
∗
)
∈
g
r
a
p
h
(
Θ
). We say that Θ isinner semicontinuous at (
x
∗
,
y
∗
) if for any sequence {
x
k
}
⊆
R
n converging to x
∗ we find a sequence {
y
k
}
⊆
R
m converging to y
∗ and k
0
∈
N such that y
k
∈
Θ
(
x
k
) is true for all k
∈
N greater than k
0. Obviously, if Θ is locally Lipschitz continuous at x
∗, then it is inner semicontinuous at any point (
x
∗
,
y
¯
) with y
¯
∈
Θ
(
x
∗
). Thenormal coderivative
D
∗
Θ
(
x
∗
,
y
∗
)
:
R
m
⇉
R
n of Θ at (
x
∗
,
y
∗
) is defined as stated below for any y
∈
R
m:(15)
D
∗
Θ
x
∗
,
y
∗
y
≔
x
∈
R
n
∣
x
,
-
y
∈
N
graph
Θ
B
x
∗
,
y
∗
.Finally, we recall some helpful calculation rules concerning the Minkowski sum of sets. Due to its simplicity the corresponding proof is omitted here.Lemma 1.
LetA
,
B
,
C
,
D
⊆
R
n be arbitrary sets. Then the following statements hold:(i)
(
A
+
B
)
∪
(
C
+
D
)
⊆
(
A
∪
C
)
+
(
B
∪
D
);
(ii)
A
⊆
B
+
C
⇒
A
×
D
⊆
(
B
×
D
)
+
(
C
×
{
0
n
}
).


## 3.2. General Setting

In order to derive optimality conditions for the natural gas cash-out problem (2a)–(2g) where the lower level problem (3a)–(3k) is replaced with (4a)–(4j), we are going to develop a general formulation. The idea is to derive general optimality conditions, and by applying those theoretical results one can easily provide optimality conditions to the original problem of interest.Let us rewrite problem (2a)–(2g) as anoptimistic BOCP such that(16)
F
x
T
,
y
,
q
⟶
m
i
n
x
,
u
,
y
,
q
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
y
,
q
∈
Ψ
x
T
,where(17)
Ψ
x
T
≔
Argmin
y
,
q
⁡
w
⊤
y
∣
y
,
q
∈
Γ
x
T
.The problem’s data comprise an interval[
0
,
T
] for a fixed final time moment T
>
0, given initial conditions x
0
∈
R
n
x, functions F
:
R
n
x
×
R
m
y
×
{
0,1
}
→
R, ϕ
:
[
0
,
T
]
×
R
n
x
×
R
n
u
→
R
n
x, G
:
[
0
,
T
]
×
R
n
x
→
R
n
G, and a multivalued mapping U
:
[
0
,
T
]
⇉
R
n
u that is measurable on [
0
,
T
]. The feasible set of control functions is U
≔
{
u
:
[
0
,
T
]
→
R
n
u
∣
u
∈
L
n
u
1
,
u
(
t
)
∈
U
(
t
)
a
.
e
.
t
∈
[
0
,
T
]
}. The state trajectory x
∈
W
n
x
1,1 is an absolutely continuous function that satisfies the differential equation and the initial conditions for some control function u
∈
L
n
u
1. Finally, Ψ
:
R
n
x
⇉
R
m
y
×
{
0,1
} denotes the solution set mapping of the lower level problem, while w
∈
R
m
y is a fixed vector and Γ
:
R
n
x
⇉
R
m
y
×
{
0,1
} is a set-valued mapping that will be specified below.In other words, problem (16) is an optimistic BOCP with final-state-dependent finite-dimensional lower level. Moreover, the upper level problem boasts a Mayer-type cost function and state constraints. This formulation is notably interesting due to the parametric optimization problem at the lower level, whose parameter is nothing else but the final state of the upper level state variable. Hence, the natural gas cash-out problem specified by (2a)–(2g) fits into the formulation of problem (16).Taking into account the POC’s problem (4a)–(4j) one can define the set Γ as follows:(18)
Γ
x
T
≔
y
,
q
∈
R
m
y
×
0,1
∣
A
1
x
T
+
B
1
y
+
C
1
q
≤
D
1
,
A
2
x
T
+
B
2
y
+
C
2
q
=
D
2
,where A
1
∈
R
m
g
×
n
x, A
2
∈
R
m
h
×
n
x, B
1
∈
R
m
g
×
m
y, B
2
∈
R
m
h
×
m
y, C
1
,
D
1
∈
R
m
g, and C
2
,
D
2
∈
R
m
h are given matrices. When comparing the original problem (2a)–(2g) and the general formulation in (16), it is not difficult to see that we have n
x
=
n
u
=
n, n
G
=
2
n
+
2, m
y
=
n
2
+
2
n
+
2, m
g
=
3
n
2
+
5
n
+
2, and m
h
=
n
+
1.Let us consider the spaceW
≔
W
n
x
1,1
×
L
n
u
1
×
R
m
y
×
{
0,1
}. Then the process (
x
,
u
,
y
,
q
)
∈
W is said to befeasible for (16) if it satisfies the dynamical system, the initial condition, and the pure state constraints, while (
y
,
q
) is a global optimal solution for the corresponding lower level problem. Now we introduce the definition of a local minimizer.Definition 2.
Take a feasible process(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W. Then (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a local minimizer of problem (16) if there exists ɛ
>
0 such that(19)
F
x
T
∗
,
y
∗
,
q
∗
≤
F
x
T
,
y
,
q
∗holds provided that (
x
,
y
)
∈
U
W
n
x
1,1
×
R
m
y
ε
(
x
∗
,
y
∗
), and (
x
,
u
,
y
,
q
∗
) is feasible for (16).Clearly, the optimality conditions for local minimizers automatically hold for strong and hence for global minimizers. By following the approach in Vinter [8], the above definition respects our desire to focus on the state variables of (16) while ignoring somehow the control function’s behavior. Additionally, fixing the binary variable q proposes a strategy about how to deal with (16). We compute possible minimizers for the problems that arise when setting q
=
0 and q
=
1 and then compare the resulting points. Note that assuming q to be free in the definition of local optimal solutions is another idea we are not going to examine here.For an arbitrary local minimum point(
x
∗
,
u
∗
,
y
∗
,
q
∗
) of (16), we accept the following assumptions:(A
1)
(i)
For a fixedq
≔
q
∗, the function F is continuously differentiable with respect to all their arguments.
(ii)
The function(
t
,
u
)
↦
ϕ
(
t
,
x
,
u
) is L
×
B
n
u-measurable for each x
∈
R
n
x.
(iii)
There exist aL
×
B
n
u-measurable function ζ
:
R
n
u
→
R and a constant δ
>
0 such that t
↦
ζ
(
u
∗
(
t
)
) is integrable and (20)
ϕ
t
,
x
,
u
-
ϕ
t
,
x
′
,
u
≤
ζ
x
-
x
′
.
Forx
,
x
′
∈
U
R
n
x
δ
(
x
∗
(
t
)
), u
∈
U
(
t
) a.e. t
∈
[
0
,
T
].
(iv)
The setg
r
a
p
h
(
U
) is L
×
B
n
u measurable.
(v)
The component functionsG
1
,
…
,
G
n
G
:
[
0
,
T
]
×
R
n
x
→
R of G are continuously differentiable with respect to all their arguments. Furthermore, for any t
∈
[
0
,
T
] the set {
∇
x
G
l
(
t
,
x
∗
(
t
)
)
∣
l
∈
I
(
t
,
x
∗
(
t
)
)
} is positive linearly independent; therein, for any s
′
∈
[
0
,
T
] and x
∈
R
n
x we define(21)
I
s
′
,
x
≔
l
∈
1
,
…
,
n
G
∣
G
l
s
′
,
x
=
max
⁡
G
1
s
′
,
x
;
…
;
G
n
G
s
′
,
x
.
(A
2)
(i)
IfG
l
(
0
,
x
0
)
=
0 holds true for some l
∈
{
1
,
…
,
n
G
}, then there exist constants ε
1
,
ε
2
>
0 such that the set {
ϕ
(
s
′
,
x
,
v
)
∈
R
n
x
∣
v
∈
U
(
s
′
)
} is convex for any s
′
∈
[
0
,
ε
1
) and any x
∈
U
R
n
x
ε
2
(
x
0
).
(ii)
IfG
l
(
0
,
x
0
)
=
0 holds true for some l
∈
{
1
,
…
,
n
G
}, then there exist constants C
,
δ
¯
,
δ
1
,
δ
2
>
0 and a control u
~
∈
U such that for almost every s
′
,
t
∈
[
0
,
δ
1
) and x
∈
U
R
n
x
δ
2
(
x
0
) the following conditions hold:(22)
ϕ
t
,
x
0
,
u
∗
t
≤
C
,
ϕ
t
,
x
0
,
u
~
t
≤
C
,
∇
x
G
i
s
′
,
x
ϕ
t
,
x
0
,
u
~
t
-
ϕ
t
,
x
0
,
u
∗
t
≤
-
δ
¯
,
∀
i
∈
I
s
′
,
x
.The assumptions stated in (A
1) are typical hypotheses in optimal control. Recall that, in assumption (A
1-(v)), I
(
s
′
,
x
) represents the set of active inequalities at (
s
′
,
x
)
∈
[
0
,
T
]
×
R
n
x. On the other hand, the assumptions in (A
2) are essential to ensure a nondegenerated maximum principle. The reader is referred to [9, 10] for a detailed discussion of these constraint qualifications.It is not difficult to check that assumption (A
1) holds for the natural gas cash-out problem (2a)–(2g) at any feasible point. Finally, this general formulation allows us to deal with a smaller problem whose theoretical properties will be useful for further discussion on the gas cash-out problem. Our approach consists in reformulating problem (16) as a locally equivalent single-level problem. On the other hand, the presence of one binary variable at the lower level problem brings some additional difficulties. As mentioned earlier, we deal with that problem by considering the different cases q
=
0 and q
=
1.


## 3.3. Single-Level Reformulation

In this subsection, we replace problem (16) by an equivalent single-level optimal control problem. One typical approach in bilevel programming in finite-dimensional spaces consists in substituting the follower’s problem by its Karush-Kuhn-Tucker conditions. They are necessary and sufficient for optimality as long as the program’s functions are continuously differentiable and convex with respect to y for a fixed parameter, and some constraint qualification (such as Slater’s condition or Mangasarian-Fromovitz constraint qualification (MFCQ)) is satisfied. Hence, if the lower level problem is differentiable, convex, and a regularity condition holds, the resulting problem would be equivalent to the original one in the sense of global optimal solutions. However, from [11] it is well-known that the surrogate problem may have local optimal solutions that do not correspond to local optimal solutions of the original bilevel programming problem. Similar difficulties may appear when using this approach to tackle problem (16).In line with the above arguments, this study uses the lower level optimal value function, which allows us to derive a problem completely equivalent to (16). The resulting modified problem usually lacks differentiability and regularity [12]. Because of that, the optimal value approach has been discussed in many publications concerning bilevel programming both in the finite- and in infinite-dimensional case; compare, for instance, [13, 14]. The latter papers develop efficient realizations of the (lower level) optimal value method in optimistic bilevel programming by making use of formulas for the limiting/basic and singular subdifferential derived by Mordukhovich for the marginal/value functions (see Mordukhovich’s book [7]).In application to our case of the BOCP with the lower level represented by a conventional problem of parametric programming, the advanced techniques proposed in [13, 14] could be employed in order to find constructive (explicit) conditions to guarantee the required local Lipschitz continuity of the (lower level) objective function’s optimal value, that is, of the functions φ and φ
r, r
=
1,2, by means of vanishing their singular subdifferentials. Moreover, necessary optimality conditions for our bilevel optimal control program could be developed through the basic subdifferential of the optimal value functions. However, these prospective targets will be postponed for our future research, since, in this paper, we make use of the concept ofpartial calmness introduced in [15].Namely, we define the lower level optimal value functionφ
:
R
n
x
→
R
¯ by means of (23)
φ
x
T
≔
+
∞
if
Γ
x
T
=
∅
i
n
f
y
,
q
w
⊤
y
∣
y
,
q
∈
Γ
x
T
if
Γ
x
T
≠
∅for any x
(
T
)
∈
R
n
x and deduce(24)
Ψ
x
T
=
y
,
q
∈
Γ
x
T
∣
w
⊤
y
-
φ
x
T
≤
0from the definition of φ. Hence, we can use the latter function to replace (16) by the following equivalent single-level optimal control problem:(25)
F
x
T
,
y
,
q
⟶
m
i
n
x
,
u
,
y
,
q
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
w
⊤
y
-
φ
x
T
≤
0
y
,
q
∈
Γ
x
T
.There are three issues that need to be especially addressed when using this approach. First, it is well-known that, in general, the value functionφ may not be differentiable. Secondly, common constraint qualifications such as MFCQ, the linear independence constraint qualification, or at least their nonsmooth counterparts are too strong to hold at the boundary conditions of (25). Finally, the binary variable q could cause some problems in applying a proper constraint qualification. Hence, we have to expect that a nonsmooth maximum principle via (25) is likely to be degenerated (in certain sense).In order to cope with the above-mentioned obstacles, we follow the ideas of Ye and Zhu [15] where the authors use apartial penalization to reach a proper constraint qualification. This partial penalization is often calledpartial calmness condition, which is frequently used for theoptimal value reformulation of an optimistic bilevel programming problem (i.e., problem (25) in our case). This constraint qualification turns out to be closely related to thecalmness of a nonlinear optimization problem at a certain point (cf. [6] for the definition). Calmness for multifunctions (for perturbations of the lower level solution set) might be considered as well. Therefore, one could introduce a multifunction Δ
:
R
⇉
R
n
x
×
R
m
y
×
{
0,1
} such that we get(26)
Δ
κ
≔
x
T
,
y
,
q
∈
R
n
x
×
R
m
y
×
0,1
∣
y
,
q
∈
Γ
x
T
,
w
⊤
y
-
φ
x
T
≤
κfor any point (
x
,
u
,
y
,
q
)
∈
W and any κ
∈
R. Observe that Δ
(
κ
) is empty for any κ
<
0 while Δ
(
0
)
=
g
r
a
p
h
(
Ψ
) is valid. Results from Henrion and Surowiec [16] suggest that the calmness of Δ at (
0
,
x
∗
(
T
)
,
y
∗
,
q
∗
) for an arbitrary feasible point (
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W of (16) (referred to asvalue function constraint qualification or VFCQ for short) is more restrictive than the partial calmness condition given in Definition 3. In [17], the authors generalize the aforementioned results from [16] to bilevel programs where the upper level is an optimal control problem. Note that Henrion and Surowiec criticize (cf. [16]) the fact that optimality conditions derived from partial calmness (or VFCQ) only contain first order information. However, this is justified enough since any subdifferential of the optimal value function is a tool offirst-order analysis. They recommend representing the lower level problem by means of a generalized equation and consider the calmness of some corresponding perturbation mapping in order to obtain optimality conditions containing second-order information of the lower level as well. Observe that the lower level problem in this paper is purely linear; that is, it makes use of no second-order information and hence it makes little sense to exploit this idea here. That is why we deal with a modification of the original concept of partial calmness, and it will turn out later that our problem of interest (16) possesses this partial calmness property at any of its local optimal solutions. We want to mention here that in [18] the author already made use of partial calmness to derive necessary optimality conditions for general optimal control problems but omitted a detailed discussion on when this condition holds in optimal control (apart from the situation where minimax problems are considered).In order to define the partial calmness condition for (16), we need to consider a partially perturbed version of problem (25) given below for some real number κ:(27)
F
x
T
,
y
,
q
⟶
m
i
n
x
,
u
,
y
,
q
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
w
⊤
y
-
φ
x
T
≤
κ
y
,
q
∈
Γ
x
T
.Note that the feasible set of (27) is empty for any κ
<
0. For the purpose of a space-saving notation we introduce the Banach space X
≔
W
n
x
1,1
×
R
m
y
×
R.Definition 3.
Problem (25) is called partially calm at one of its local minimizers (
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W if there exist scalars ɛ
>
0 and η
>
0 such that for any feasible point (
x
,
u
,
y
,
q
∗
,
κ
)
∈
W
×
R of (27) satisfying the condition (
x
,
y
,
κ
)
∈
U
X
ɛ
(
x
∗
,
y
∗
,
0
) the following inequality holds:(28)
F
x
T
,
y
,
q
∗
-
F
x
∗
T
,
y
∗
,
q
∗
+
η
κ
≥
0
.Adapting a result from [9] it becomes clear that partial calmness can be characterized equivalently via partial penalization provided the optimal value function φ is locally Lipschitz continuous in a certain neighborhood of the reference point.Proposition 4.
Let(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W be a local minimizer of (25) such that φ is locally Lipschitz continuous at x
∗
(
T
). Then (25) is partially calm at (
x
∗
,
u
∗
,
y
∗
,
q
∗
) if and only if there exists a scalar η
>
0 such that (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a local minimizer of(29)
η
w
⊤
y
-
φ
x
T
+
F
x
T
,
y
,
q
⟶
m
i
n
x
,
u
,
y
,
q
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a
.
e
.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a
.
e
.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
y
,
q
∈
Γ
x
T
.In order to apply the above result, we have to find a criterion which ensures the postulated Lipschitz-property ofφ. Hence, we start a deeper analysis of the lower level problem by decomposing the lower level problem with respect to q. Let us introduce two additional set-valued mappings Γ
r
:
R
n
x
⇉
R
m
y and functions φ
r
:
R
n
x
→
R
¯, r
=
0,1, such that, for all x
(
T
)
∈
R
n
x, we get (30)
Γ
r
x
T
≔
y
∈
R
m
y
∣
A
1
x
T
+
B
1
y
+
C
1
r
≤
D
1
,
A
2
x
T
+
B
2
y
+
C
2
r
=
D
2
,
φ
r
x
T
≔
+
∞
if
Γ
r
x
T
=
∅
;
i
n
f
y
w
⊤
y
∣
y
∈
Γ
r
x
T
if
Γ
r
x
T
≠
∅
.The following lemma summarizes our results on the continuity ofΓ
0, Γ
1, and Γ.Lemma 5.
For anyx
(
T
)
∈
R
n
x, the following statements hold true: (i)
Γ
(
x
(
T
)
)
=
Γ
0
(
x
(
T
)
)
×
{
0
}
∪
Γ
1
(
x
(
T
)
)
×
{
1
}.
(ii)
The mappingΓ is polyhedral, closed, and locally upper Lipschitz continuous, as well as upper semicontinuous at any x
∗
(
T
)
∈
d
o
m
(
Γ
). Furthermore, it is locally Lipschitz continuous and lower semicontinuous at any x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
Γ
0
)
∩
d
o
m
(
Γ
1
)
).Proof.
(i) This relationship follows directly from the definitions ofΓ, Γ
0, and Γ
1.
(ii) From (i) we deduce(31)
graph
Γ
=
graph
Γ
0
×
0
∪
graph
Γ
1
×
1
.Since g
r
a
p
h
(
Γ
0
) and g
r
a
p
h
(
Γ
1
) are polyhedra by the definition, g
r
a
p
h
(
Γ
) is a polyhedral set; that is, Γ is a polyhedral mapping. Hence, it is locally upper Lipschitz continuous at any point x
∗
(
T
)
∈
d
o
m
(
Γ
) (cf. [19]). It follows from the definition of upper Lipschitz continuity that any mapping boasting this property is upper semicontinuous. The closedness of Γ follows from its being polyhedral. Now fix x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
Γ
0
)
∩
d
o
m
(
Γ
1
)
). Hence, Γ
0 and Γ
1 are locally Lipschitz continuous at x
∗
(
T
); that is, we can find scalars L
r
,
ε
r
>
0 such that for all x
(
T
)
,
x
′
(
T
)
∈
U
R
n
x
ε
r
(
x
∗
(
T
)
) one yields(32)
Γ
r
x
T
⊆
Γ
r
x
′
T
+
L
r
x
T
-
x
′
T
B
R
m
y
,for r
=
0,1. Now we apply Lemma 1 twice. First, we note that for all x
(
T
)
,
x
′
(
T
)
∈
U
R
n
x
ε
r
(
x
∗
(
T
)
)
(33)
Γ
r
x
T
×
r
⊆
Γ
r
x
′
T
×
r
+
L
r
x
T
-
x
′
T
B
R
m
y
×
0
,for r
=
0,1. Next, by defining ɛ
≔
m
i
n
{
ε
0
;
ε
1
} and L
≔
m
a
x
{
L
0
;
L
1
} we derive for all x
(
T
)
,
x
′
(
T
)
∈
U
R
n
x
ɛ
(
x
∗
(
T
)
) the following inclusion:(34)
Γ
x
T
⊆
Γ
x
′
T
+
L
x
T
-
x
′
T
B
R
m
y
+
1
,from statement (i) and Lemma 1. The above formula implies the local Lipschitz continuity of Γ at x
∗
(
T
). Finally, it follows from the definition of local Lipschitz continuity that Γ is lower semicontinuous at x
∗
(
T
) as well. Thus, the proof is complete.Lemma 6.
(i) Forr
=
0,1, the function φ
r is convex, piecewise affine, and locally Lipschitz continuous on its domain.
(ii) The optimal value function can be represented by the formulaφ
(
x
(
T
)
)
=
m
i
n
{
φ
0
(
x
(
T
)
)
;
φ
1
(
x
(
T
)
)
} for any point x
(
T
)
∈
R
n
x.
(iii) The functionφ is piecewise affine and lower semicontinuous on d
o
m
(
φ
). If x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
) holds true, that φ is locally Lipschitz continuous at x
∗
(
T
).
(iv) Forr
=
0,1, the function φ
r is subdifferentiable in the classical sense (i.e., its subdifferential is nonempty) at any point x
∗
(
T
)
∈
d
o
m
(
φ
r
), and the following formula holds:(35)
∂
φ
r
x
∗
T
=
A
1
⊤
λ
+
A
2
⊤
ν
∈
R
n
x
∣
∃
y
∗
∈
Γ
r
x
∗
T
:
w
+
B
1
⊤
λ
+
B
2
⊤
ν
=
0
m
y
,
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0
.
(v) Forr
=
0,1, the following criterion can be used to check whether x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
r
)
). Suppose that x
∗
(
T
)
∈
d
o
m
(
φ
r
) and y
∗
∈
Γ
r
(
x
∗
(
T
)
) satisfy φ
r
(
x
∗
(
T
)
)
=
w
⊤
y
∗. If the set(36)
A
1
⊤
λ
+
A
2
⊤
ν
∈
R
n
x
∣
B
1
⊤
λ
+
B
2
⊤
ν
=
0
m
y
,
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0only contains 0
n, then x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
r
)
) holds true.
(vi) The functionφ is Clarke subdifferentiable everywhere on its domain (i.e., its Clarke subdifferential is nonempty at the point x
∗
(
T
)
∈
d
o
m
(
φ
)). Introducing the set of active indices of the optimal value function I
(
x
∗
(
T
)
)
≔
{
r
∈
{
0,1
}
∣
φ
(
x
∗
(
T
)
)
=
φ
r
(
x
∗
(
T
)
)
}, the following formulas are correct: (a)
IfI
(
x
∗
(
T
)
)
=
{
r
}, then(37)
∂
c
φ
x
∗
T
=
∂
φ
r
x
∗
T
.
(b)
IfI
(
x
∗
(
T
)
)
=
{
r
,
1
-
r
}, then(38)
∂
c
φ
x
∗
T
⊆
c
o
n
v
∂
φ
r
x
∗
T
∪
∂
φ
1
-
r
x
∗
T
.Proof.
(i) This statement is well-known from linear parametric optimization (cf. [20]).
(ii) We deduce this representation directly from statement (i) of Lemma5:(39)
φ
x
T
=
inf
y
,
q
⁡
w
⊤
y
∣
y
,
q
∈
Γ
x
T
=
i
n
f
y
,
q
w
⊤
y
∣
y
,
q
∈
Γ
0
x
T
×
0
∪
Γ
1
x
T
×
1
=
min
⁡
inf
y
,
q
⁡
w
⊤
y
∣
y
,
q
∈
Γ
0
x
T
×
0
;
inf
y
,
q
⁡
w
⊤
y
∣
y
,
q
∈
Γ
1
x
T
×
1
=
min
⁡
inf
y
⁡
w
⊤
y
∣
y
∈
Γ
0
x
T
;
inf
y
⁡
w
⊤
y
∣
y
∈
Γ
1
x
T
=
min
⁡
φ
0
x
T
;
φ
1
x
T
.
(iii) We already know from statement (i) thatφ
0 and φ
1 are piecewise affine and lower semicontinuous functions, being also locally Lipschitz continuous on the interior of their domains. Due to the fact that φ is the pointwise minimum of these two functions (cf. statement (ii) of this lemma), it is piecewise affine as well.
Now, from assertion (ii) of Lemma5 we know that Γ is upper semicontinuous, which yields that φ is a lower semicontinuous function (cf. [20]). On the other hand, at any point x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
) the functions φ
0 and φ
1 are locally Lipschitz continuous, so the same holds true for φ.
(iv) One may apply the results from [21] for fully convex parametric optimization problems to the given linear optimization problems using the duality of linear programming. Note that the classical subdifferentialis not bounded at the boundary points of the domain of the optimal value function.
(v) For any fixedr
∈
{
0,1
}, the parametric optimization problem(40)
min
y
⁡
w
⊤
y
∣
y
∈
Γ
r
x
∗
Tis completely linear and hence its solution set mapping is inner semicontinuous, while the singular subdifferential of its objective function reduces to {
0
n
+
m
} (cf. [22]). Note that y
∗ is a solution of (40). We apply Theorem 7 [5] to derive(41)
∂
∞
φ
r
x
∗
T
⊆
D
∗
Γ
r
x
∗
T
,
y
∗
0
m
.In order to evaluate the above coderivative, we have to compute the basic normal cone(42)
N
graph
Γ
r
B
x
∗
T
,
y
∗
.
Observe thatg
r
a
p
h
(
Γ
r
) is a polyhedron; that is, it is closed and convex. Hence, this cone coincides with the corresponding (classical) normal cone defined as(43)
N
graph
Γ
r
x
∗
T
,
y
∗
=
A
1
⊤
λ
+
A
2
⊤
ν
B
1
⊤
λ
+
B
2
⊤
ν
∈
R
n
x
+
m
y
∣
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0
,since at least Abadie Constraint Qualification holds at any feasible point of a purely linear optimization problem. It follows from (41) and the definition of the normal coderivative D
∗
Γ
r
(
x
∗
(
T
)
,
y
) that the inclusion(44)
∂
∞
φ
r
x
∗
T
⊆
A
1
⊤
λ
+
A
2
⊤
ν
∈
R
n
x
∣
B
1
⊤
λ
+
B
2
⊤
ν
=
0
m
y
,
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0is true; that is, the criterion from statement (v) implies ∂
∞
φ
r
(
x
∗
(
T
)
)
=
{
0
n
}. Consequently, φ
r is Lipschitz continuous in a neighborhood of x
∗
(
T
), which is only possible if x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
r
)
).
(vi) These formulas follow from the calculation rules of the Clarke subdifferential stated in [6].Note that the criterion from statement (v) of the above lemma always holds if, for a fixedx
∗
(
T
), the linear problem (40) is solvable, while Γ
(
x
∗
(
T
)
) possesses an interior point. In order to make this clear, recall that, in the latter case, the Slater condition holds true for problem (40) and the set of singular Lagrange multipliers(45)
λ
,
ν
∈
R
0
m
g
,
+
×
R
m
h
∣
B
1
⊤
λ
+
B
2
⊤
ν
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
r
-
D
1
⊤
λ
=
0reduces to {
(
0
m
g
,
0
m
h
)
}. In general, one may use statement (
v
) as a criterion to check whether x
∗
(
T
) comes from i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
)
=
i
n
t
(
d
o
m
(
φ
0
)
)
∩
i
n
t
(
d
o
m
(
φ
1
)
), that is, whether φ is locally Lipschitz continuous in a neighborhood of x
∗
(
T
). This condition will play an important role in our main results, that is, Theorems 7, 8, and 10.In order to present our next result, we need to introduce two surrogate single-level optimal control problems that arise from (25) and its partially perturbed version (27) by fixing the binary variable value q either to 0 or to 1. Hence, for any r
∈
{
0,1
} we define(46)
F
x
T
,
y
,
r
⟶
m
i
n
x
,
u
,
y
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
w
⊤
y
-
φ
r
x
T
≤
0
y
∈
Γ
r
x
T
,
(47)
F
x
T
,
y
,
r
⟶
m
i
n
x
,
u
,
y
x
˙
t
=
ϕ
t
,
x
t
,
u
t
a.e.
t
∈
0
,
T
x
0
=
x
0
u
t
∈
U
t
a.e.
t
∈
0
,
T
G
t
,
x
t
≤
0
n
G
∀
t
∈
0
,
T
w
⊤
y
-
φ
r
x
T
≤
κ
y
∈
Γ
r
x
T
.The following theorem reveals that (16) isalways partially calm in the sense of Definition 3.Theorem 7.
Let(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W be a feasible point of (16) satisfying x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
). Then (16) is partially calm at this point. In particular, if (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a local minimizer of (16), then there exists an η
>
0 such that (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a local minimizer of (29), too.Proof.
Denote byW
′
≔
W
n
x
1,1
×
L
n
u
1
×
R
m
y. Since (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is a feasible point of (16), (
y
∗
,
q
∗
) is a global optimal solution for the lower level problem with the fixed parameter x
∗
(
T
). Hence, we have φ
(
x
∗
(
T
)
)
=
φ
q
∗
(
x
∗
(
T
)
)
=
w
⊤
y
∗. That is why (
x
∗
,
u
∗
,
y
∗
) is feasible for problem (46) with r
=
q
∗. The function φ
q
∗ appearing therein is the optimal value function of a purely linear parametric optimization problem. Therefore, we may apply the results of Section  3 in [9] in order to find an ε
>
0 and a scalar η
′
>
0 such that, for any feasible point (
x
,
u
,
y
,
κ
)
∈
W
′
×
R of (47) with (
x
,
y
,
κ
)
∈
U
X
ε
(
x
∗
,
y
∗
,
0
) (and r
=
q
∗), we have(48)
F
x
T
,
y
,
q
∗
-
F
x
∗
T
,
y
∗
,
q
∗
+
η
′
κ
≥
0
.Now choose an arbitrary feasible point (
x
,
u
,
y
,
q
∗
,
κ
)
∈
W
×
R of (27) satisfying (
x
,
y
,
κ
)
∈
U
X
ε
(
x
∗
,
y
∗
,
0
). Then (
x
,
u
,
y
,
κ
) is feasible for problem (47) for r
=
q
∗ since from Lemma 6 we have(49)
κ
≥
w
⊤
y
-
φ
x
T
=
w
⊤
y
-
min
⁡
φ
0
x
T
;
φ
1
x
T
≥
w
⊤
y
-
φ
q
∗
x
T
.For any such point (48) holds true; that is, (16) is partially calm at (
x
∗
,
u
∗
,
y
∗
,
q
∗
) in the sense of Definition 3. The second part of the statement follows now easily taking Proposition 4 and Lemma 6 into account.General classes of bilevel programming problems that are partially calm can be found in Ye and Zhu [15], Dempe and Zemkoho [23], and more recently Benita and Mehlitz [17] and Benita et al. [9]. Furthermore, any minimax problem is partially calm at its local optimal solutions. Apart from these classes, there are two well-known conditions ensuring the partial calmness, namely, (i) the property of the lower level problem to have a so-calleduniformly weak sharp minimum (cf. [15]) and (ii) the above-mentioned condition VFCQ. In [9, 17], it is asserted that a BOCP with a finite-dimensional linear lower level problem is always partially calm since its lower level boasts a uniformly weak sharp minimum. Recall that we implicitly used this result when proving Theorem 7.


## 3.4. Optimality Conditions

In this subsection, we present an appropriate formulation of the maximum principle for problem (16). Since, in our notion of local optimality, we consider the binary variable to be fixed, it is possible to proceed as in [9]. We postulate assumptions that allow us to transform (16) into the single-level nonsmooth optimal control problem (29) by means of Theorem 7. Afterwards, we apply a maximum principle (cf. [8, 9]) to (29) and exploit the subdifferential formulas for φ we introduced in Lemma 6. We omit the proof here and refer the interested reader to the recent paper [9].Theorem 8.
Let(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W be a local minimizer of (16), assume that (A
1)-(A
2) hold, and let x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
) be satisfied. (a)
Suppose thatI
(
x
∗
(
T
)
)
=
{
q
∗
} holds (recall Lemma 6 for the definition of this set). Then there exist a function θ
∈
W
n
x
1,1, vectors λ
1
,
λ
2
∈
R
0
m
g
,
+, ν
1
,
ν
2
∈
R
m
h, measures μ
1
,
…
,
μ
n
G
∈
C
⊕, and scalars τ
≥
0, η
>
0 such that the we have (for almost every t
∈
[
0
,
T
]) the following:
(i)
The nontriviality condition is(50)
τ
+
p
L
n
u
∞
+
∑
l
=
1
n
G
μ
l
0
,
T
>
0
.
(ii)
The adjoint equation is(51)
-
θ
˙
t
⊤
=
p
t
⊤
∇
x
ϕ
t
,
x
∗
t
,
u
∗
t
.
(iii)
The Weierstrass-Pontryagin condition is(52)
p
t
⊤
ϕ
t
,
x
∗
t
,
u
∗
t
=
max
v
∈
U
t
⁡
p
t
⊤
ϕ
t
,
x
∗
t
,
v
.
(iv)
The transversality condition is(53)
-
p
T
=
τ
·
∇
x
F
x
∗
T
,
y
∗
,
q
∗
⊤
+
A
1
⊤
λ
1
-
τ
η
·
λ
2
+
A
2
⊤
ν
1
-
τ
η
·
ν
2
.
(v)
The support condition is(54)
supp
⁡
μ
l
⊆
t
∈
0
,
T
∣
G
l
t
,
x
∗
t
=
0
,
l
∈
1
,
…
,
n
G
.
(vi)
The lower level optimality condition is(55)
w
+
B
1
⊤
λ
2
+
B
2
⊤
ν
2
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
q
∗
-
D
1
⊤
λ
2
=
0
.
(vii)
The complementarity condition is(56)
A
1
x
∗
T
+
B
1
y
∗
+
C
1
q
∗
-
D
1
⊤
λ
1
=
0
.
(viii)
The multiplier condition is(57)
τ
·
∇
y
F
x
∗
T
,
y
∗
,
q
∗
⊤
+
η
·
w
+
B
1
⊤
λ
1
+
B
2
⊤
ν
1
=
0
m
y
.
Here, the functionp is defined as follows for almost every t
∈
[
0
,
T
]:(58)
p
t
≔
θ
t
+
∫
0
,
t
∑
l
=
1
n
G
∇
x
G
l
ξ
,
x
∗
ξ
⊤
μ
l
d
ξ
,
i
f
t
<
T
;
θ
T
+
∫
0
,
T
∑
l
=
1
n
G
∇
x
G
l
ξ
,
x
∗
ξ
⊤
μ
l
d
ξ
,
i
f
t
=
T
.
(b)
Suppose thatI
(
x
∗
(
T
)
)
=
{
q
∗
,
1
-
q
∗
} holds. Then we find a function θ
∈
W
n
x
1,1, vectors λ
1
,
λ
2
,
λ
3
∈
R
0
m
g
,
+, ν
1
,
ν
2
,
ν
3
∈
R
m
h, y
¯
∈
R
m
y, measures μ
1
,
…
,
μ
n
G
∈
C
⊕, constants τ
≥
0, η
>
0, and α
∈
[
0,1
] such that conditions (i), (ii), (iii), (v), (vii), and (viii) hold true, together with relationships (ix) and (x) listed below:
(ix)
The modified transversality condition(59)
-
p
T
=
τ
·
∇
x
F
x
∗
T
,
y
∗
,
q
∗
⊤
+
A
1
⊤
λ
1
-
τ
η
·
α
λ
2
+
1
-
α
λ
3
+
A
2
⊤
ν
1
-
τ
η
·
α
ν
2
+
1
-
α
ν
3
.
(x)
The modified lower level optimality condition(60)
w
+
B
1
⊤
λ
2
+
B
2
⊤
ν
2
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
q
∗
-
D
1
⊤
λ
2
=
0
,
w
+
B
1
⊤
λ
3
+
B
2
⊤
ν
3
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
¯
+
C
1
1
-
q
∗
-
D
2
⊤
λ
3
=
0
,
A
1
x
∗
T
+
B
1
y
¯
+
C
1
1
-
q
∗
≤
D
1
,
A
2
x
∗
T
+
B
2
y
¯
+
C
2
1
-
q
∗
=
D
2
.
Here, the functionp is defined as given in (58).Now we illustrate the above theory by means of an example. Observe that it is an adaptation of the BOCP that the second and third authors already discussed in [9]. Here we modify the upper level objective function and the lower level problem in order to fit the settings of this paper.Example 9.
Consider the bilevel optimal control problem(61)
x
2
3
+
1
2
y
1
-
2
2
+
1
2
y
2
+
1
2
⟶
min
⁡
x
,
u
,
y
,
q
⟶
subject  to
x
˙
1
t
=
u
t
a.e.
t
∈
0,3
,
⟶
subject  to
x
˙
2
t
=
x
1
t
a.e.
t
∈
0,3
,
⟶
subject  to
x
1
0
=
1
,
⟶
subject  to
x
2
0
=
0
,
⟶
subject  to
u
t
∈
-
1,1
a.e.
t
∈
0,3
,
⟶
subject  to
-
x
1
t
≤
0
∀
t
∈
0,3
,
⟶
subject  to
y
,
q
∈
Ψ
x
3
,where(62)
Ψ
x
3
≔
Argmin
y
,
q
⁡
-
y
1
-
2
y
2
∣
-
x
1
3
+
y
1
+
y
2
≤
1
,
y
1
+
3
q
≤
3
,
y
2
-
q
≤
0
,
-
y
1
≤
0
,
-
y
2
≤
0
,
q
∈
0,1
.
A similar argumentation as presented in [9] reveals that its global minimizer (
x
∗
,
u
∗
,
y
∗
,
q
∗
) is given as stated below (for almost every t
∈
[
0,3
]):(63)
x
1
∗
t
=
1
-
t
,
if
t
∈
0,1
;
0
,
if
t
∈
1,2
;
t
-
2
,
if
t
∈
2,3
,
x
2
∗
t
=
1
2
-
1
2
t
-
1
2
,
if
t
∈
0,1
;
1
2
,
if
t
∈
1,2
;
1
2
+
1
2
t
-
2
2
,
if
t
∈
2,3
,
u
∗
t
=
-
1
,
if
t
∈
0,1
;
0
,
if
t
∈
1,2
;
1
,
if
t
∈
2,3
,
y
1
∗
=
2
,
y
2
∗
=
0
,
q
∗
=
0
.It is easy to see that the assumptions of Theorem8 hold for problem (61). Now we demonstrate that the corresponding necessary optimality conditions are satisfied.Observe that the optimal value functionsφ
0
,
φ
1
:
R
2
→
R
¯ of the lower level problem (62) take the following values for an arbitrary (terminal) point x
(
3
)
∈
R
2:(64)
φ
0
x
3
=
+
∞
,
if
x
1
3
∈
-
∞
,
-
1
;
-
x
1
3
-
1
,
if
x
1
3
∈
-
1,2
;
-
3
,
if
x
1
3
∈
2
,
+
∞
,
φ
1
x
3
=
+
∞
,
if
x
1
3
∈
-
∞
,
-
1
;
-
2
x
1
3
-
2
,
if
x
1
3
∈
-
1,0
;
-
2
,
if
x
1
3
∈
0
,
+
∞
.Thenx
∗
(
3
) is an interior point of d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
), and I
(
x
∗
(
3
)
)
=
{
0,1
} holds true. Due to Theorem 8, there exist a function θ
∈
W
2
1,1, vectors λ
1
,
λ
2
,
λ
3
∈
R
0
5
,
+, y
¯
∈
R
2, a measure μ
∈
C
⊕, constants τ
≥
0, η
>
0, and α
∈
[
0,1
] which satisfy the following set of conditions (for almost every t
∈
[
0,3
]):(i)
The nontriviality condition is(65)
τ
+
p
L
2
∞
+
μ
0,3
>
0
.
(ii)
The adjoint equation is(66)
-
θ
˙
1
t
=
p
2
t
,
-
θ
˙
2
t
=
0
.
(iii)
The Weierstrass-Pontryagin Condition is(67)
p
1
t
·
u
∗
t
+
p
2
t
·
x
1
∗
t
=
max
v
∈
-
1,1
⁡
p
1
t
·
v
+
p
2
t
·
x
1
∗
t
.
(v)
The support condition is(68)
supp
⁡
μ
⊆
1,2
.
(vii)
The complementarity condition is(69)
λ
1,2
=
0
,
λ
1,4
=
0
.
(viii)
The multiplier condition is(70)
-
τ
η
+
λ
1,1
+
λ
1,2
-
λ
1,4
=
0
,
τ
-
2
τ
η
+
λ
1,1
+
λ
1,3
-
λ
1,5
=
0
.
(x)
The modified transversality condition is(71)
-
p
1
3
=
-
λ
1,1
-
τ
η
α
λ
2,1
+
1
-
α
λ
3,1
,
-
p
2
3
=
τ
.
(xi)
The modified lower level optimality condition is(72)
-
1
+
λ
2,1
+
λ
2,2
-
λ
2,4
=
0
,
λ
2,2
=
0
,
λ
2,4
=
0
,
-
2
+
λ
2,1
+
λ
2,3
-
λ
2,5
=
0
,
-
1
+
λ
3,1
+
λ
3,2
-
λ
3,4
=
0
,
λ
3,1
=
0
,
λ
3,5
=
0
,
-
2
+
λ
3,1
+
λ
3,3
-
λ
3,5
=
0
,
y
¯
1
=
0
,
y
¯
2
=
1
.Here, the function p
∈
L
2
∞ is defined as follows for almost every t
∈
[
0,3
]:(73)
p
1
t
=
θ
1
t
-
∫
0
,
t
μ
d
ξ
,
if
t
<
3
;
θ
1
3
-
∫
0,3
μ
d
ξ
,
if
t
=
3
,
p
2
t
=
θ
2
t
.Note that we already computed the lower level solution y
¯ for the fixed x
∗
(
3
) and 1
-
q
∗ in (xi) to make the latter condition more convenient. As a consequence, (xi) yields λ
2,1
=
1, λ
2,3
=
λ
2,5
+
1, λ
3,3
=
2, and λ
3,2
=
λ
3,4
+
1. Taking (vi) and (vii) together we obtain λ
1,1
=
τ
η and λ
1,3
=
λ
1,5
+
τ
(
η
-
1
). Substituting these representations into (x) leads to p
1
(
3
)
=
τ
η
(
1
-
α
) and p
2
(
3
)
=
-
τ.Taking into account (ii) and the definition ofp, we derive θ
2
≡
-
τ, p
2
≡
-
τ, and θ
1
(
t
)
=
τ
·
t
+
c for some constant c
∈
R and almost every t
∈
[
0,3
]. We evaluate (iii) to obtain(74)
t
∈
0,1
⟹
p
1
t
≤
0
,
t
∈
1,2
⟹
p
1
t
=
0
,
t
∈
2,3
⟹
p
1
t
≥
0
.In order to satisfy the latter condition, as well as the definition of p, we choose c
≔
-
τ and μ
≔
τ
·
(
l
∘
I
[
1,2
]
), where l denotes the Lebesgue measure and I
[
1,2
] represents the intersection mapping with the interval [
1,2
]; that is, I
[
1,2
]
(
M
)
=
M
∩
[
1,2
] for all M
⊆
R. This leads to the following representation of θ
1 and p
1 for almost every t
∈
[
0,3
]:(75)
θ
1
t
=
τ
·
t
-
τ
,
p
1
t
=
τ
·
t
-
τ
,
if
t
∈
0,1
;
0
,
if
t
∈
1,2
;
τ
·
t
-
2
τ
,
if
t
∈
2,3
.In order to satisfy the terminal condition p
1
(
3
)
=
τ
η
(
1
-
α
) we derived earlier, we finally fix α
≔
1
-
1
/
η for an arbitrary η
≥
1 to guarantee α
∈
[
0,1
].Resuming the above calculations while taking into account (i), the following multipliers satisfy the necessary optimality conditions postulated in Theorem8 (definitions hold for almost every t
∈
[
0,3
] when necessary) for any choice of η
≥
1:(76)
θ
1
t
=
τ
·
t
-
τ
,
θ
2
t
=
-
τ
,
λ
1
=
τ
η
0
τ
η
-
1
0
0
,
λ
2
=
1
0
1
0
0
,
λ
3
=
0
1
2
0
0
,
y
¯
=
0
1
,
μ
=
τ
·
l
∘
I
1,2
,
τ
>
0
,
α
=
1
-
1
η
.This result underlines that the partial calmness property (that we used to derive these optimality conditions) theoretically is closely related to partial penalization. One may interpret η as penalization parameter and observe that the necessary optimality conditions above hold for any η which is greater than or equal to some lower bound (which is 1 in this example).


## 4. Optimality Conditions of the Natural Gas Cash-Out Problem

In this section, we provide the optimality conditions for local minimizers of problem (2a)–(2g). We only present a result for the case I
(
x
∗
(
T
)
)
=
{
q
∗
} using statement (a) of Theorem 8. The case I
(
x
∗
(
T
)
)
=
{
q
∗
,
1
-
q
∗
} can be handled similarly applying assertion (b) of the latter theorem. Recall that we already introduced the necessary notation for the matrix representation of the linear lower level problem (corresponding to the natural gas cash-out problem) in Section 2.1. Now these matrices play the role of the general matrices we considered in Section 3. For the brevity purpose, we introduce functions g
1
L
,
…
,
g
n
L
,
g
L
,
g
1
U
,
…
,
g
n
U
,
g
U
:
[
0
,
T
]
×
R
n
→
R by means of(77)
g
i
L
t
,
x
≔
x
i
L
t
-
x
⊤
e
i
n
,
i
∈
N
;
g
L
t
,
x
≔
x
L
t
-
x
⊤
s
n
;
g
i
U
t
,
x
≔
x
⊤
e
i
n
-
x
i
U
t
,
i
∈
N
;
g
U
t
,
x
≔
x
⊤
s
n
-
x
U
t
,for any t
∈
[
0
,
T
] and x
∈
R
n.Theorem 10.
Let(
x
∗
,
u
∗
,
y
∗
,
q
∗
)
∈
W
n
1,1
×
L
n
1
×
R
n
2
+
2
n
+
2
×
{
0,1
} be a local minimizer of the natural gas cash-out problem (2a)–(2g) such that assumption (A
2)-(ii) is satisfied (note that (A
2)-(i) holds trivially) while x
∗
(
T
)
∈
i
n
t
(
d
o
m
(
φ
0
)
∩
d
o
m
(
φ
1
)
) and I
(
x
∗
(
T
)
)
=
{
q
∗
}. Then there exist a function θ
∈
W
n
1,1, vectors λ
1
,
λ
2
∈
R
0
3
n
2
+
5
n
+
2
,
+, ν
1
,
ν
2
∈
R
n
+
1, measures μ
1
L
,
…
,
μ
n
L
,
μ
L
,
μ
1
U
,
…
,
μ
n
U
,
μ
U
∈
C
⊕, and scalars τ
≥
0, η
>
0 such that one has (for almost every t
∈
[
0
,
T
]) the following: (i)
The nontriviality condition is(78)
τ
+
p
L
n
∞
+
∑
i
=
1
n
μ
i
L
0
,
T
+
μ
L
0
,
T
+
∑
i
=
1
n
μ
i
U
0
,
T
+
μ
U
0
,
T
>
0
.
(ii)
The adjoint equation is(79)
θ
˙
t
=
0
n
.
(iii)
The Weierstrass-Pontryagin Condition is(80)
u
i
∗
t
=
u
i
L
t
⟹
p
i
t
≤
0
,
i
∈
N
;
u
i
∗
t
=
u
i
U
t
⟹
p
i
t
≥
0
,
i
∈
N
;
u
i
L
t
<
u
i
∗
t
<
u
i
U
t
⟹
p
i
t
=
0
,
i
∈
N
.
(iv)
The transversality condition is(81)
-
p
T
=
A
1
⊤
λ
1
-
τ
η
·
λ
2
+
A
2
⊤
ν
1
-
τ
η
·
ν
2
.
(v)
The support condition is(82)
supp
⁡
μ
i
L
⊆
t
∈
0
,
T
∣
g
i
L
t
,
x
∗
t
=
0
,
i
∈
N
;
supp
⁡
μ
L
⊆
t
∈
0
,
T
∣
g
L
t
,
x
∗
t
=
0
;
supp
⁡
μ
i
U
⊆
t
∈
0
,
T
∣
g
i
U
t
,
x
∗
t
=
0
,
i
∈
N
;
supp
⁡
μ
U
⊆
t
∈
0
,
T
∣
g
U
t
,
x
∗
t
=
0
.
(vi)
The lower level optimality condition is(83)
w
+
B
1
⊤
λ
2
+
B
2
⊤
ν
2
=
0
m
y
,
A
1
x
∗
T
+
B
1
y
∗
+
C
1
q
∗
-
D
1
⊤
λ
2
=
0
.
(vii)
The complementarity condition is(84)
A
1
x
∗
T
+
B
1
y
∗
+
C
1
q
∗
-
D
1
⊤
λ
1
=
0
.
(viii)
The multiplier condition is(85)
τ
·
e
1
n
2
+
2
n
+
2
+
η
·
w
+
B
1
⊤
λ
1
+
B
2
⊤
ν
1
=
0
n
2
+
2
n
+
2
.Here, the function p is defined as follows for almost every t
∈
[
0
,
T
]:(86)
p
t
≔
θ
t
+
∑
i
=
1
n
μ
i
U
0
,
t
-
μ
i
L
0
,
t
·
e
i
n
+
μ
U
0
,
t
-
μ
L
0
,
t
·
s
n
,
i
f
t
<
T
;
θ
T
+
∑
i
=
1
n
μ
i
U
0
,
T
-
μ
i
L
0
,
T
·
e
i
n
+
μ
U
0
,
T
-
μ
L
0
,
T
·
s
n
,
i
f
t
=
T
.


## 5. Concluding Remarks

In this paper, we formulate the well-known natural gas cash-out model as abilevel optimal control problem. The new formulation yields an interesting theoretical problem with three difficulties. First, its single-level reformulation implies that one has to guarantee that a local optimal solution of the single-level problem corresponds to a local optimal solution of the bilevel problem. Second, one has to find an approach to compute a general derivative of the lower level value function, and, third, the pure state constraints at the upper level and the binary variable at the lower level imply that common regularity conditions do not hold. An important contribution is that we develop a general maximum principle, which is likely to be nondegenerated in order to find the optimality conditions to the cash-out problem.The natural targets for the future research include (i) deriving a theory where the binary variable need not be fixed, that is, where we do not have to evaluate the necessary optimality conditions twice, and (ii) implementing proper discretization techniques with the intention to find numerical solutions to the natural gas cash-out problem.Another task of our future research is to apply to our case (of the BOCP with the lower level represented by a conventional problem of parametric programming) the advanced techniques proposed in [13, 14]. The latter can be employed in order to find constructive (explicit) conditions to guarantee the required local Lipschitz continuity of the (lower level) objective function’s optimal value, that is, of the functions φ and φ
r, r
=
1,2, by means of vanishing their singular subdifferentials. Moreover, necessary optimality conditions for our bilevel optimal control program will be developed through the basic subdifferential of the optimal value functions, similar to that made in the above-mentioned works by Dempe, Morduchovich, Dutta, and their coauthors.



---

*Source: 286083-2015-10-28.xml*