Điều kiện cần tối ưu cho bài toán tối ưu hai cấp

Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) 
10 
ĐIỀU KIỆN CẦN TỐI ƯU CHO BÀI TOÁN TỐI ƯU HAI CẤP 
Trần Thị Mai1, Phạm Thị Linh2 
Tóm tắt 
Bài toán tối ưu hai cấp đang hấp dẫn các nhà khoa học nghiên cứu do ý nghĩa khoa học và tính ứng 
dụng rộng rãi của bài toán trong thực tế. Tối ưu hai cấp xuất hiện trên sách báo, tạp chí thường có liên 
quan đến các hệ thống phân cấp. Bài toán tối ưu hai cấp bao gồm hai bài toán tối ưu, trong đó một 
phần dữ liệu của bài toán thứ nhất được xác định ẩn thông qua nghiệm của bài toán thứ hai. Người ra 
quyết định ở mỗi cấp cố gắng tối ưu hóa (cực tiểu hay cực đại) hàm mục tiêu riêng của cấp mình mà 
không để ý tới mục tiêu của cấp kia, nhưng quyết định của mỗi cấp lại ảnh hưởng tới giá trị mục tiêu 
của cả hai cấp và tới không gian quyết định nói chung. Mô hình toán học của bài toán tối ưu hai cấp 
cùng với công cụ dưới vi phân suy rộng dùng để thiết lập điều kiện tối ưu cho bài toán được chúng tôi 
trình bày trong bài báo này. 
Từ khóa: Bài toán, bài toán hai cấp, dưới vi phân suy rộng, nghiệm, tối ưu. 
NECESSARY CONDITIONS FOR BILEVEL OPTIMIZATION PROBLEM 
 Abstract 
Bilevel optimzation is attracting scientists due to its scientific significance and wide applicability in 
practice. The bilevel programming in books and magazines is often related to hierarchies. The bilevel 
optimzation includes two optimal problems, in which a part of the data of the first problem is identified 
through the solution of the second problem. The decision maker at each level tries to optimize 
(minimum or maximum) the function of his own level without paying attention to the goal of the other 
level but the decision of each level affects the target value of both levels and the decision space in 
general. The math model of bilevel optimzation along with the convexificator tool used to establish 
optimal conditions for the problem is presented in this paper. 
Keywords: Problem, bilevel programming, convexificator, solution, optimization. 
JEL classification: C; C02
1. Introduction 
 Bilevel programming is arising from 
actual needs such as: Problem of socio-economic 
development planning for a territory or a 
country. Inside, the upper-level is the state that 
controls policies such as tariffs, exchange rate, 
import quota with the aim of creating more 
jobs, minor resource usage Lower-level are the 
companies with the goal of maximizing income 
with the constraints on superiors' policies. Or, 
resource allocation problem at a firm or a 
company with management decentralization. 
Inside, the upper echelon plays a central role in 
providing resources (capital, supplies and labor) 
aiming to maximize the company's profits. 
Lower-level are factories producing products in 
different locations, decide the ratio, own 
production output to maximize the performance 
of their units. 
Mathetical model of bilevel programmimg 
problem ( )P in this paper is a sequence of two 
optimization problems in which the feasible 
region of upper-level problem 1( )P is 
determined implicitly by the solutions set of the 
lower-level problem 2( )P . It may be given as 
follows: 
1
Min ( , )
( ) :
subject to : ( , ) 0, ( );
F x y
P
G x y y S x
Where, for each , ( )x X S x is the 
solution set of the following parametric 
optimization problem: 
2
Min ( , )
( ) :
subject to : ( , ) 0,
f x y
P
g x y
where, 
Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) 
11 
1 2
1 2
1 2 2
2
1
1
( ,..., ) : ,
: ,
( ,..., ) :
n n m
m
n n
n n m
m
F F F
f
G G G
and 1 2 1
11
( ,..., ) : ;
n n m
m ig g g n 
, 1,2im i are integers, with 1, 0.i in m 
Whenever 1 0m or 2 0,m this means that 
the corresponding inequality constraint is absen 
in the ( )P . 
Within the scope of the article, we using 
convexificator for establishing necessary 
condition with optimal solution to the ( )P in 
finite dimensional space. 
2. Preliminaries 
Let X be a Banach space, *X topological 
dual of X , x X . We recall some notions on 
convexificators in [4]. 
Definition 2.1 [4] The lower (upper) Dini 
directional derivatives of :f X  
at x X in a direction X is defined as 
0
( ) ( )
( ; ) liminfd
t
f x t f x
f x
t

 

