![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
This paper is concerned with the value function approach to multiobjective bilevel optimization which exploits a lower-level frontier-type mapping in order to replace the hierarchical model of two interdependent multiobjective optimization problems by a single-level multiobjective optimization problem. As a starting point, different value-function-type reformulations are suggested and their relations are discussed. Here, we focus on the situations where the lower-level problem is solved up to efficiency or weak efficiency, and an intermediate solution concept is suggested as well. We study the graph-closedness of the associated efficiency-type and frontier-type mappings. These findings are then used for two purposes. First, we investigate existence results in multiobjective bilevel optimization. Second, for the derivation of necessary optimality conditions via the value function approach, it is inherent to differentiate frontier-type mappings in a generalized way. Here, we are concerned with the computation of upper coderivative estimates for the frontier-type mapping associated with the setting where the lower-level problem is solved up to weak efficiency. We proceed in two ways, relying, on the one hand, on a weak domination property and, on the other hand, on a scalarization approach. Illustrative examples visualize our findings and some flaws in the related literature.
1. Introduction
In this note, we are concerned with multiobjective bilevel optimization problems of type
(BPP)
(BPP) where
is a continuous vector-valued function,
is a nonempty, closed, convex, pointed cone with nonempty interior,
is a nonempty, closed set, and
is a suitable solution mapping associated with the parametric multiobjective optimization problem
(P(x))
(P(x)) Above,
is a continuous vector-valued function,
is a nonempty, closed, convex, pointed cone with nonempty interior, and
is a set-valued mapping with a closed graph. In our model problem,
and
play the role of ordering cones, i.e. they specify what ‘minimization’ means in (EquationBPP
(BPP)
(BPP) ) and (EquationP(x)
(P(x))
(P(x)) ), up to different notions of optimality/efficiency in multiobjective optimization. Indeed, even for a fixed ordering cone, there exist diverse concepts of efficiency which aim to characterize the valuable points in the feasible set when faced with multiple objective functions. In this paper, we focus our attention on so-called efficiency and weak efficiency. Exemplary, we refer the interested reader to the monographs [Citation1,Citation2] for a detailed introduction to multiobjective optimization and to Section 2.2 where we summarize some essential foundations of this topic.
In the case where and
, (EquationBPP
(BPP)
(BPP) ) reduces to a so-called standard bilevel optimization problem which is used to model situations of interdependent decision making between two parties that cooperate with each other. Let us note that this model is closely related to the so-called optimistic approach to bilevel optimization as shown in [Citation3, Proposition 6.9]. In the literature, (EquationBPP
(BPP)
(BPP) ) and (EquationP(x)
(P(x))
(P(x)) ) are referred to as the upper- and lower-level problem, respectively, and we will stick to this terminology even in the more general situation considered here. Due to numerous underlying applications from, e.g. finance, economics, data as well as natural sciences, and energy management, bilevel optimization can be found among the most active fields of research within the optimization community, see the survey papers [Citation4,Citation5].
For an introduction to bilevel optimization, we refer the interested reader to the monographs [Citation6–9]. We emphasize that bilevel optimization problems are, in general, highly irregular and nonconvex optimization problems which are only implicitly given as a closed-form representation of the solution mapping associated with (EquationP(x)
(P(x))
(P(x)) ) is often not available. This causes the model (EquationBPP
(BPP)
(BPP) ) to be rather challenging from a theoretical as well as numerical perspective.
Since the set of efficient or weakly efficient points of a multiobjective optimization problem is, usually, not a singleton, the minimization of a scalar function over the set of efficient or weakly efficient points, in order to reduce the number of reasonable and economically utilizable points, is a closely related topic, see e.g. [Citation10–13], and such problems already possess a hierarchical structure. So-called semivectorial bilevel optimization problems, where only and
are demanded in (EquationBPP
(BPP)
(BPP) ), i.e. only the underlying parametric optimization problem (EquationP(x)
(P(x))
(P(x)) ) possesses multiple objective functions, provide a much more general model paradigm and have been investigated, e.g. in [Citation14–19]. The even more general situation where the objective functions of both decision makers in (EquationBPP
(BPP)
(BPP) ) are allowed to be vector-valued has been considered, e.g. in [Citation20–25]. For formal completeness, let us also mention that the setting where
and
hold while the objective function of (EquationBPP
(BPP)
(BPP) ) is vector-valued is also reasonable, see e.g. [Citation26–28]. It is well known from the literature that scalarization techniques can be used to transfer multiobjective optimization problems into scalar ones, see e.g. [Citation2, Section 5]. Hence, whenever the lower-level problem (EquationP(x)
(P(x))
(P(x)) ) possesses multiple objective functions, it seems to be an obvious idea to replace it with a scalarized counterpart and to treat the scalarization parameters as additional upper-level variables. This procedure, however, comes with a price. It has been shown in the setting of semivectorial bilevel optimization that this reformulation induces additional local minimizers which might be attractive for solution algorithms, see [Citation17]. Even worse, the more detailed study [Citation29] revealed that this transformation also induces additional stationary points while the constraint qualifications needed to tackle the reformulated problem might be stronger than the ones applicable to the original model. These observations are likely to concern multiobjective bilevel optimization problems, too. Hence, one should not tackle (EquationP(x)
(P(x))
(P(x)) ) with scalarization approaches for the theoretical and numerical treatment of (EquationBPP
(BPP)
(BPP) ) in a lightheaded way.
From the viewpoint of applications, the investigation of multiobjective bilevel optimization problems is rather relevant. Let us point the reader to three interesting model problems arising in practice. First, for example, in [Citation28], transportation planning systems are considered in which a system manager wants to determine road tolls for a transportation network by deciding on the charges on each edge of the network. Thereby, the leader wants to minimize the total network cost and to maximize the total revenue as well as the consumers' surplus at the same time. For the lower-level problem, the travelers choose their routes in the network by the traffic volume. This circumstance is modeled as an equilibrium traffic assignment problem in which each user chooses the most convenient path selfishly. Second, [Citation30] is concerned with standalone hybrid renewable energy systems which can reliably meet the energy demand of users in remote areas and reduce the intermittency of different renewable energy sources. At the upper-level stage, policy makers like a government give incentive subsidies to investors to fill in the gap between the market price and the price charged to consumers. Thereby, the decision maker is interested to minimize the negative impact of hybrid renewable energy systems on the environment measured by the emitted annualized carbon dioxide and, conflicting to this, the subsidies borne by the government. The investor's objective for the lower-level problem is to reduce the annualized cost of the energy system project which comprise the annualized capital cost, annual fuel cost, annual system maintenance cost, and subsidies. In the constraints, technical components of several energy technologies are considered. Third, in [Citation31], multiobjective optimization problems are used to model waste management with obnoxious effects. The government decides at the upper level about the location and scale of waste recycling centers to minimize the total economic cost and, simultaneously, the abominable effects caused by recycling centers under given capacity constraints. Based on the locations of the recycling centers, a sanitation company determines waste collection routing plans to minimize the vehicle traveling and fixed cost for which, exemplary, flow conservation for delivery, locations of the underlying routing graph, load of the vehicle on its edges, and the recycling center capacities are considered as constraints.
In this note, we are concerned with the so-called value function approach to bilevel optimization, which dates back to [Citation32] in the scalar case. Let us, for a moment, assume that (EquationP(x)(P(x))
(P(x)) ) is a scalar problem, i.e.
and
. With the aid of the so-called lower-level optimal value function
given by
(1)
(1) where
and
, one can equivalently reformulate (EquationBPP
(BPP)
(BPP) ) by means of
(2)
(2) as the feasible sets of (EquationBPP
(BPP)
(BPP) ) and (Equation2
(2)
(2) ) coincide. Noting that φ is only implicitly available while being inherently nonsmooth, and observing that classical constraint qualifications from nonsmooth programming are likely to fail at all feasible points of (Equation2
(2)
(2) ), see [Citation33, Proposition 3.2], (Equation2
(2)
(2) ) is still a rather challenging problem. Nevertheless, the so-called value function reformulation (Equation2
(2)
(2) ) has turned out to be useful for the construction of necessary optimality conditions and solution algorithms for (EquationBPP
(BPP)
(BPP) ) in the setting where, additionally,
and
, see e.g. [Citation33–37] and the references therein.
Based on its successful application in the scalar situation, the paper [Citation24] suggests an extension of the value function approach to multiobjective bilevel optimization. In order to recover the approach of [Citation24], let us introduce the set-valued mapping by means of
and observe that (EquationBPP
(BPP)
(BPP) ) is closely related to
(VFR)
(VFR) which, again, we will refer to as value function reformulation of (EquationBPP
(BPP)
(BPP) ). Let us note at this point that (EquationBPP
(BPP)
(BPP) ) and (EquationVFR
(VFR)
(VFR) ) do not need to be equivalent anymore in general, see Example 3.19. In [Citation24], the authors exploit the model problem (EquationVFR
(VFR)
(VFR) ) for the derivation of necessary optimality conditions for the associated model (EquationBPP
(BPP)
(BPP) ) where the lower-level parametric optimization problem is solved up to efficient points. More precisely, the authors of [Citation24] transfer the classical arguments from [Citation33], which apply to bilevel optimization problems with scalar upper- and lower-level objective functions, to the multiobjective situation. Among others, this makes the (generalized) differentiation of the so-called frontier mapping
from above necessary. Therefore, Mordukhovich's coderivative construction is exploited, see e.g. [Citation38,Citation39]. Let us mention that the computation of coderivatives associated with frontier maps has already been studied in the literature before, see e.g. [Citation40–42].
Now, we would like to mention an important and crucial observation which seemingly has been overlooked in most of the aforementioned literature dealing with multiobjective bilevel optimization. If the lower-level problem (EquationP(x)(P(x))
(P(x)) ) is solved up to efficiency, then the associated solution mapping is likely to possess a graph which is not closed – even under comparatively strict assumptions. This non-closedness also concerns the associated frontier mapping which is used in the definition of the associated value function reformulation. Let us point out two immediate disadvantages which result from this non-closedness. First, it will be difficult to guarantee that (EquationBPP
(BPP)
(BPP) ) possesses efficient or at least weakly efficient points in this case. Second, for the computation of coderivatives, the underlying set-valued mapping needs to possess, at least locally around the reference point, a closed graph, so, in turn, this concept formally cannot be applied to the frontier mapping of interest in general.
In this note, we tackle both of the aforementioned issues and, along the way, comment on related peculiarities of multiobjective bilevel optimization. Throughout the paper, several examples are presented to illustrate our arguments. Furthermore, we compare our results with related findings applying to (Equation2(2)
(2) ) in the scalar case. To start, let us mention that whenever (EquationP(x)
(P(x))
(P(x)) ) is solved up to weak efficiency only, then the associated solution map is likely to possess a closed graph under mild assumptions, and this also extends to the associated frontier mapping. This can be distilled e.g. from [Citation43, Section 3.5], but we provide a self-contained proof here for the purpose of completeness. In Section 3 of the paper, we are not only concerned with some formal properties of the value function reformulation, but also with the derivation of existence results for (EquationBPP
(BPP)
(BPP) ) which is a closely related issue. As already mentioned, this is reasonable under mild assumptions if (EquationP(x)
(P(x))
(P(x)) ) is solved up to weak efficiency. We also show that the efficiency and associated frontier mapping of a fully linear parametric multiobjective optimization problem possess closed graphs, giving rise to yet another criterion for the existence of efficient and weakly efficient points for (EquationBPP
(BPP)
(BPP) ). Furthermore, we suggest an intermediate solution approach between efficiency and weak efficiency applying to (EquationP(x)
(P(x))
(P(x)) ) which naturally comes along with a closed graph of the associated mappings
as well as
and, thus, the superordinate problem (EquationBPP
(BPP)
(BPP) ) is also likely to possess efficient and weakly efficient points. Section 4 is dedicated to the computation of upper coderivative estimates for the weak frontier mapping, i.e. the frontier mapping associated with (EquationP(x)
(P(x))
(P(x)) ) when solved up to weak efficiency. First, we follow the approach promoted in [Citation40], which relies on the so-called domination property, see e.g. [Citation44,Citation45], and point out some associated advantages and disadvantages. Furthermore, we illustrate a crucial error in [Citation24, Theorem 4.1], that is concerned with the computation of an upper estimate for the coderivative of the efficiency-related frontier mapping of (EquationP(x)
(P(x))
(P(x)) ). Unluckily, this shows that the results obtained in [Citation24, Section 4] are not reliable. A second approach to coderivative estimates we discuss here is based on a weighted-sum scalarization of the problem (EquationP(x)
(P(x))
(P(x)) ) in the convex situation. This idea is motivated by considerations from [Citation19].
The remainder of the paper is organized as follows. In Section 2, we comment on the basic notation used in this paper, as well as some preliminaries from set-valued analysis and generalized differentiation. Furthermore, some foundations of multiobjective optimization are presented. Section 3 is dedicated to the detailed study of model problems in multiobjective bilevel optimization with a particular emphasis on value-function-type reformulations and their relations to each other. Based on a discussion of closedness properties of efficiency-type and associated frontier mappings in Section 3.1, some existence results are stated in Section 3.2. Furthermore, an intermediate way between efficiency and weak efficiency on how to interpret (EquationP(x)(P(x))
(P(x)) ) is suggested in Section 3.3. In Section 4, we are concerned with the derivation of upper coderivative estimates for frontier mappings. Based on a classical approach from the literature, we recover some known results in the novel setting of weak efficiency in Section 4.1. Relying on a scalarization approach, some new findings are obtained in Section 4.2. The paper closes with some concluding remarks in Section 5.
2. Preliminaries
In this section, we comment on the notation used in this paper. Particularly, some foundations of set-valued and variational analysis are provided. Furthermore, we present some necessary basics of multiobjective optimization.
2.1. Basic notation
The notation in this paper is fairly standard and mainly follows [Citation38,Citation39].
Let and
represent the nonnegative and nonpositive real numbers, respectively. Throughout the paper, we equip
, where
is a positive integer, with the Euclidean inner product
and the associated Euclidean norm
. We use
to represent the unit sphere around the origin in
where the dimension of the underlying space will be always clear from the context. For some set
,
,
,
, and
denote the closure, the interior, the convex hull, and the convex conic hull of Ω, respectively.
Whenever is a mapping which is differentiable at
, then
denotes the Jacobian of υ at
. Partial derivatives are represented in analogous fashion.
2.1.1. Convexity properties of vector-valued functions
In this paper, we are partially concerned with convexity properties of vector-valued mappings with respect to (w.r.t.) a given so-called ordering cone, see e.g. [Citation2]. For a nonempty, closed, convex, pointed cone , a mapping
is said to be
-convex if
We note that whenever F is
-convex and
is convex, then
is convex, and the function
is convex for each
. Here, we made use of
to denote the dual cone of
which is a closed, convex cone as well. Let us mention that a componentwise convex mapping
is
-convex.
The mapping F is said to be -strictly-quasiconvex if
Exemplary, in the case where
, F is
-strictly-quasiconvex if
are so-called semi-strictly quasiconvex in the sense that
has to hold for all
. The latter is clearly inherent whenever the functions
are strictly convex.
2.1.2. Set-valued mappings
In this paper, we are concerned with so-called set-valued mappings which assign to each element of the pre-image space a (potentially empty) subset of the image space. Such objects will be denoted by . Throughout the paper, we use
to represent the graph and the domain of Υ, respectively. For a set
, we define the set-valued mappings
by means of
for brevity of notation. A set-valued mapping is referred to as polyhedral whenever its graph can be represented as the union of finitely many convex polyhedral sets.
For fixed , we call Υ closed at
whenever for each sequence
and each
such that
and
, we also have
. Note that this property is inherent whenever
is closed. Additionally, whenever Υ is closed at
,
is a closed set. Observe that closedness of
does not necessarily give closedness of
. However, closedness of
and closedness of Υ at each point from
give closedness of
. We refer to Υ as locally bounded at
if there exist a bounded set
and some neighborhood
of
such that
for all
. Furthermore, Υ is called lower semicontinuous at
(in Berge's sense) w.r.t.
whenever for each open set
such that
, there is neighborhood
of
such that
for all
. For some fixed pair
, we say that Υ is inner semicontinuous at
w.r.t.
whenever for each neighborhood
of
, there exists a neighborhood
of
such that
for all
. If
can be chosen, Υ is called inner semicontinuous at
for brevity. Note that Υ is lower semicontinuous at
w.r.t. Ω if and only if it is inner semicontinuous at
w.r.t. Ω for each
. Furthermore, observe that Υ is inner semicontinuous at
w.r.t. Ω if and only if for each sequence
such that
, there exists a sequence
satisfying
and
for all large enough
. Let us also mention that Υ is referred to as inner semicompact at
w.r.t. Ω if for each sequence
with
, there are a subsequence
and a convergent sequence
such that
holds for all
. If
can be chosen, Υ is called inner semicompact at
. Clearly, if Υ is locally bounded at
, then it is inner semicompact at
w.r.t. each subset of
. Furthermore, whenever there exists
such that Υ is inner semicontinuous at
w.r.t. Ω, then Υ is inner semicompact at
w.r.t. Ω. In the definitions of lower and inner semicontinuity as well as inner semicompactness, special emphasis is laid on settings where
.
In the subsequently stated lemma, we characterize the closedness of the graph of set-valued mappings of special type.
Lemma 2.1
For a function , we consider the set-valued mapping
given by
with the conventions
and
. Then
is closed if and only if υ is upper semicontinuous.
Proof.
We observe that equals
, the so-called hypograph of υ, and
is closed if and only if υ is an upper semicontinuous function, see e.g. [Citation39, Theorem 1.6].
For two given set-valued mappings and
, their composition
is defined by
The associated so-called intermediate mapping
is given by
and plays an important role for the analysis of the underlying composition, see e.g. [Citation46, Section 5.3] or [Citation38, Section 3.1.2].
2.1.3. Variational analysis and generalized differentiation
The following definitions are taken from [Citation38,Citation39].
For some set , which is closed locally around some point
, we call
the limiting (or Mordukhovich) normal cone to Ω at
. Above,
denotes the projector of Ω which is given by
We note that
is a closed cone which reduces to the classical normal cone of convex analysis as soon as Ω is a convex set.
For a set-valued mapping and some point
where
is locally closed, the set-valued mapping
given by
is referred to as the (limiting or Mordukhovich) coderivative of Υ at
. In the case of a single-valued continuous mapping
, which can naturally be interpreted as a singleton-valued set-valued mapping, and
, we make use of
for brevity of notation. If the mapping υ is continuously differentiable at
, then
is valid for all
.
2.2. Foundations of multiobjective optimization
For a continuous vector function , a nonempty, closed set
, and some closed, convex, pointed cone
with nonempty interior, we investigate the rather general multiobjective optimization problem
(MOP)
(MOP) Recall that some feasible point
of (EquationMOP
(MOP)
(MOP) ) is called efficient (weakly efficient) whenever
holds. The set of all efficient (weakly efficient) points of (EquationMOP
(MOP)
(MOP) ) will be denoted by
(
). Further,
(
) is referred to as the nondominated (weakly nondominated) set of (EquationMOP
(MOP)
(MOP) ). Let us mention that the computation of efficient (weakly efficient) points makes knowledge of F, S, and
necessary, while, in principle, nondominated (weakly nondominated) points can be characterized from knowledge of
and
only. Clearly, the inclusions
and
hold by definition. Let us also point out that continuity of F and the openness of
give closedness of the sets
and
. In contrast, the sets
and
do not need to be closed, see Example 2.3 below. Let us also note that the closedness of
and
guarantees
and
, and these inclusions can be strict. In the case where
, there is no difference between efficiency and weak efficiency as well as nondominance and weak nondominance, respectively, since the only cones satisfying our requirements would be
and
in this case.
In this paper, we are concerned with so-called domination properties of (EquationMOP(MOP)
(MOP) ), see e.g. [Citation44,Citation45,Citation47].
Definition 2.2
We say that (EquationMOP(MOP)
(MOP) ) possesses the domination property (the weak domination property) if the following inclusion is valid:
It is clear from the definition that validity of the domination property also gives validity of the weak domination property. Observe that, by convexity of , (EquationMOP
(MOP)
(MOP) ) possesses the domination property (the weak domination property) if and only if
Thus, the discussion at the beginning of [Citation24, Section 4] is completely superfluous. Sufficient criteria for the domination and weak domination property can be found in [Citation44,Citation47]. Exemplary, let us mention that (EquationMOP
(MOP)
(MOP) ) possesses the domination property whenever F is continuous while S is compact. This follows by combining [Citation44, Theorem 2] and [Citation2, Theorem 3.38]. Furthermore, we also want to point the reader's attention to the fact that even in the presence of the domination property,
and
might be non-closed.
Example 2.3
Let be the identity, let
be given by
and let
. Then we find
On the one hand, this can be used to see that the associated problem (EquationMOP
(MOP)
(MOP) ) possesses the domination property. On the other hand,
and
are not closed.
It follows from [Citation48, Example 3.4.2] that the efficient set might not be closed even if the set
is compact and convex. However, for instance in [Citation49, Lemma 7.1], it is shown that if
and all functions
are strictly quasiconvex while S is convex, then
coincides with
and so
is closed since
is closed. This result can also be extended to more general ordering cones.
Lemma 2.4
Let F be -strictly-quasiconvex, and let S be convex. Then
and
.
Proof.
We only show equality of the efficient and weakly efficient set. This automatically gives equivalence of the nondominated and weakly nondominated set. Since holds in general, we only need to prove the converse inclusion holds true. Fix
and suppose that
. Then we find some
satisfying
. For all
,
follows by convexity of S, and since F is
-strictly-quasiconvex, we obtain
This is a contradiction to
.
3. Value function models in multiobjective bilevel optimization
In order to make (EquationBPP(BPP)
(BPP) ) explicit, one has to specify the precise meaning behind the optimization goals at the (upper- and) lower-level stage. Therefore, let us define set-valued mappings
and
by means of
for each
. Note that the identities
hold by definition of these mappings. We will refer to Ψ and
as the efficiency and weak efficiency mapping associated with (EquationP(x)
(P(x))
(P(x)) ), respectively. Similarly, Φ and
are called the frontier and weak frontier mapping associated with (EquationP(x)
(P(x))
(P(x)) ). For brevity of notation, we further introduce the set-valued mapping
given by
(3)
(3) In the course of this note, we are mainly concerned with the optimization problems
as well as their associated respective value function reformulations
which are apparently equivalent.
Proposition 3.1
(a) | For each | ||||
(b) | For each |
Proof.
Let us start with the proof of the first assertion. Indeed, if holds for some
, then
and
follow trivially, i.e. the inclusion ⊂ is obvious. For the proof of the converse inclusion
, pick
such that
for some
. By definition of Φ, we find
such that
. Since
, we also have
, and this gives
.
The proof of the second assertion is completely analogous.
Corollary 3.2
(a) | Problems (Equation | ||||
(b) | Problems (Equation |
Let us note that whenever and
hold, then both problems (Equation
-VFR
(5)
(5) ) and (Equation
-VFR
(5)
(5) ) are equivalent to
(4)
(4) which, up to the relation sign in the constraint involving φ, is the same as the classical value function reformulation (Equation2
(2)
(2) ). In scalar bilevel programming, however, it has turned out to be beneficial to work with the constraint
as this opens the door to algorithmic applications and induces a sign condition for the Lagrange multiplier associated with this constraint in the context of nonsmooth optimality conditions. Noting that, for each
and
,
is not possible, we can reformulate (Equation2
(2)
(2) ) and (Equation4
(6a)
(6a) ) as
(5)
(5) with the conventions
and
. Observing that
is the ordering cone associated with the lower-level problem in the scalar situation, this motivates to investigate
(6a)
(6a)
(6b)
(6b) as potential surrogates of (Equation
-VFR
(5)
(5) ) and (Equation
-VFR
(5)
(5) ), respectively. As the following results show, the addition of the lower-level ordering cone in (Equation6a
(7)
(7) ) and (Equation6b
(8)
(8) ) does not change the problem.
Proposition 3.3
(a) | For each | ||||
(b) | For each |
Proof.
Let us start with the proof of the first assertion. Clearly, as , the inclusion ⊂ is clear from Proposition 3.1. Conversely, fix
and
such that
. Then there exist
and
such that
. By definition of efficiency, this gives c = 0, i.e.
, and, hence,
by Proposition 3.1.
In order to prove the second assertion, we observe that the inclusion ⊂ follows again from and Proposition 3.1. Thus, pick an arbitrary
and
such that
. Then there exist
and
such that
. Suppose that
. Then there are
and
such that
, and this gives
. As we have
,
follows which is a contradiction. Hence, we find
which yields
, i.e.
due to Proposition 3.1.
Corollary 3.4
(a) | Problems (Equation | ||||
(b) | Problems (Equation |
In order to guarantee the existence of efficient or weakly efficient points for the above model problems (Equation-BPP
(4)
(4) ), (Equation
-BPP
(4)
(4) ), (Equation
-VFR
(5)
(5) ), and (Equation
-VFR
(5)
(5) ), and to make their algorithmic treatment reasonable, it is important to guarantee that their respective feasible sets are nonempty and closed. Recalling that the mapping f is continuous, and the sets X and
are assumed to be closed, this reduces to the closedness of
,
,
, and
, respectively. This is addressed in Sections 3.1 and 3.2 below. As we will see,
and
are not likely to be closed in several popular settings. In Section 3.3, we suggest an intermediate approach that bridges the model problems (Equation
-BPP
(4)
(4) ) and (Equation
-BPP
(4)
(4) ) (and, similarly, (Equation
-VFR
(5)
(5) ) and (Equation
-VFR)
(5)
(5) ) and comes along with a guaranteed closedness of the feasible set.
3.1. Closedness properties of efficiency and frontier mappings
In the following lemma, we show that as well as
are indeed closed under mild assumptions, see e.g. [Citation43, Corollary 3.5.6] for a related result.
Lemma 3.5
Fix and let Γ be lower semicontinuous at
w.r.t. its domain. Then
is closed at
. If, additionally, Γ is locally bounded at
,
is closed at
.
Proof.
Let and
as well as
be chosen such that
,
, and
for all
. By definition of
, we find
and
(7)
(7) for all
. Since Γ is closed at
, we obtain
. Suppose that
. Then there are
and
such that
. Noting that
, the assumed lower semicontinuity of Γ yields the existence of a sequence
such that
and
for all
. We set
for each
. Continuity of f gives us
, and due to
,
holds for all large enough
. Some rearrangements yield
i.e.
for large enough
, contradicting (Equation7
(9)
(9) ). Hence,
follows, i.e.
is closed at
.
In order to verify the closedness of at
, we pick sequences
and
such that
,
for all
, and
for some
. This gives the existence of
such that
and
for all
. Local boundedness of Γ at
guarantees
along a subsequence (without relabeling) for some
. The first part of the proof ensures
, and continuity of f yields
, i.e.
, showing the closedness of
at
.
As a corollary, we can state conditions which guarantee the closedness of and
.
Corollary 3.6
Let be closed, and let Γ be locally bounded and lower semicontinuous w.r.t. its domain at each point from
. Then
and
are closed.
Proof.
The closedness of and the assumed local boundedness guarantee that, for each
,
is nonempty and compact. Thus, [Citation2, Theorem 6.3] shows
, i.e.
and
are closed. Furthermore, Lemma 3.5 shows that
and
are closed at each point of their domain, respectively. Taking these facts together, the assertion follows.
Let us relate these findings to the classical results from [Citation50] which apply to the scalar situation and
. Then the closedness of
corresponds to the closedness of the classical solution mapping while the closedness of
corresponds to continuity (w.r.t. the domain) of the so-called optimal value function. Consulting [Citation50, Theorems 4.2.1, 4.2.2], these properties are obtained under continuity of the objective function and lower semicontinuity of the constraint mapping Γ. In this regard, Lemma 3.5 amounts to a reasonable generalization to the vector-valued situation.
Remark 3.7
Recall that the efficient set as well as the associated nondominated set in multiobjective optimization do not need to be closed even in situations where all objective functions are continuous and the feasible set is compact. This issue naturally extends to the parametric setting. Typically, the set-valued mappings Ψ and Φ do not possess closed graphs in many situations.
Let us inspect some simple examples.
Example 3.8
We consider (EquationP(x)(P(x))
(P(x)) ) with
,
, and
The efficiency map is given by
which is not closed for each
, whereas the weak efficiency map, given by
is closed at each
.
Example 3.9
We consider (EquationP(x)(P(x))
(P(x)) ) with
,
, and
For
, the efficient and weakly efficient points of (EquationP(x)
(P(x))
(P(x)) ) coincide. In the case x = 0, there are no efficient point of (EquationP(x)
(P(x))
(P(x)) ), but all points from
are weakly efficient. Moreover, for
, there is neither an efficient nor a weakly efficient point. Hence, the efficiency map and frontier map are given by
and these mappings do not possess closed graphs. Furthermore, the weak efficiency map and the weak frontier map are given by
and possess closed graphs, see Corollary 3.6 while noting that Γ is not locally bounded at each point
.
Remark 3.10
Assume that, for each ,
is
-strictly-quasiconvex while
is convex. Then, due to Lemma 2.4, we find
and
for all
, i.e. there is no difference between the models (Equation
-BPP
(4)
(4) ) and (Equation
-BPP
(4)
(4) ), (Equation
-VFR
(5)
(5) ) and (Equation
-VFR
(5)
(5) ), or (Equation6a
(7)
(7) ) and (Equation6b
(8)
(8) ), respectively. Particularly, Lemma 2.4 and Corollary 3.6 can be used to infer closedness results on Ψ and Φ.
In the following lemma, we show that the efficiency and frontier mapping of a fully linear multiobjective parametric optimization problem possess closed graphs.
Lemma 3.11
For matrices ,
,
, and
, let
and
be given by
(8)
(8) Furthermore, let the ordering cone
be fixed. Then the associated mappings Ψ and Φ possess closed graphs.
Proof.
We prove the closedness of by combining a classical scalarization argument and results from scalar linear parametric optimization. Afterwards, the closedness of
is shown via Hofmann's lemma.
Fix a sequence and a pair
such that
. Let
be fixed for the moment. Due to [Citation1, Theorem 4.7],
is an optimal solution of the scalar linear optimization problem
(9)
(9) where
denotes the all-ones vector. The dual of this problem is given by
(10)
(10) As (Equation9
(11)
(11) ) possesses a solution, (Equation10
(12)
(12) ) is solvable as well.
Let us inspect (Equation10(12)
(12) ) which can be interpreted as a linear parametric optimization problem with multiple parameters, namely
and
, which merely appear in the objective function. Based on [Citation51, Sections 7, 8], the set of parameters where this parametric problem possesses a solution is a convex polyhedron and can be partitioned into finitely many so-called regions of stability, being convex polyhedra as well, such that, in the interior of any such region, precisely one of the vertices associated with the convex polyhedron
is optimal, while on the boundary, this vertex is still optimal but may not be the unique maximizer. Anyhow, since there exist only finitely many regions of stability, there is an infinite index set
such that all points from the subsequence
belong to the same region of stability which is associated with some fixed vertex
of Q. As all regions of stability are closed,
does not only solve (Equation10
(12)
(12) ) for each
but also the problem
(11)
(11) Strong duality of linear programming yields
for each
, and taking the limit
gives
. As
is feasible to
which is the dual of (11), it already must be a minimizer. Applying [Citation1, Theorem 4.7] once more gives
. This shows the closedness of
.
In the remainder of the proof, we show that is closed. Thus, let
and
be chosen such that
. By definition of Φ, we find a sequence
such that
and
hold for each
. Applying Hofmann's lemma, see e.g. [Citation52, Lemma 3C.4], for each
to the linear system
yields some which satisfies
and the upper bound
where the constant
does not depend on k. Particularly, for each
,
, i.e.
. Further, by boundedness of
and
,
is bounded as well so we may assume
for some
. The first part of the proof gives
, so that
yields
. Hence,
is closed.
We note that the first part of the above proof has been inspired by classical arguments of Isermann who showed that all efficient points of a linear multiobjective optimization problem can be found with the aid of the weighted-sum scalarization technique where all weights are positive, see [Citation53].
In the context of Proposition 3.3 and Corollary 3.4, the following result should be taken into account.
Lemma 3.12
Let Γ be locally bounded at each point of its domain. Then the following assertions hold.
(a) | The set | ||||
(b) | The set |
Proof.
We only prove the first assertion. The second one can be shown in analogous fashion while incorporating some arguments from the proof of Proposition 3.3.
We show both implications separately.
Let
be closed, and choose
such that
for some
. By definition, we find sequences
and
such that
and
, i.e.
, for each
. As the sequence
is bounded by assumption, it possesses an accumulation point
which, by continuity of f and closedness of
, satisfies
. Furthermore,
possesses the accumulation point
which, by closedness of
, belongs to
. Hence, we have shown
, and closedness of
follows.
Let
be closed, and choose a sequence
such that
for some
. On the one hand, since
, we also have
, and
follows, i.e. there are
and
such that
. On the other hand, there is a sequence
such that
and
for all
. As the sequence
is bounded by assumption, it possesses an accumulation point
which, by closedness of
, belongs to
. Combining these observations, we have
. Now,
guarantees c = 0, i.e.
, and closedness of
follows.
3.2. Existence results in multiobjective bilevel optimization
The following example shows that the closedness of is, indeed, essential for the existence of efficient and weakly efficient points of (EquationBPP
(BPP)
(BPP) ).
Example 3.13
We consider (EquationBPP(BPP)
(BPP) ) with
,
,
, and
Furthermore, we assume that
is the efficiency or weak efficiency map of the parametric optimization problem from Example 3.8, i.e.
In the case
, there is neither an efficient nor a weakly effficient point of (EquationBPP
(BPP)
(BPP) ). However, in the case
,
is a feasible subset of (EquationBPP
(BPP)
(BPP) ), and these are precisely the efficient and, simultaneously, weakly efficient points of the problem.
The following result concerns the existence of efficient and weakly efficient points of (EquationBPP(BPP)
(BPP) ).
Theorem 3.14
Let be closed and
be nonempty and bounded. Then there exist an efficient and a weakly efficient point of (EquationBPP
(BPP)
(BPP) ).
Proof.
Problem (EquationBPP(BPP)
(BPP) ) is equivalent to
(12)
(12) Due to the postulated assumptions, the set
is nonempty, bounded, and closed and, thus, compact. Then
is compact because F is continuous. The existence of an efficient point of (Equation12
(13)
(13) ), which then is efficient and, thus, weakly efficient for (EquationBPP
(BPP)
(BPP) ), follows by [Citation2, Theorem 6.3].
Let us note that the boundedness assumption on in Theorem 3.14 is inherently satisfied whenever X and
are bounded.
Based on Corollary 3.6, we obtain from Theorem 3.14 an existence result for efficient and weakly efficient points of (Equation-BPP
(4)
(4) ).
Corollary 3.15
Let be closed, and let Γ be locally bounded and lower semicontinuous w.r.t. its domain at each point from
. Let
be nonempty and bounded. Then there exist an efficient and a weakly efficient point of (Equation
-BPP
(4)
(4) ).
We note that Corollary 3.15 generalizes [Citation17, Theorem 5.5] to multiobjective bilevel optimization problems, but does not cover the situation were the lower-level variable comes from an infinite-dimensional space.
Similar as in Corollary 3.15, Theorem 3.14 gives an existence result for efficient and weakly efficient points of (Equation-BPP
(4)
(4) ) and (Equation
-BPP
(4)
(4) ) whenever the lower-level data is fully linear as described in (Equation8
(10)
(10) ).
Corollary 3.16
Let the lower-level data be given as in (Equation8(10)
(10) ) and fix
. Then the following assertions hold.
(a) | Let | ||||
(b) | Let |
Proof.
The first assertion directly follows from Lemma 3.11 and Theorem 3.14. The second statement can be obtained from Corollary 3.6 and Theorem 3.14 as is a convex polyhedral set and, thus, closed, and these properties also ensure that Γ is lower semicontinuous w.r.t. its domain at each point from
, see e.g. [Citation39, Example 9.35].
Remark 3.17
Taking a look back at the optimal value function reformulation for standard scalar bilevel optimization problems, we know from Lemma 2.1 that the feasible set of (Equation5(6b)
(6b) ) is closed if and only if φ is upper semicontinuous, and this can also be seen from (Equation2
(2)
(2) ) as sublevel sets of extended-real-valued functions are closed if and only if they are lower semicontinuous. The latter property is clearly milder than the continuity of φ on its domain
which seems to be necessary for this desirable closedness when focusing on the model problem (Equation4
(6a)
(6a) ).
Thus, having problems (Equation6a(7)
(7) ) and (Equation6b
(8)
(8) ) as well as Corollary 3.4 at hand, it is seemingly reasonable to work out conditions which ensure that the graphs of
and
are closed. This is enough to obtain the closedness of the feasible sets of (Equation6a
(7)
(7) ) and (Equation6b
(8)
(8) ) which, in turn, provides the basis for further existence results in multiobjective bilevel optimization. However, note that due to Lemma 3.12, it turns out that whenever the feasibility mapping Γ is locally bounded, then this apparently milder approach yields no new insights. Observe that this is in accordance with the aforementioned scalar situation as the optimal value function φ is lower semicontinuous on its domain whenever Γ is locally bounded.
3.3. An intermediate approach to multiobjective bilevel optimization
On the one hand, the feasible set of (Equation-BPP
(4)
(4) ) is likely to be much smaller than the one of (Equation
-BPP
(4)
(4) ) since the solution criterion behind Ψ is sharper than the one behind
. On the other hand, from the viewpoint of existence theory, necessary optimality conditions, and solution algorithms, a closed feasible set is desirable. The latter is given for (Equation
-BPP
(4)
(4) ) under mild assumptions, see Corollary 3.6, while the feasible set of (Equation
-BPP
(4)
(4) ) is not likely to be closed apart from selected situations.
In this subsection, we suggest yet another possibility for the choice of in the general multiobjective bilevel optimization problem (EquationBPP
(BPP)
(BPP) ) which induces an intermediate model between (Equation
-BPP
(4)
(4) ) and (Equation
-BPP
(4)
(4) ). To start, however, we would like to suggest an intermediate value function model which bridges (Equation
-VFR
(5)
(5) ) and (Equation
-VFR
(5)
(5) ) to some extent. There are two reasons for this approach. First, it allows for a simple definition of an intermediate solution map such that the associated models (EquationBPP
(BPP)
(BPP) ) and (EquationVFR
(VFR)
(VFR) ) are equivalent. Second, noting that, in order to determine efficient and weakly efficient points of some multiobjective optimization problem, one has to compute its nondominated and weakly nondominated points first before identifying their pre-images in the feasible set, this procedure seems the more natural one.
Therefore, let us introduce by means of
and consider
As
is closed under mild assumptions, see e.g. Corollary 3.6, the inclusions
are likely to hold and would give
for each
. Hence, (Equation
-VFR
(14)
(14) ) can be interpreted as an intermediate problem between (Equation
-VFR
(5)
(5) ) and (Equation
-VFR
(5)
(5) ) since the feasible set of (EquationEquation
-VFR
(14)
(14)
(5)
(5) ) is not smaller than the one of (Equation
-VFR
(5)
(5) ) and likely to be not larger than the one of (Equation
-VFR
(5)
(5) ). Furthermore, (Equation
-VFR
(14)
(14) ) possesses a closed feasible set by construction of
, and, thus, efficient and weakly efficient points of (Equation
-VFR
(14)
(14) ) exist under standard assumptions.
Based on , let us introduce
by means of
In the subsequent lemma, we comment on the properties of
. The simple proof follows by definition of
as well as our above discussion on the properties of
and is, thus, omitted.
Lemma 3.18
(a) | The set | ||||
(b) | Whenever | ||||
(c) | We have |
By definition of , the problem
is equivalent to (Equation
-VFR
(14)
(14) ), and due to Lemma 3.18(b), can be seen as an intermediate model between (Equation
-BPP
(4)
(4) ) and (Equation
-BPP
(4)
(4) ). Clearly, (Equation
-BPP
(15)
(15) ) has a closed feasible set and, due to Theorem 3.14, is likely to possess efficient and weakly efficient points which can be interpreted as approximately efficient and approximately weakly efficient for (Equation
-BPP
(4)
(4) ).
Let us state yet another motivation behind the consideration of the models (Equation-BPP
(15)
(15) ) and (Equation
-VFR
(14)
(14) ). When solving (Equation
-BPP
(4)
(4) ) and (Equation
-VFR
(5)
(5) ) numerically with a suitable solution algorithm, respectively, one typically obtains a sequence of iterates from the solution method. Taking into account the potential non-closedness of
and
, accumulation points of this sequence are not necessarily feasible to (Equation
-BPP
(4)
(4) ) and (Equation
-VFR
(5)
(5) ), respectively. However, they are likely to be feasible to (Equation
-BPP
(15)
(15) ) and (EquationEquation
-VFR
(14)
(14)
(5)
(5) ) as
and
are closed supersets of
and
, respectively. Hence, qualitative properties of solution methods associated with (Equation
-BPP
(4)
(4) ) and (Equation
-VFR
(5)
(5) ) are naturally related to the model problems (Equation
-BPP
(15)
(15) ) and (Equation
-VFR
(14)
(14) ), respectively.
Let us point out that one does not obtain equality in Lemma 3.18(c) in general situations. Furthermore, when defining by
and
by
for all
, then the corresponding problems (EquationBPP
(BPP)
(BPP) ) and (EquationVFR
(VFR)
(VFR) ) for
and
, respectively, are not necessarily equivalent. We omitted this undesirable behavior by starting with the definition of a suitable intermediate frontier mapping before introducing an intermediate efficiency mapping.
Example 3.19
We consider (EquationP(x)(P(x))
(P(x)) ) with
,
, and
We easily find
which gives
Observe, however, that
i.e. the feasible set of any superordinate model (EquationBPP
(BPP)
(BPP) ) for
in likely to be smaller than the feasible set of the associated value function reformulation (EquationVFR
(VFR)
(VFR) ) for
.
Let us also mention that
holds in this example. This also shows
.
The following example shows that (Equation-BPP
(4)
(4) ), (Equation
-BPP
(4)
(4) ), and (Equation
-BPP
(15)
(15) ) may possess pairwise different solutions.
Example 3.20
Motivated by Example 2.3, for , and
, we consider the parametric multiobjective optimization problem (EquationP(x)
(P(x))
(P(x)) ) with the data
A simple calculation reveals
Observe that
holds true.
Now, we consider the superordinate semivectorial bilevel optimization problem
where
. Let us start with the investigation of
. The associated problem (Equation
-BPP
(4)
(4) ) does not possess a global minimizer, but there is a local minimizer at
. Whenever
, the associated problem (Equation
-BPP
(4)
(4) ) possesses the uniquely determined global minimizer
, and no other local minimizers exist. Finally, for
, the associated problem (Equation
-BPP
(15)
(15) ) possesses the uniquely determines global minimizer
(which is not feasible to (Equation
-BPP
(4)
(4) )) and an additional local minimizer at
.
Finally, we would like to point the reader's attention to the fact that, in contrast to Corollary 3.4, (Equation-VFR
(14)
(14) ) and
(13)
(13) are not necessarily equivalent as the feasible set of (Equation13
(16)
(16) ) is likely to be larger than the one of (Equation
-VFR
(14)
(14) ). However, if
is closed, the feasible set of (Equation13
(16)
(16) ) is included in the feasible set of (Equation6b
(8)
(8) ) which, by Corollary 3.4, equals the feasible set of (Equation
-VFR
(5)
(5) ). Thus, the enlargement of the feasible set in (Equation13
(16)
(16) ) in comparison with (Equation
-VFR
(14)
(14) ) is somewhat controllable.
Example 3.21
Let us reinspect the semivectorial bilevel optimization problem from Example 3.20. One can easily check that, for ,
satisfies
but
is not feasible to the associated problem (Equation
-BPP
(15)
(15) ) and, thus, (Equation
-VFR
(14)
(14) ). Keeping our above discussion in mind and noticing that
is closed, the associated model (Equation13
(16)
(16) ) possesses the global minimizer
, see Example 3.20 as well.
4. Towards necessary optimality conditions
For the derivation of necessary optimality conditions and constraint qualifications for (Equation-BPP
(4)
(4) ) and (Equation
-BPP
(4)
(4) ) via (Equation
-VFR
(5)
(5) ) and (Equation
-VFR
(5)
(5) ), respectively, in terms of the limiting tools of generalized differentiation, it is important to have formulas or at least upper estimates for the coderivative of Φ and
available. Here, we focus on the latter and comment on two approaches which can be used to obtain such estimates in terms of initial problem data.
4.1. Coderivative estimates via the domination property
In the literature, one can find several papers dealing with the derivation of upper coderivative estimates for the frontier mapping Φ in the case where (EquationP(x)(P(x))
(P(x)) ) possesses the domination property for all
from a neighborhood of the reference point, see e.g. [Citation40–42]. Apart from the fact that these papers completely ignore the fact that
is likely to be non-closed, so that the coderivative is not well-defined, they obtain validity of the upper estimate
(14)
(14) only for points
and
where
In practice, this means that the estimate (Equation14
(17)
(17) ) is, more or less, only reasonable for arguments
from
. For the derivation of necessary optimality conditions for (Equation
-BPP
(4)
(4) ) via (Equation
-VFR
(5)
(5) ), however, this additional constraint on the variable
might be too restrictive.
In the proof of [Citation24, Theorem 4.1], the authors claim that for , one has the estimate
(15)
(15) for all
. This estimate, however, does not depend on the choice of the ordering cone
which is somewhat dubious. As the following example shows, this estimate is indeed false, and so are [Citation24, Theorems 4.1, 4.4].
Example 4.1
We consider (EquationP(x)(P(x))
(P(x)) ) with
,
, and
i.e. the associated problem (EquationP(x)
(P(x))
(P(x)) ) does not depend on the parameter. We find
and observe that (EquationP(x)
(P(x))
(P(x)) ) possesses the domination property (for each
). Let us fix
and
. Then we find
This can be easily seen from
and
, the product rule for the computation of limiting normals, see e.g. [Citation38, Proposition 1.2], and a simple calculation of the normal cones to
(which is convex) and
in
. Hence, for
, we find
showing that the estimate (Equation15
(P(x,λ))
(P(x,λ)) ) fails to be true for general arguments.
Our next example indicates that the results from [Citation40–42] can be directly generalized to weak frontier mappings.
Example 4.2
We consider (EquationP(x)(P(x))
(P(x)) ) with
,
, and
Then we find
for all
as well as
Using this, one can easily check that
holds for all
, i.e. the associated problem (EquationP(x)
(P(x))
(P(x)) ) possesses the weak domination property for all
(actually, it also possesses the domination property for all
). Let us consider
and
. It is not hard to see that
This directly shows that the inclusion
(16)
(16) holds for all
, but is violated for, e.g.
already, where
Let us now formally prove that the estimate (Equation16(16)
(16) ) holds for all
.
Lemma 4.3
Let be fixed and let
and
be locally closed around
. Assume that (EquationP(x)
(P(x))
(P(x)) ) possesses the weak domination property for all
where
is a neighborhood of
. Then, for each
, the estimate (Equation16
(16)
(16) ) is valid.
Proof.
Fix . By mimicking the proof of [Citation40, Lemma 3.2], which does not rely on the precise underlying notion of nondominance, we find
Furthermore, locally around
, the mappings
and
are identical by the weak domination property. Noting that the coderivative is a local construction, the claim follows.
We would like to point the reader's attention to the similarities in the estimates (Equation14(17)
(17) ) and (Equation16
(16)
(16) ). Indeed, the right-hand side is the same in both estimates which is somewhat unsatisfying as the precise underlying notion of nondominance seems to make no difference. More precisely, it does not seem to be too reasonable to try to find assumptions which guarantee correctness of the results, e.g. in [Citation40] for the frontier mapping as we obtained the same upper estimate for the coderivative of the weak frontier mapping under most likely milder conditions.
With the aid of Lemma 4.3, we are in position to obtain an upper estimate for the coderivative of in terms of initial problem data. The following result is inspired by [Citation40, Theorem 3.3].
Theorem 4.4
Let be fixed and let
be locally closed around
. Assume that (EquationP(x)
(P(x))
(P(x)) ) possesses the weak domination property for all
where
is a neighborhood of
. Furthermore, let Γ be locally bounded at
. Let f be locally Lipschitz continuous at all points
such that
and
hold. Then, for each
,
If, additionally, f is continuously differentiable at all points
such that
and
hold, then, for each
,
Proof.
Let us note that closedness of and local boundedness of Γ at
yield that, locally around
,
and
are closed. Combining Lemma 4.3 and the first part of the proof of [Citation40, Theorem 3.3] while taking into account that
since
is a cone gives
for each
.
Defining by
for each
gives
, and
holds for each
and
, see e.g. [Citation46, Lemma 5.7]. Thus, in order to infer the more general assertion of the theorem, we apply the chain rule from [Citation46, Theorem 5.2]. Therefore, we note that the involved intermediate mapping
(17)
(17) is inner semicompact at
w.r.t. its domain since Γ is assumed to be locally bounded at
, and that f is Lipschitz continuous at
which serves as a qualification condition. Then we find
and noting that, due to Proposition 3.1, each
with
already belongs to
yields the claim.
The second statement of the theorem is an obvious consequence of the first assertion.
Let us note that the chain rule from [Citation46, Theorem 5.2] also allows for the derivation of refined upper estimates in terms of directional coderivatives.
We would like to point the interested reader to the fact that in the proofs of [Citation40, Theorem 3.3] and [Citation24, Theorem 4.1], the authors rely on the chain rule from [Citation38, Theorem 3.18(i)] which is only possible if the intermediate mapping from (Equation17(17)
(17) ) possesses certain inner semicontinuity properties. These, however, are not inherent from the assumptions stated in [Citation24,Citation40], and one can easily check that even inner semicontinuity of Γ is not sufficient for these requirements. Thus, the aforementioned results are not reliable. Let us also note that, in situations where f is Lipschitzian, the coderivative of Σ can be computed exploiting a combination of the image and pre-image rule as we have
where
is given by
for all
,
, and
, see e.g. [Citation46, Sections 5.1.3, 5.1.4]. This, however, still makes some additional boundedness assumption on Γ necessary, and the resulting upper estimate on the coderivative of Σ would also comprise a union over
. More precisely, this approach precisely recovers the estimates from Theorem 4.4.
Let us specify Theorem 4.4 for the scalar case where and
. Then the weak domination property is inherently satisfied. Furthermore, we find
, and
equals the so-called limiting subdifferential at
of the optimal value function φ from (Equation1
(1)
(1) ) provided the latter is continuous around
, see [Citation38, Definition 1.77, Theorem 1.80]. Then the estimates in Theorem 4.4 recover those obtained in [Citation54, Theorem 7] under slightly different assumptions. Hence, one can interpret Theorem 4.4 as a generalization of this result to the multiobjective situation. Nevertheless, Theorem 4.4 is of limited practical use as it provides no information about situations where the argument
of the coderivative is chosen in
, and such values of
might be of interest when deriving necessary optimality conditions for (Equation
-VFR
(5)
(5) ) as the concept of subdifferentials is not reasonable in vector-valued scenarios whenever scalarization is not taken into account.
4.2. Coderivative estimates via scalarization
In this section, we aim to find upper coderivative estimates for the weak frontier mapping via a scalarization approach. This, however, makes additional assumptions necessary.
Assumption 4.5
For each ,
is
-convex and
is convex.
We emphasize that Assumption 4.5 guarantees that is convex for each
. Hence, due to [Citation2, Corollary 5.29], for each
, we find the equivalence
where
is the solution mapping associated with the scalar parametric optimization problem
(P(x,λ))
(P(x,λ)) Based on the chain rule, we obtain a simple upper estimate for the coderivative of
in terms of the coderivative of
, as we have
where the mapping
is given by
for each
. We omit the proof as it mainly parallels the arguments used to validate Theorem 4.4.
Lemma 4.6
Fix and let
be locally closed around
. Let
be inner semicompact at
w.r.t.
. Furthermore, for each
with
, let
be closed locally around
, and let f be locally Lipschitz continuous at
. Then, for each
,
If, additionally, f is continuously differentiable at all points
such that
and
hold, then, for each
,
Let us emphasize that Lemma 4.6 is correct even in the absence of Assumption 4.5 which is not needed for the proof. We note that the estimates from Lemma 4.6 are closely related to those ones obtained in Theorem 4.4. Indeed, the only difference (apart from the underlying assumptions) is that in Theorem 4.4, all estimates are valid for only, while the coderivative of the efficiency mapping
appearing in Lemma 4.6 is replaced by the coderivative of the feasibility mapping Γ in Theorem 4.4. Let us also visualize this in exemplary way.
One can easily check that the estimate provided in Lemma 4.6 is actually sharp in the context of Example 4.2. Indeed, one obtains
for each
in this situation (observe that the only point
which satisfies
in the present situation is
). We also note that the estimates from Theorem 4.4 do not apply for
as these vectors do not belong to
.
It is an essential disadvantage of the estimates from Lemma 4.6 that they are not stated in terms of initial problem data as the coderivative of is a fully implicit object. Subsequently, we aim to estimate it from above. In order to deal with this issue, Assumption 4.5 turns out to be helpful as we will demonstrate in the results below. For brevity of notation, we introduce an intermediate mapping
given by
For given
,
comprises all (normalized) scalarization parameters for which y is a minimizer of (EquationP
(P(x,λ))
(P(x,λ)) ). We note that, by compactness of
, Ξ is inner semicompact w.r.t. its domain at each point of its domain.
Lemma 4.7
Fix and let
be closed locally around
. Furthermore, for each
, let
be closed locally around
. Additionally, let Assumption 4.5 hold. Finally, let one of the following conditions be valid:
(a) |
| ||||
(b) | for each |
Then, for each , we have
Proof.
Defining by
for each
, we find
since Assumption 4.5 holds. Since Ξ is inner semicompact at
w.r.t. its domain, the intermediate mapping
is inner semicompact at
w.r.t. its domain as well. Thus, the result follows from the chain rule stated in [Citation46, Theorem 5.2] while observing that
holds for each
and
while each of the additionally postulated assumptions guarantees validity of the qualification condition which is imposed in [Citation46, Theorem 5.2].
Let us note that Lemma 4.7 generalizes [Citation19, Proposition 3.2] to arbitrary ordering cones while coming along with a simpler proof and another type of qualification condition. Furthermore, we would like to mention that Lemma 4.7 can be used to derive necessary optimality conditions for (Equation-BPP
(4)
(4) ) directly.
In order to obtain a valuable coderivative estimate for the weak frontier mapping from Lemmas 4.6 and 4.7, it remains to estimate the appearing coderivative of . This, however, is a well-established subject in variational analysis since
is the solution mapping of a scalar parametric optimization problem. Exemplary, let us mention that, in the presence of Assumption 4.5, (EquationP
(P(x,λ))
(P(x,λ)) ) is a convex optimization problem for each
and
. Assuming, additionally, that f is a smooth function, we find
i.e.
possesses the structure of a so-called parametric variational system. Consulting e.g. [Citation38, Section 4.4], coderivative estimates for
can be obtained in terms of derivatives of f and coderivatives of the normal cone mapping
under suitable constraint qualifications. The remaining coderivative of the normal cone map may be specified for diverse different types of constraint systems, see e.g. [Citation55–58]. Exemplary, this has been worked out in the proof of [Citation19, Corollary 3.4] in the particular situation where
and Γ is induced by smooth parametric inequality constraints.
As the purpose of this note is mainly focused on the value behind the model reformulations (Equation-VFR
(5)
(5) ) and (Equation
-VFR
(5)
(5) ), we abstain from the postulation of any more technical results, but simply combine Lemmas 4.6 and 4.7 to obtain a coderivative estimate which can be made fully explicit by respecting the above comments by the interested reader.
Theorem 4.8
Fix and let
be locally closed around
. Furthermore, let Assumption 4.5 be valid. Let
be inner semicompact at
w.r.t.
. Furthermore, for each
with
, let
be closed locally around
, let f be locally Lipschitz continuous at
, and, for each
, let
be closed locally around
, and let one of the conditions (a) or (b) of Lemma 4.7 be valid. Then, for each
,
If, additionally, f is continuously differentiable at all points
such that
and
hold, then, for each
,
Let us note that, based on Lemma 3.5, one can easily check that the numerous closedness assumptions as well as the inner semicompactness assumption on in Theorem 4.8 are inherently satisfied whenever Γ is lower semicontinuous w.r.t. its domain locally around
, and locally bounded at
. Both assumptions are inherent whenever
holds for some nonempty and compact set
and all
. Then it remains to validate condition (a) or (b) of Lemma 4.7.
Remark 4.9
Let Assumption 4.5 be valid and be the optimal value function associated with (EquationP
(P(x,λ))
(P(x,λ)) ), i.e.
Then we find the representation
where
has been defined in (Equation3
(3)
(3) ). Using
from the proof of Lemma 4.7 as well as
and
given by
we find
. Seemingly, this representation offers the possibility to obtain an upper estimate for the coderivative of
via an intersection rule, see e.g. [Citation38, Proposition 3.20], and the chain rule, see e.g. [Citation46, Theorem 5.2]. Indeed, in the case where
is a locally Lipschitzian function, which holds under fairly mild assumptions, one can apply the chain rule from [Citation46] twice in order to find an upper estimate of the coderivative of
which comprises the limiting subdifferential of (a non-specified multiple of)
. The latter, however, cannot be approximated from above by the Cartesian product of the associated subdifferentials w.r.t. the variables x and λ in general which is a first difficulty. A second problem pops up as the constraint qualification from [Citation38, Proposition 3.20] which is sufficient to get the intersection rule working is also likely to fail. Hence, we abstain here from providing the details as this approach does not seem too reasonable.
Remark 4.10
In scalar bilevel optimization, the value function reformulation is often preferred over the formulation comprising the lower-level solution mapping when the derivation of necessary optimality conditions is considered. This is due to the fact that the computation of upper estimates for generalized derivatives of the lower-level value function is often much easier than obtaining upper estimates for generalized derivatives of the lower-level solution mapping. Thus, on the one hand, Lemma 4.6 and Theorem 4.8 seemingly are of limited practical use in the context of necessary optimality conditions as the coderivative of some solution mapping associated with the lower-level problem appears. Indeed, one could try to directly make use of Lemma 4.7 in order to obtain necessary optimality conditions. On the other hand, the value function approach to bilevel optimization is often preferred for the construction of solution algorithms, and taking this aspect into account, some upper estimate for the coderivative of the weak frontier mapping might be essential, and this is where Lemma 4.6 and Theorem 4.8 may become handy.
5. Conclusions
In this paper, we visualized that multiobjective bilevel optimization is, up to a certain degree, only reasonable if the lower-level efficiency-type and frontier-type mapping possess closed graphs as this is a fundamental assumption in order to guarantee the existence of solutions (in whatever sense) and to allow for the derivation of optimality conditions. We presented conditions which guarantee validity of these closedness properties, gave existence results, and discussed the computation of upper coderivative estimates for frontier-type mappings. The latter is an essential step on the route to necessary optimality conditions as visualized in the recent paper [Citation24] which, however, has some flaws which we carved out here. Furthermore, we commented on different ways on how to introduce a value function reformulation of a multiobjective bilevel optimization problem which might be important in algorithmic applications.
In the future, it has to be investigated whether the value function reformulation of a multiobjective optimization problem can be exploited beneficially for its algorithmic solution. Whenever the lower-level problem is a scalar optimization problem, this has already been demonstrated in several different ways in the literature, see e.g. [Citation5, Section 20.6.4] for an overview. Furthermore, it remains open whether the approach from Section 3.3 is suitable from the viewpoint of optimality conditions as, in contrast to Section 4, it is not clear how the derivation of coderivative estimates for the mappings and
can be done.
Disclosure statement
No potential conflict of interest was reported by the author(s).
References
- Ehrgott M. Multicriteria optimization. Berlin: Springer; 2005. doi: 10.1007/3-540-27659-9
- Jahn J. Vector optimization – theory, applications, and extensions. Berlin: Springer; 2011. doi: 10.1007/978-3-642-17005-8
- Dempe S, Mordukhovich BS, Zemkoho AB. Sensitivity analysis for two-level value functions with applications to bilevel programming. SIAM J Optim. 2012;22(4):1309–1343. doi: 10.1137/110845197
- Dempe S. Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization. 2003;52(3):333–359. doi: 10.1080/0233193031000149894
- Dempe S. Bilevel optimization: theory, algorithms, applications and a bibliography. In: Bilevel optimization: advances and next challenges. Cham: Springer; 2020. p. 581–672. doi: 10.1007/978-3-030-52119-6_20
- Bard JF. Practical bilevel optimization: algorithms and applications. Dordrecht: Kluwer Academic; 1998. doi: 10.1007/978-1-4757-2836-1
- Dempe S. Foundations of bilevel programming. Dordrecht: Kluwer Academic; 2002. doi: 10.1007/b101970
- Dempe S, Kalashnikov V, Pérez-Valdéz G, et al. Bilevel programming problems – theory, algorithms and applications to energy networks. Berlin: Springer; 2015. doi: 10.1007/978-3-662-45827-3
- Shimizu K, Ishizuka Y, Bard JF. Nondifferentiable and two-level mathematical programming. Dordrecht: Kluwer Academic; 1997. doi: 10.1007/978-1-4615-6305-1
- Bolintineanu S. Necessary conditions for nonlinear suboptimization over the weakly efficient set. J Optim Theory Appl. 1993;78(3):579–598. doi: 10.1007/BF00939883
- Bolintineanu S. Optimality conditions for minimization over the (weakly or properly) efficient set. J Math Anal Appl. 1993;173(2):523–541. doi: 10.1006/jmaa.1993.1085
- Bonnel H, Kaya CY. Optimization over the efficient set of multi-objective convex optimal control problems. J Optim Theory Appl. 2010;147(1):93–112. doi: 10.1007/s10957-010-9709-y
- Horst R, Thoai NV. Maximizing a concave function over the efficient or weakly-efficient set. Eur J Oper Res. 1999;117(2):239–252. doi: 10.1016/S0377-2217(98)00230-6
- Bonnel H. Optimality conditions for the semivectorial bilevel optimization problem. Pac J Optim. 2006;2(3):447–468. Available from: http://www.yokohamapublishers.jp/online2/pjov3-1.html
- Bonnel H, Morgan J. Semivectorial bilevel optimization problem: penalty approach. J Optim Theory Appl. 2006;131(3):365–382. doi: 10.1007/s10957-006-9150-4
- Dempe S, Gadhi N, Zemkoho AB. New optimality conditions for the semivectorial bilevel optimization problem. J Optim Theory Appl. 2013;157(1):54–74. doi: 10.1007/s10957-012-0161-z
- Dempe S, Mehlitz P. Semivectorial bilevel programming versus scalar bilevel programming. Optimization. 2020;69(4):657–679. doi: 10.1080/02331934.2019.1625900
- Liu B, Wan Z, Chen J, et al. Optimality conditions for pessimistic semivectorial bilevel programming problems. J Inequalities Appl. 2014;41(1). doi: 10.1186/1029-242X-2014-41
- Zemkoho AB. Solving ill-posed bilevel programs. Set-Valued Var Anal. 2016;24:423–448. doi: 10.1007/s11228-016-0371-x
- Dandurand B, Guarneri P, Fadel GM, et al. Bilevel multiobjective packing optimization for automotive design. Struct Multidiscipl Optim. 2014;50:663–682. doi: 10.1007/s00158-014-1120-0
- Eichfelder G. Multiobjective bilevel optimization. Math Program. 2010;123:419–449. doi: 10.1007/s10107-008-0259-0
- Eichfelder G. Methods for multiobjective bilevel optimization. In: Dempe S, Zemkoho AB, editors. Bilevel optimization: advances and next challenges. Cham: Springer; 2020. p. 423–449. doi: 10.1007/978-3-030-52119-6_15
- Gebhardt E, Jahn J. Global solver for nonlinear bilevel optimization problems. Pac J Optim. 2009;5(2):387–401. Available from: http://www.ybook.co.jp/pjo.html
- Lafhim L, Zemkoho AB. Extension of the value function reformulation to multiobjective bilevel optimization. Optim Lett. 2023;17:1337–1358. doi: 10.1007/s11590-022-01948-9
- Ruuska S, Miettinen K, Wiecek MM. Connections between single-level and bilevel multiobjective optimization. J Optim Theory Appl. 2012;153:60–74. doi: 10.1007/s10957-011-9943-y
- Gadhi N, Dempe S. Necessary optimality conditions and a new approach to multiobjective bilevel optimization problems. J Optim Theory Appl. 2012;155:100–114. doi: 10.1007/s10957-012-0046-1
- Ye JJ. Necessary optimality conditions for multiobjective bilevel programs. Math Oper Res. 2011;36(1):165–184. doi: 10.1287/moor.1100.0480
- Yin Y. Multiobjective bilevel optimization for transportation planning and management problems. J Adv Transport. 2002;36(1):93–105. doi: 10.1002/atr.5670360106
- Benko M, Mehlitz P. On implicit variables in optimization theory. J Nonsmooth Anal Optim. 2021;2:7215. doi: 10.46298/jnsao-2021-7215
- Luo X, Liu Y, Liu X. Bi-level multi-objective optimization of design and subsidies for standalone hybrid renewable energy systems: a novel approach based on artificial neural network. J Build Eng. 2021;41:Article ID 102744. doi: 10.1016/j.jobe.2021.102744
- Ma Y, Zheng W, Feng C, et al. A bi-level multi-objective location-routing model for municipal waste management with obnoxious effects. Waste Manag. 2021;135:109–121. doi: 10.1016/j.wasman.2021.08.034
- Outrata JV. On the numerical solution of a class of Stackelberg problems. Zeitschrift Oper Res. 1990;34(4):255–277. doi: 10.1007/BF01416737
- Ye JJ, Zhu DL. Optimality conditions for bilevel programming problems. Optimization. 1995;33(1):9–27. doi: 10.1080/02331939508844060
- Dempe S, Dutta J, Mordukhovich BS. New necessary optimality conditions in optimistic bilevel programming. Optimization. 2007;56(5-6):577–604. doi: 10.1080/02331930701617551
- Dempe S, Franke S. On the solution of convex bilevel optimization problems. Comput Optim Appl. 2016;63(3):685–703. doi: 10.1007/s10589-015-9795-8
- Dempe S, Zemkoho AB. The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Math Program. 2013;138:447–473. doi: 10.1007/s10107-011-0508-5
- Mordukhovich BS, Nam NM, Phan HM. Variational analysis of marginal functions with applications to bilevel programming. J Optim Theory Appl. 2012;152(3):557–586. doi: 10.1007/s10957-011-9940-1
- Mordukhovich BS. Variational analysis and generalized differentiation. Berlin: Springer; 2006. doi: 10.1007/3-540-31247-1
- Rockafellar RT, Wets RJ-B. Variational analysis. Berlin: Springer; 2009. doi: 10.1007/978-3-642-02431-3
- Huy NQ, Mordukhovich BS, Yao J-C. Coderivatives of frontier and solution maps in parametric multiobjective optimization. Taiwan J Math. 2008;12(8):2083–2111. doi: 10.11650/twjm/1500405137
- Li SJ, Xue XW. Sensitivity analysis of gap functions for vector variational inequality via coderivatives. Optimization. 2014;63(7):1075–1098. doi: 10.1080/02331934.2012.688970
- Xue XW, Li SJ, Liao CM, et al. Sensitivity analysis of parametric vector set-valued optimization problems via coderivatives. Taiwan J Math. 2011;15(4):2533–3554. Available from: https://www.jstor.org/stable/taiwjmath.15.6.2533
- Göpfert A, Riahi H, Tammer C, et al. Variational methods in partically ordered spaces. New York: Springer; 2003. doi: 10.1007/b97568
- Henig MI. The domination property in multicriteria optimization. J Math Anal Appl. 1986;114(1):7–16. doi: 10.1016/0022-247X(86)90061-2
- Luc DT. On the domination property in vector optimization. J Optim Theory Appl. 1984;43:327–330. doi: 10.1007/BF00936168
- Benko M, Mehlitz P. Calmness and calculus: two basic patterns. Set-Valued Var Anal. 2022;30:81–117. doi: 10.1007/s11228-021-00589-x
- Liu CG, Ng KF, Yang WH. Merit functions in vector optimization. Math Program. 2009;119:215–237. doi: 10.1007/s10107-008-0208-y
- Sawaragi Y, Nakayama H, Tanino T. Theory of multiobjective optimization. Orlando: Academic Press; 1985. Available from: https://www.sciencedirect.com/bookseries/mathematics-in-science-and-engineering/vol/176
- Plastria F. On the structure of the weakly efficient set for quasiconvex vector minimization. J Optim Theory Appl. 2020;184:547–564. doi: 10.1007/s10957-019-01608-6
- Bank B, Guddat J, Klatte D, et al. Non-linear parametric optimization. Basel: Birkhäuser; 1983. doi: 10.1007/978-3-0348-6328-5
- Nožička F, Guddat J, Hollatz H, et al. Theorie der linearen parametrischen Optimierung. Berlin: Akademie-Verlag; 1974. doi: 10.1515/9783112471548
- Dontchev AL, Rockafellar RT. Implicit functions and solution mappings. Heidelberg: Springer; 2014. doi: 10.1007/978-0-387-87821-8
- Isermann H. Proper efficiency and the linear vector maximization problem. Oper Res. 1974;22(1):189–191. doi: 10.1287/opre.22.1.189Available from: https://www.jstor.org/stable/169229
- Mordukhovich BS, Nam NM, Yen NY. Subgradients of marginal functions in parametric mathematical programming. Math Program. 2009;116:369–396. doi: 10.1007/s10107-007-0120-x
- Benko M, Gfrerer H, Outrata JV. Stability analysis for parametric variational systems with implicit constraints. Set-Valued Var Anal. 2020;28:167–193. doi: 10.1007/s11228-019-00516-1
- Gfrerer H, Outrata JV. On computation of generalized derivatives of the normal-cone mapping and their applications. Math Oper Res. 2016;41(4):1535–1556. doi: 10.1287/moor.2016.0789
- Gfrerer H, Outrata JV. On computation of limiting coderivatives of the normal-cone mapping to inequality systems and their applications. Optimization. 2016;65(4):671–700. doi: 10.1080/02331934.2015.1066372
- Gfrerer H, Outrata JV. On the Aubin property of a class of parameterized variational systems. Math Methods Oper Res. 2017;86(3):443–467. doi: 10.1007/s00186-017-0596-y