Nội dung

Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) Đ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 Mathetical model of bilevel programmimg 1. Introduction problem ( P) in this paper is a sequence of two Bilevel programming is arising from actual needs such as: Problem of socio-economic optimization problems in which the feasible development planning for a territory or a region of upper-level problem ( P1 ) is country. Inside, the upper-level is the state that determined implicitly by the solutions set of the controls policies such as tariffs, exchange rate, lower-level problem ( P2 ) . It may be given as import quota… with the aim of creating more follows: jobs, minor resource usage… Lower-level are the companies with the goal of maximizing income  Min F ( x, y ) ( P1 ) :  with the constraints on superiors' policies. Or,   subject to : G( x, y)  0, y  S ( x); resource allocation problem at a firm or a Where, for each x  X , S ( x) is the company with management decentralization. Inside, the upper echelon plays a central role in solution set of the following parametric providing resources (capital, supplies and labor) optimization problem: aiming to maximize the company's profits.  Min f ( x, y)  Lower-level are factories producing products in where, ( P2 ) :  subject to : g ( x , y )  0,   different locations, decide the ratio, own production output to maximize the performance of their units. 10 Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) F  ( F1 ,..., Fm ) : f: n1  n2 n1  n2  m upper and lower convexificators of f at x . , Proposition 2.1 ([4]) Suppose that the function admits an upper f :X   , G  (G1 ,..., Gm2 ) : n1 and g  ( g1 ,..., gm1 ) :  n1 n2   n2 m2  m1 convexificator * f ( x ) at x  X . If f attains ; ni mi , i  1, 2 are integers, with ni  1, mi  0. Whenever m1  0 or m2  0, 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 f ( x  t )  f ( x) f d ( x; )  lim inf t 0 t f ( x  t )  f ( x)     resp., f d ( x; )  limsup . t t 0     In case f d ( x; )  f d ( 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 f :X  (lower) 2.2 ([4]) The function   is said to have an upper convexificator * f ( x) at * f ( x)  X * (* f ( x)  X * ) is x if weakly* closed, and for all   X , f ( x, )  sup  d x , * x** f ( x )  resp., f  ( x, )  inf x* ,    d x** f ( x )   A weakly* closed set * f ( x)  X * is said to have a convexificator of f at x if it is both 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 f  ( f1 , f 2 ,.... f n ) be a continuous p function from n function from n to to and g be continuous . Suppose that, for each i  1,..., n , fi admits a bounded convexificator * fi ( x ) and g admits a bounded convexifi-cator * g ( x ) at x . For each i  1,..., n if * fi ( x ) and * g ( x ) are upper semiconti-nuos at x then the set: * ( f g )( x )  * g ( f ( x ))(* f1 ( x ),..., * f n ( 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) S   x , y   n1  n2 where, : G( x, y)  0; y  S ( x). According to Stephane Dempe [3], ( P) can be replaced by ( P* ) : Min F ( x, y ), subject to: G( x, y)  0, g ( x, y)  0; f ( x, y)  V ( x)  0 với ( x, y)  n1  n2 . Luderer (1983) has proved that the problem ( P* ) has an optimal solutions, where V ( x)  min  f ( x, y) : g ( x, y)  0, y  y n2 . Assumption 3.1 Dempe [2] has proved that under the following hypotheses ( H1 ),( H 2 ),( H3 ), the problem ( P) has at lest one optimal solution. 11 Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) F (.,.), f (.,.), g (.,.) and G(.,.) are (H1): lower semicontinuos (l.s.c) on n1  n2 ; (H2): V (.,.) is upper semicontinuos (u.s.c) on n1 ; (H3): The problem ( P* ) has at least one feasible solution, there exists  *  c   such M  {(x, y )  as: n1  n2 : G ( x, y )  0, g ( x, y )  0, 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 (  , )  m1   m1  ; ( x, y) U ; x*g  co g ( x, y ); xG*  co G ( x, y ); x*f  co f ( x, y ); xV*  *V ( x)  {0};    X m   ,  ,   1 and k  1;     k  1  m2  m1   i gi ( x , y )  0 and   j G j ( x , y )  0; j 1  i 1 m  *  (0, 0)  cl{ k conv  Fk ( x , y )  k 1  m1   m 1[ conv * f k ( x , y )   i conv * g i ( x , y ) i 1   m2   j conv *G j ( x , y )   (*V ( x )  {0}]}, (1)  j 1 where,  *V ( x )  conv {* f (., y )( x ) : y  J ( x )}  n2 : g ( x , y)  0; f ( x , y)  V ( x )}.  J ( x )  {y  If in addition to the above assumptions, the problem (P) is regular at ( x , y ) one has k  0, k  1, m. Proof A ccording to Stephane Dempe [3], ( P) can be replaced by ( P* ) : such that  g ( x, y)  G( x, y)  ( x*g , xG* x*f  xV* ,  )  0. Min F ( x, y), subject to: Theorem 3.1 Let ( x , y ) is a solution of ( P) . G( x, y)  0, g ( x, y)  0; f ( x, y)  V ( x)  0 Suppose that, there exists a neigh-borhood U  X at ( x , y ) such that the functions with ( x, y)  F , f , g , G are continuous on U and admits Gong (2010, Theorem 3.1) to Problem ( P* ) bounded convexificators. yields the existence of a continuous positively * F ( x , y ); * f ( x , y ); * g ( x , y ); *G( x , y ) at ( x , y ) .  F;  f ; * n2 . homogeneous subadditive function  on satisfying m  m  ( y2 )  ( y1) and : ( F )( x, y)  0, ( x, y)  M  g;  G *  Applying the scalarization theorem by y2  y1  int Assume that: * n1 * Hence, ( x , y ) is a minimum of the are upper semicontinuos at ( x , y ) . Then, there exists scalars 1 , 2 ,..., m1   0 and vector    1 ,..., m   1   1 ,...,m   2 following scalars optimization Problem (MP): Min ( F )( x, y), subject to: m1  G( x, y)  0, g ( x, y)  0; f ( x, y)  V ( x)  0 ; m2  such that: with ( x, y)  n1  n2 . Luderer (1983) has proved that the problem (MP) has an optimal solutions, where V ( x)  min  f ( x, y) : g ( x, y)  0, y  y Taking account of Theorem 1 in 12 n2 . Bard Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) (1984) to the scalars problem (MP) yields the exists and vector  , 1 ,   0    1 ,..., m   1 m1    ;   1 ,...,m2  m2  such that zn  cl{  C (0)(* F ( x , y )1 ,..., * F ( x , y ) m ) m1 m2 1[ i conv  gi ( x , y )   j conv *G j ( x , y ) * i 1 j 1  conv  f ( x , y )   ( V ( x )  {0})]}, * * (4)    , ,    1 and   1  1  m1 m2   g ( x , y )  0 and  jG j ( x , y )  0   i i  i 1 j 1  * (0,0)  cl{ conv  (  F )( x , y )  m m  [ 1  conv * g ( x , y )  2  conv *G ( x , y )  i i j j  1 i 1 j 1  * * (2)   conv  f ( x , y )   ( V ( x )  {0})]} where, such that limn zn  0. By (4), there exists a *V ( x )  conv {* f (., y)( x ) : y  J ( x )}  n2 : g ( x , y )  0; f ( x , y )  V ( x )}.  J ( x )  {y  assume sequence { n }  C (0)  m such as zn  cl{  n (* F ( x , y )1 ,..., * F ( x , y ) m ) m1 m2 1[ i conv * gi ( x , y )   j conv *G j ( x , y ) i 1 j 1  conv  f ( x , y )   ( V ( x )  {0})]}, * * Since  C (0) is a compact set in that m (5) , we can n   C (0) . Putting    . one has   (1 ,..., m ).  m . It follows from (5), we have 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 F ( x , y )  0. Since function  is convex and locally Lipschitz, Proposition 7.3.9 trong Schirotzek (2007) was poined that: C ( F( x , y ) ( x , y ))  ( F( x , y ) ( x , y )). (0,0)  cl{ (* F ( x , y )1 ,..., * F ( x , y ) m ) m1 i 1 C ( F( x , y ) ( x , y ))(* F ( x , y )1 ,..., * F ( x , y )m ) is a convexificator of ( F )( x , y ) at ( x , y ).  conv  f ( x , y )   ( V ( x )  {0})]}, (0, 0)  cl{  C ( F( x , y ) ( x , y ))(* F ( x , y )1 ,..., m1 * F ( x , y ) m )  1[ i conv * gi ( x , y ) (6) virtue of (6), its holds that m (0, 0)  cl{ k conv * Fk ( x , y ) k 1 m1 m1[ i conv * gi ( x , y ) i 1   j conv *G j ( x , y )   conv * f ( x , y ) j 1  (*V ( x )  {0})]}, which implies (6). Let us see that i  m  \{0}(i  1,..., m) . Since   0, we just need to prove   i 1 m  \{0}. Indeed, for any it can be written 0  ( y)  int m2   j conv  G j ( x , y )   conv  f ( x , y ) * m . We have j 1 (3) Since F( x , y ) ( x , y )  0 , it follows from (3) that there exists a sequence * Sine   (1 ,..., m ), putting 1  m1 , by It follows from (2), we obtain  (*V ( x )  {0})]}. j 1 * m2 Moreover, due to Proposition 2.2, we have * m2 1[ i conv * gi ( x , y )   j conv *G j ( x , y )  ,  y   , F( x , y ) ( x , y )  y  F( x , y ) ( x , y )  ( F( x , y ) ( x , y )  y )  ( F( x , y ) ( x , y )  ( y )  P(0)  0. Consequently,   m  \{0}, and so, it can 13 Chuyên mục: Thông tin & Trao đổi - TẠP CHÍ KINH TẾ & QUẢN TRỊ KINH DOANH SỐ 10 (2019) m be assumed that   k  1 . Hence, k 1 m 1  k 1 k  1, 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 14 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