0
( ) ( )
resp., ( ; ) limsup .d
t
f x t f x
f x
t

 

In case ( ; ) ( ; )d df x f x 
 their common 
value is defined by 
'( ; )f x  which is called Dini 
derivative of f in the direction  . The function 
f is called Dini differentiable at x its Dini 
derivative at x exists in all diretions. 
Definition 2.2 ([4]) The function 
 :f X  is said to have an upper 
(lower) convexificator 
* ( )f x at x if 
* * *
*( ) ( ( ) )f x X f x X    is weakly* 
closed, and for all ,X 
* *
*
( )
( , ) sup ,d
x f x
f x x  
 
*
*
*
( )
resp., ( , ) inf ,d
x f x
f x x  
 
A weakly* closed set 
* *( )f x X  is said 
to have a convexificator of f at x if it is both 
upper and lower convexificators of f at x . 
Proposition 2.1 ([4]) Suppose that the 
function :f X admits an upper 
convexificator 
* ( )f x at x X . If f attains 
its minimum at x then: *0 clconv ( )f x  
where cl and conv indicate the weakl* closure 
and convex hull, respectively. 
Proposition 2.2 ([4]) Suppose that the 
function 1 2( , ,.... )nf f f f be a continuous 
function from 
p
 to 
n
and g be continuous 
function from
n
 to . Suppose that, for each 
1,..., , ii n f admits a bounded convexificator 
* ( )if x and g admits a bounded convexifi-cator 
* ( )g x at .x For each 1,...,i n if * ( )if x
and 
* ( )g x are upper semiconti-nuos at x then 
the set: 
* * * *
1( )( ) ( ( ))( ( ),..., ( ))nf g x g f x f x f x   
is a convexificator of f g at .x 
 We shall begin with establishing necessary 
optimality condition for optimal solutions of 
bilevel programming problem. 
3. Optimality condition 
A pair ( , )x y is said to be optimal solution 
to the ( )P if it is an optimal solution to the 
following problem: 
( , )
Min ( , )
x y S
F x y
 where, 
 1 2, : ( , ) 0; ( ) .n nS x y G x y y S x 
According to Stephane Dempe [3], ( )P can be 
replaced by 
*( )P : Min ( , ),F x y 
subject to: 
( , ) 0, ( , ) 0; ( , ) ( ) 0G x y g x y f x y V x 
với 1 2( , )
n n
x y . 
Luderer (1983) has proved that the problem 
*( )P has an optimal solutions, where 
 2( ) min ( , ) : ( , ) 0, .n
y
V x f x y g x y y 
Assumption 3.1 Dempe [2] has proved that 
under the following hypotheses 
1 2 3( ),( ), ( ),H H H the problem ( )P has at lest 
one optimal solution. 
Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) 
12 
(H1): (.,.), (.,.), (.,.)F f g and (.,.)G are 
lower semicontinuos (l.s.c) on 1 2
n n ; 
(H2): (.,.)V is upper semicontinuos (u.s.c) on 
1n ; 
(H3): The problem 
*( )P has at least one 
feasible solution, there exists 
* c such 
as: 
1 2{( , ) : ( , ) 0,
( , ) 0, ( , ) }
n n
M x y G x y
g x y F x y c
is not empty and bounded. 
Definition 3.1 [1] The problem ( )P is said 
to be regular at ( , )x y if there exists a 
neighborhood U of ( , )x y and , 0  such 
that 
1 1
* *
( , ) ; ( , ) ;
co ( , ); co ( , );
m m
g G
x y U
x g x y x G x y
    
  
* * *co ( , ); ( ) {0};f V
X
x f x y x V x
 
   
 
 such that 
