Sequential Optimality Conditions for Bilevel Multiobjective Fractional Programming Problems with Extremal Value Function
Subject Areas : Operation Research
1 - University Chouaib Doukkali
Keywords: convex, vetor, mappings,
Abstract :
In this paper, we consider a bilevel multiobjective fractional programming problem $(\mathcal{BMFP})$ with an extremal value function. We provide necessary and sufficient optimality conditions characterizing (properly, weakly) efficient solutions of the considered problem. These optimality conditions are obtained in terms of sequences and based on sequential calculus rules for the Br\o ndsted-Rockafellar subdifferential of the sum and the multi-composition of convex functions, without constraint qualifications.
Ahmad, I., Zhang, F., Liu, J. (2018). Anjum, M.N., Zaman, M., Tayyab, M., Waseem, M., Farid, H.U.: A linear bi-level multi-objective program for optimal allocation of water resources. Plos one 13(2), 1-25.
Aboussoror, A., Adly, S. (2011) A Fenchel-Lagrange duality approach for a bilevel programming problem with extremal-value function. J. Optim. Theory Appl. 149(2), 254-268.
Bard, J.F. (2013). Practical Bilevel Optimization: Algorithms and Applications, vol. 30. Springer Science & Business Media.
Bot, R.I., Vargyas, E., Wanka, G. (2007) Conjugate duality for multiobjective composed optimization problems. Acta Math. Hungarica 116(3), 177-196.
Bot, R.I., Grad, S.M., Wanka, G. (2009). Duality in Vector Optimization. Springer Science & Business Media.
Colson, B., Marcotte, P., Savard, G. (2007). An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235-256.
Dempe, S. (2002). Foundations of Bilevel Programming. Springer Science & Business Media.
Dempe, S. (2015). Kalashnikov, V., Perez-Valdes, G.A., Kalashnykova, N.: Bilevel Programming Problems. Springer, Berlin, Heidelberg.
Eichfelder, G. (2010) Multiobjective bilevel optimization. Math. Program. 123(2), 419-449.
Floudas, C.A., (2009). Pardalos, P.M.: Encyclopedia of Optimization. Springer Science & Business Media.
Laghdir, M., Dali, I., Moustaid, M.B. (2020). A generalized sequential formula for subdi erential of multi-composed functions de ned on Banach spaces and applications. Pure Appl. Funct. Anal. 5(4), 999-1023.
Migdalas, A. (1995). Bilevel programming in traffic planning: Models, methods and challenge. J. Global Optim. 7(4), 38-405.
Stancu-Minasian, I.M. (2012). Fractional Programming: Theory, Methods and Applications, vol. 409. Springer Science & Business Media.
Stancu-Minasian, I.M., (2019) A ninth bibliography of fractional programming. Optimization 68(11), 2125-2169.
Shimizu, K., (2012), Ishizuka, Y., Bard, J.F.: Nondi erentiable and Two-level Mathematical Programming. Springer Science & Business Media.
Shimizu, K., Ishizuka, Y., (1985) Optimality conditions and algorithms for parameter design problems with two-level structure. IEEE Trans. Autom. Control 30(10), 986-993.
Thibault, L. (1995). A generalized sequential formula for subdi erentials of sums of convex functions de ned on Banach spaces. Lecture Notes Econom. Math. Syst.
Thibault, L. (1997). Sequential convex subdi erential calculus and sequential Lagrange multipliers. SIAM J. Control Optim.
Wang, H., Zhang, R. (2015). Duality for multiobjective bilevel programming roblems with extremal-value function. J. Math. Res. Appl. 35(3), 311-320.
Yin, Y. (2002). Multiobjective bilevel optimization for transportation planning and management problems. J. Adv. Transp. 36(1), 93-105.
Islamic Azad University Rasht Branch ISSN: 2588-5723 E-ISSN:2008-5427
|
|
Optimization Iranian Journal of Optimization Volume 14, Issue 3, 2022, 231-244 Research Paper |
|
Online version is available on: www.ijo.rasht.iau.ir
Sequential Optimality Conditions for Bilevel Multiobjective Fractional Programming Problems with Extremal Value Function
Mohamed Laghdir*
University Chouaib Doukkali
Revise Date: 01 September 2022 Abstract
Keywords: Sequential Optimality Conditions Brøndsted-Rockafellar Subdifferential Bilevel Programming Multiobjective fractional programming |
INTRODUCTION
Bilevel programming problems are considered as a class of optimization problems
for which the feasible set and/or the objective function of the so-called leader's problem depend on the set of solutions or the optimal value function of another optimization problem called the follower's problem. This type of mathematical problems appears in many practical problems dealing for instance with transportation planning and management problems (Migdalas, 1995; Yin, 2002), medical engineering (Eichfelder, 2010) and optimal allocation of water resources (Ahmad et al. 2018). For more applications and details about bilevel programming problems, one can see for example (Bard, 2013; Dempe, 2002; Dempe et al. 2015; Shimizu et al. 2012; Floudas & Pardalos, 2009; Colson, 2007). In the bilevel programming framework, when the leader's problem contains the optimal value function of the follower's problem in its objective and/or constraint functions then it is called bilevel programming problem with extremal value function. Shimizu and Ishizuka (Shimizu & Ishizuka, 1985) studied bilevel programming problems with extremal value functions and derived necessary conditions by means of the directional derivatives. Aboussoror and Adly (2011) considered a bilevel nonlinear optimization problem with an extremal value function and obtained necessary and sufficient optimality conditions under constraint quali cations and via the Fenchel-Lagrange duality approach. Recently, Wang and Zhang (2015) have introduced and studied a bilevel multiobjective programming problem with an extremal value function. For obtaining the optimality conditions of the latter problem, the authors have extended the approach in Abiussoror & Adly, (2011) by applying the duality scheme described in (Bot et al. 2007) under a generalized Slater-type constraint qualification.
Fractional programming was investigated extensively in the literature due to its importance in modelling numerous problems with applications for example in economic, management science, information theory, stochastic programming, electric power system, etc (see Stancu-Minasian, 2012; Thibault, 1995 and the references therein). To the best of our knowledge, there is no paper integrates fractional programming with the class of bilevel programming problems with extremal value function. Therefore, the aim of this paper is to consider a bilevel programming problem more general than those in (Aboussoror & Adly, 2011; Wang & Zhang, 2015) which is a bilevel multiobjective fractional programming problem
where 
is the optimal value function of the following problem parametrized by x
Herein, A is a nonempty subset of Rm closed and convex, B is a nonempty
subset of R d compact and convex, Ks is a nonempty closed convex cone of Rs
and
Besides, by adopting an approach completely di erent to that in Aboussoror & Adly, 2011; Wang & Zhang, 2015, the optimality conditions characterizing (properly, weakly) e cient solutions of (BMFP) will be obtained without constraint quali cations and in terms of sequences in exact subdi erentials at some nearby points. More precisely, these optimality conditions will be established via sequential calculus rules for the Brøndsted-Rockafellar subdi erential of the sum and the multi-composition of convex functions. It is worth noting that these sequential calculus rules were initiated and developed by Thibault (1995, 1997) for the Brøndsted-Rockafellar subdi erential of the sum and the composition of two convex functions in order to overcome the drawbacks of constraint quali cations.
The paper is organized as follows. In Section 2, we present some basic de nitions, notations and results which will be used throughout the paper. In Section 3, we provide without constraint quali cations a sequential formula for the subdi erential of nite sums involving composed and multi- composed functions under convexity and lower semicontinuity hypotheses. In Section 4, we derive sequential optimality conditions for (properly, weakly) efficient solutions of the problem (BMFP) without constraint qualifications.
PRELIMINARIES
Symmetry in this section, we recall some basic de nitions and present some preliminary results which are needed in succeeding sections. We denote by 
the nonneg - ative orthant of R m the m-dimensional Euclidean space. For 
and 
in R m , the inner product of x and y is denoted by
while the norm of x is given by 
Further, we understand by 
that the sequence 
converges to 
For a nonempty subset 
by int (A) we will denote the topological interior of A. Let 
be a nonempty convex cone with 
then the dual cone of Km is given by 
On R m , we consider the partial order 
induced by the convex cone Km which is defined by
With respect to , the augmented set 
is considered where 
is an abstract element verifying the following operations and conventions:
and 
for all 
and all 
Let 
be a real valued function. Then f is called proper if its
effiective domain dom 
for all 
and it is called convex if 
for all 
and 
The function f is called lower semicontinuous if its epigraph epi
is a closed subset of 
Furthermore, the function 
is called Km-nondecreasing if for all 
The function 
defined by
is called the conjugate function off. We have the so-called Young-Fenchel inequality
The subdifferential of f at 
dom f is defined by
It is easy to prove that
Let A be a nonempty subset of Rm , then the indicator function 
One can prove that if 
is Ks-convex and 
nondecreasing on domg and 
is Kq-convex with
Let us consider the following multiobjective optimization problem
where A is a nonempty subset of 
is a propervector valued function and 
is partially ordered by 
The following definitions can be found in [19].
Definition 1. A point 
is said to be -efficient solution of (MOP) if there is no 
such that
and
- Weakly efficient sloution of (MOP) if there is no 
such that
- Properly efficient solution of (MOP) (in the sense of Geoffrion) if it is efficient and there exists 
such that for all 
and all 
satisfying 
there exists at least one 
such that 
and
Definition 2. A point 
is said to be
- weakly efficient solution of (MOP) in linear scalarization's sense if there exists
such that 
- properly efficient solution of (MOP) in linear scalarization's sense if there exists 
such that
Below, the following proposition resumes some relations between the above definitions.
Proposition 1. ([Bot et al. 2009; Proposition 2.4.18]) Let 
and assume that A is convex and 
is proper and 
convex. Then, 
is a weakly (properly) efficient solution of (MOP) if and only if is a weakly (properly) efficient solution of (MOP) in linear scalarization's sense.
SEQUENTIAL SUBDIFFERENTIAL CALCULUS INVOLVING COMPOSED and MULTI-COMPOSED FUNCTIONS
Let 
be two nonempty convex cones. The aim of this section is to derive without qualification assumptions a sequential formula for the subdifferential of the following function 
where
are proper, convex, lower semicontinuous, Kq-nondecreasing and
is proper, Ks-convex, Ks-epi closed and (Kq; Ks)- nondecreasing with 
is proper, convex, lower semicontinuous and Ks-nondecreasing with 
is proper, Kq-convex and Kq-epi closed with 
is proper, convex and lower semicontinuous,
Consider now the following functions
and
Remark 1. Let us note that the functions 
are proper, convex and lower semicontinuous.
In the sequel, we will need the following lemmas.
Lemma 1. let
if and only if
Proof 
We proceed by contradiction. So, let
and assume that
From (1), it follows that there exist 
This implies that
By taking in the account the monotonicity of 
it follows from (3) that
Hence, from (2) and (4) we get
which contradicts
Follows easily by contradiction too.
Lemma 2. Let
Proof (a)
It is easily to check that for any 
Thus
Since (x; y) epiφ and according to the Young-Fenchel inequality, (5) becomes
and hence the proof is complete.
For (b) and (c) we apply the same arguments as in (a).
Before stating the main result of this section, we recall an interesting result established by Laghdir et al. [20] in the setting of Banach spaces which provides a sequential formula for the subdifferential of the sums of proper, convex and lower semicontinuous functions, without constraint qualifications.
Theorem 1. (Laghdir et al, 2020; Theorem 3.2]) Let 
be a Banach space and 
its topological dual space paired in duality by 
where 
denotes the weak-star topology on 
be k proper, convex and lower semicontinuous functions. Assume that 
then 
if and only if there exist nets 
and
and
Here is the main result of this section.
Theorem 2. Let
and 
Then
if and only if there exist sequences 
satisfying
and
Proof. Let 
From Lemma 1, it is clear tha
if and only if 
According to Remark 1, one can see that the functions 
and
verify all the conditions of Theorem 1. Hence by applying Theorem 1, it follows that there exist sequences 
and
By Lemma 2, (6) is equivalent to
with
By (10), we have
and
Hence, the proof is complete since in (8) the sequences 
and
are superfluous.
SEQUENTIAL OPTIMALITY CONDITIONS FOR (BMFP)
In this section, we consider the following bilevel multiobjective fractional programming problem (the leader's problem)
Where 
and 
is the optimal value function of the following problem parametrized by x (the follower's problem)
Herein, A is a nonempty, closed and convex subset of R m , B is a nonempty, compact and convex subset of R d , Ks is a nonempty closed convex cone of 
is a convex function, 
are convex and 
-nondecreasing functions, 
and 
is a proper, 
convex, epi closed and 
nondecreasing function with 
Furthermore, we assume that 
We mention that the functions 
and 
are all continuous since
Moreover, one can see that the function 
is finite, convex, continuous and for each 
there exists 
such that 
Now, our aim is to derive sequential optimality conditions characterizing (properly, weakly) efficient solutions of the problem (BMFP). For this, we begin by formulating scalar convex optimization problems by using the parametric approach due to Dinkelbach [21]. So, for a given 
we consider below a multiobjective optimization problem (associated to (BMFP)) denoted by (Pn)
Remark 2. Let us note that by using Dinkelbach's transformation, the (weakly) efficient solutions of (BMFP) and (Pn) coincide. For the case of proper efficiency,one needs the following additional assumption
Proposition 2. Let 
and 
with 
Then 
is an efficient solution of (BMFP) if and only if is an optimal solution of the following scalar convex optimization problem
where 
proof 
Assume that is an efficient solution of (BMFP), then by Definition 1 one can see easily that there exist no 
such that 
For all 
for some 
Therefore, we have for all 
This implies that
On other hand, it is clear that
and
Hence, it follows that
and thus the right implication is proved.
For the reciprocal implication, we proceed by contradiction. Assume that is an optimal solution of the problem
if is not an efficient solution of (BMFP), then there exists 
A such that 
for all 
and 
for some
Thus, it follows that 
and
and this contradicts is an optimal solution of the problem (EPn).
Proposition 3. Let
Then is a weakly efficient solution of (BMFP) if and only if there exists 
such that is an optimal solution of the following scalar convex optimization problem
Proof. According to Remark 2, x is a weakly efficient solution of (BMFP) if and only if it is a weakly efficient solution of (Pn). Since A is convex and the functions
are convex, 
it follows by applying Proposition 1 that x is a weakly efficient solution of (Pn) in linear scalarization's sense. Hence the proof is complete.
Proposition 4. Let
Assume that there exist non-negative real numbers a and b such that 
for all 
and 
Then x is a properly efficient solution of (BMFP) if and only if there exists 
such that is an optimal solution of the following scalar convex optimization problem
Proof. It suffices to show that x is a properly efficient solution of (BMFP) if and only if x is a properly efficient solution of (Pn) and apply Proposition 1. So, Assume that x is a properly efficient solution of (BMFP), then by Definition 1 it follows that is efficient and there exists 
such that for all 
and all 
satisfying 
there exists one 
such that
and
Thus, is a properly efficient solution of (Pn). Similarly, we prove the reciprocal implication.
Now, let 
be a function defined by
It is clear that the function is proper, 
convex, 
epi closed and 
since the function 
is finite, convex and continuous. Furthermore, we have
Lemma 3. Let 
such that 
Then for any 
and 
it holds 
where
Proof. Let 
and 
It is clear that
From [12, Proposition 5.1], it results that
This completes the proof.
Now, we are able to state the main results of this section.
Theorem 3. Let
with 
and 
Then x is an efficient solution of (BMFP) if and only if there exist sequences
Satisfying
and
Proof. By Proposition 2, we have x 2 A is an efficient solution of (BMFP) if and only if it is an optimal solution of the scalar problem (εPn) and this is equivalent to
where the function 
is defined by
Obviously, the functions 
and and ' satisfy all ρ the assumptions of Theorem 2 (note that for the monotonicity of 
one can see [22]). Hence, there exist sequences 
Satisfying
and
To end up the proof, it remains to note that (11) is equivalent to
Theorem 4. Let
and 
with 
Then, x is a weakly efficient solution of (BMFP) if and only if there exist 
and sequences
satisfying
Proof According to Proposition 3, it is clear that x is a weakly efficient solution of (BMFP) if and only if there exist 
such that
Thus, by Theorem 2 it follows that there exist sequences 
satisfying
Hence, the proof is complete.
Now, by applying Proposition 5 and Theorem 2 we get the following result.
Theorem 5. Let
and 
with 
Assume that there exist non-negative real numbers a and b such that 
for all 
and all 
Then, x is a properly efficient solution of (BMFP) if and only if there exist 
and sequences 
Proof. We apply Proposition 5 and Theorem 2 and we follow the same reasonings as in the proof of Theorem 4.
Next, we close this section by providing an example illustrating sequential optimality conditions given in Theorem 3, Theorem 4 and Theorem 5 where for instance the Slater's constraint qualification fails. Let us recall that the set A is said to satisfy Slater's constraint qualification if there exists 
such that
Example 1. Let
Then, our bilevel multiobjective fractional programming problem that we consider can be formulated as follows
Where 
and min 
for all 
Clearly, f is convex, 
are convex and 
-nondecreasing, 
and h is proper, convex, lower semicontinuous and -nondecreasing. Moreover, one can see that 
for all and
It is a simple matter to check that x = 0 is a properly and weakly efficient solution of (BMFP) where A does not satisfy the Slater's constraint qualification.
Nevertheless, the sequential optimality conditions given in Theorem 4 and also Theorem 5 are satisfied. Take 
for all 
Thus, we can see easily that
For the sequential optimality conditions given in Theorem 3, it suffices to set
CONCLUSION
In this work, without assuming any quali cation condition, we have obtained sequential calculus rules for the subdi erential of nite sums involving composed and multi-composed functions under convexity and lower semicontinuity hypotheses, in terms of limits of subgradients at nearby points to the nominal point. Next, we have deduced sequential optimality conditions characterizing properly or weakly e cient solutions of a bilevel multiobjective fractional programming problem with an extremal value function. As nal conclusion, we think that several results of this work will be useful in order to improve the actual resolution techniques and develop new methods to solve multiobjective fractional mathematical programs.
REFERENCES
Ahmad, I., Zhang, F., Liu, J. (2018). Anjum, M.N., Zaman, M., Tayyab, M., Waseem, M., Farid, H.U.: A linear bi-level multi-objective program for optimal allocation of water resources. Plos one 13(2), 1-25.
Aboussoror, A., Adly, S. (2011) A Fenchel-Lagrange duality approach for a bilevel programming problem with extremal-value function. J. Optim. Theory Appl. 149(2), 254-268.
Bard, J.F. (2013). Practical Bilevel Optimization: Algorithms and Applications, vol. 30. Springer Science & Business Media.
Bot, R.I., Vargyas, E., Wanka, G. (2007) Conjugate duality for multiobjective composed optimization problems. Acta Math. Hungarica 116(3), 177-196.
Bot, R.I., Grad, S.M., Wanka, G. (2009). Duality in Vector Optimization. Springer Science & Business Media.
Colson, B., Marcotte, P., Savard, G. (2007). An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235-256.
Dempe, S. (2002). Foundations of Bilevel Programming. Springer Science & Business Media.
Dempe, S. (2015). Kalashnikov, V., Perez-Valdes, G.A., Kalashnykova, N.: Bilevel Programming Problems. Springer, Berlin, Heidelberg.
Eichfelder, G. (2010) Multiobjective bilevel optimization. Math. Program. 123(2), 419-449.
Floudas, C.A., (2009). Pardalos, P.M.: Encyclopedia of Optimization. Springer Science & Business Media.
Laghdir, M., Dali, I., Moustaid, M.B. (2020). A generalized sequential formula for subdi erential of multi-composed functions de ned on Banach spaces and applications. Pure Appl. Funct. Anal. 5(4), 999-1023.
Migdalas, A. (1995). Bilevel programming in traffic planning: Models, methods and challenge. J. Global Optim. 7(4), 38-405.
Stancu-Minasian, I.M. (2012). Fractional Programming: Theory, Methods and Applications, vol. 409. Springer Science & Business Media.
Stancu-Minasian, I.M., (2019) A ninth bibliography of fractional programming. Optimization 68(11), 2125-2169.
Shimizu, K., (2012), Ishizuka, Y., Bard, J.F.: Nondi erentiable and Two-level Mathematical Programming. Springer Science & Business Media.
Shimizu, K., Ishizuka, Y., (1985) Optimality conditions and algorithms for parameter design problems with two-level structure. IEEE Trans. Autom. Control 30(10), 986-993.
Thibault, L. (1995). A generalized sequential formula for subdi erentials of sums of convex functions de ned on Banach spaces. Lecture Notes Econom. Math. Syst.
Thibault, L. (1997). Sequential convex subdi erential calculus and sequential Lagrange multipliers. SIAM J. Control Optim.
Wang, H., Zhang, R. (2015). Duality for multiobjective bilevel programming roblems with extremal-value function. J. Math. Res. Appl. 35(3), 311-320.
Yin, Y. (2002). Multiobjective bilevel optimization for transportation planning and management problems. J. Adv. Transp. 36(1), 93-105.