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