* * * *( , ) ( , ) ( , , ) 0.g G f Vg x y G x y x x x x   
Theorem 3.1 Let ( , )x y is a solution of ( )P . 
Suppose that, there exists a neigh-borhood 
U X at ( , )x y such that the functions 
, , ,F f g G are continuous on U and admits 
bounded convexificators. 
* * * *( , ); ( , ); ( , ); ( , )F x y f x y g x y G x y   
at ( , )x y . 
 Assume that: 
* *; ;F f  
* *;g G  
are upper semicontinuos at ( , )x y . 
Then, there exists scalars 1 2 1, ,..., m   
0 and vector 
 1
11
,..., ;mm   
21
,..., m   
2m
 such that: 
1 2
1
2
1
1 1
*
1
* *
1
1
* *
1
, , 1 1;
( , ) 0 ( , ) 0;
(0,0) { ( , )
[ ( , ) ( , )
( , ) ( ( ) {0}]}, (1)
m
k
k
m m
i i j j
i j
m
k k
k
m
m k i i
i
m
j j
j
and
g x y and G x y
cl conv F x y
conv f x y conv g x y
conv G x y V x
   
 

  
 
  
  
   

 



where, 
2
* *( ) { (., )( ) : ( )}
( ) { : ( , ) 0; ( , ) ( )}.
n
V x conv f y x y J x
J x y g x y f x y V x
   
If in addition to the above assumptions, the 
problem (P) is regular at ( , )x y one has 
0,k 1, .k m 
Proof 
A ccording to Stephane Dempe [3], ( )P 
can be replaced by 
*( )P : Min ( , ),F x y 
subject to: 
( , ) 0, ( , ) 0; ( , ) ( ) 0G x y g x y f x y V x 
with 1 2( , )
n n
x y . 
 Applying the scalarization theorem by 
Gong (2010, Theorem 3.1) to Problem 
*( )P 
yields the existence of a continuous positively 
homogeneous subadditive function  on m
satisfying 
2 1 2 1)int ( ) (
my y y y   
and : ( )( , ) 0, ( , )F x y x y M  
Hence, ( , )x y is a minimum of the 
following scalars optimization Problem (MP): 
Min ( )( , ),F x y 
 subject to: 
( , ) 0, ( , ) 0; ( , ) ( ) 0G x y g x y f x y V x 
with 1 2( , )
n n
x y . 
Luderer (1983) has proved that the problem 
(MP) has an optimal solutions, where 
 2( ) min ( , ) : ( , ) 0, .n
y
V x f x y g x y y 
 Taking account of Theorem 1 in Bard 
Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) 
13 
(1984) to the scalars problem (MP) yields the 
exists 1, , 0   and vector 
 1
11
,..., ;mm   221,...,
m
m   
such that 
1 2
1 2
1
1 1
*
* *
1
1 1
* *
, , 1 and 1
( , ) 0 and ( , ) 0
(0,0) { conv ( )( , )
[ conv ( , ) conv ( , )
conv ( , ) ( ( ) {0})]} (2)
m m
i i j j
i j
m m
i i j j
i j
g x y G x y
cl F x y
g x y G x y
f x y V x
    
 

  
 
   
  
   
 
 
where, 
2
* *( ) conv { (., )( ) : ( )}
( ) { : ( , ) 0; ( , ) ( )}.
n
V x f y x y J x
J x y g x y f x y V x
   
We now check hypotheses of a chain rule 
by Jeyakumar-Luc ([4], Prop 5.1) to the 
composite function ( )( , )F x y . Since the 
function  is continuous convex, we can apply 
Proposition 2.2.6 trong Clarke (1983) to deduce 
that it is locally Lipschitz.Hence, its 
subdifferential ( ( , ))C F x y  is abounded 
convexificator of  at ( , ) 0.F x y Since 
function  is convex and locally Lipschitz, 
Proposition 7.3.9 trong Schirotzek (2007) was 
poined that: 
( , ) ( , )( ( , )) ( ( , )).C x y x yF x y F x y   
Moreover, due to Proposition 2.2, we have 
* *
( , ) 1( ( , ))( ( , ) ,..., ( , ) )C x y mF x y F x y F x y   
is a convexificator of ( )( , )F x y at ( , ).x y 
It follows from (2), we obtain 
1
2
*
( , ) 1
* *
1
1
* *
1
*
(0,0) cl{ ( ( , ))( ( , ) ,...,
( , ) ) [ conv ( , )
conv ( , ) conv ( , )
( ( ) {0})]}. (3)
C x y
m
m i i
i
m
j j
j
F x y F x y
F x y g x y
G x y f x y
V x

 
 

   
 
  
  


Since ( , ) ( , ) 0x yF x y , it follows from (3) that 
there exists a sequence 
1 2
* *
1
* *
1
1 1
* *
cl{ (0)( ( , ) ,..., ( , ) )
[ conv ( , ) conv ( , )
conv ( , ) ( ( ) {0})]}, (4)
n C m
m m
i i j j
i j
z F x y F x y
g x y G x y
f x y V x

  
 
    
  
   
 
such that lim 0.n nz By (4), there exists a 
sequence { } (0) mn C     such as 
1 2
* *
1
* *
1
1 1
* *
cl{ ( ( , ) ,..., ( , ) )
[ conv ( , ) conv ( , )
conv ( , ) ( ( ) {0})]}, (5)
n n m
m m
i i j j
i j
z F x y F x y
g x y G x y
f x y V x
 
  
 
  
  
   
 
 Since (0)C  is a compact set in 
m
, we can 
assume that (0)n C    . Putting 
.   one has 1( ,..., ).m   .
m It 
follows from (5), we have 
1 2
* *
1
* *
1
1 1
* *
(0,0) cl{ ( ( , ) ,..., ( , ) )
[ conv ( , ) conv ( , )
conv ( , ) ( ( ) {0})]}, (6)
m
m m
i i j j
i j
F x y F x y
g x y G x y
f x y V x

  
 
  
  
   
 
Sine 1( ,..., ),m   putting 1 1m  , by 
virtue of (6), its holds that 
1
2
*
1
*
1
1
* *
1
*
(0,0) cl{ conv ( , )
[ conv ( , )
conv ( , ) conv ( , )
( ( ) {0})]},
m
k k
k
m
m i i
i
m
j j
j
F x y
g x y
G x y f x y
V x

 
 

 
 
  
  



which implies (6). 
Let us see that 
\{0}( 1,..., )mi i m  . Since 0, we 
just need to prove \{0}.m Indeed, for 
any it can be written 0 ( ) int my . We 
have 
( , ) ( , )
( , ) ( , )
, , ( , ) ( , )
( ( , ) ) ( ( , )
( ) (0) 0.
x y x y
x y x y
y F x y y F x y
F x y y F x y
y P
  
  
  
Consequently, \{0},m and so, it can 
Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) 
14 
be assumed that 
1
1
m
k
k

  . Hence, 
1
1
1,
m
k
k

  
which completes the proof. 
4. Conclusions 
In reference [2], the author applies bilevel 
programming problem with the function 
considered is scalar function in . 
In our article, the optimal condition of the 
problem is established for function vector in 
m
. This is a new result, have scientific 
meaning and tools to prove the problem is 
convexificator, currently many scientists are 
interested. 
TÀI LIỆU THAM KHẢO 
[1]. Amahroq, T. and Gadhi, N. (2001). On the regularity condition for vector programming problems. 
Journal of global optimization, 21, 435 - 443. 
[2]. Babahadda, H and Gadhi, N. (2006). Necessary optimality conditions for bilevel optimization 
problems using convexificators. Journal of Global Optimization, 34, 535 - 549. 
[3]. Dempe, S. (1997). First- order necessary optimality conditions for general bilevel programming 
problems. Journal of optimization theory and applications, 95, 735 - 739. 
[4]. Jeyakumar, V., Luc, D. T. (1999). Nonsmooth calculus, minimality and monotonicity of 
convexificators. J. Optim. Theory Appl. 101, 599 - 612. 
Thông tin tác giả: 
1. Trần Thị Mai 
- Đơn vị công tác: Trường ĐH Kinh tế & QTKD 
- Địa chỉ email: tranthimai879@gmail.com 
2. Phạm Thị Linh 
- Đơn vị công tác: Trường ĐH Kinh tế & QTKD 
Ngày nhận bài: 19/8/2019 
Ngày nhận bản sửa: 28/8/2019 
Ngày duyệt đăng: 25/09/2019