bileveloptimizationusingapproximations.zip资源-CSDN文库

共19个文件

m：14个

mat：3个

pdf：1个

版权申诉

5星 · 超过95%的资源 175 浏览量 2022-01-19 11:32:28 上传评论 8 收藏 1.03MB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

Evolutionary algorithm for bilevel optimization using approximations.zip （19个子文件）

Evolutionary algorithm for bilevel optimization using approximations.pdf 1.39MB

程序_基于二次近似（BLEAQ）的双层优化进化算法

llTestProblem.m 2KB

使用说明.doc 25KB

tp1_temp.mat 2KB

tp1_main_temp.mat 2KB

ulTestProblem.m 2KB

getMappings.m 4KB

tp1.m 1KB

calculateCrowdingDistance.m 1KB

getOptimalSolutionSMD.m 5KB

tp1_main.mat 1KB

llSearch.m 43KB

ulSearch.m 50KB

getLowerLevelVariableFromMapping.m 7KB

quadApprox.m 3KB

terminationCheck.m 6KB

doLocalSearch2.m 14KB

initialization.m 10KB

nonDominatedSorting.m 943B

European Journal of Operational Research 257 (2017) 395–411

Contents lists available at ScienceDirect

European Journal of Operational Research

journal homepage: www.elsevier.com/locate/ejor

Continuous Optimization

Evolutionary algorithm for bilevel optimization using approximations

of the lower level optimal solution mapping

Ankur Sinha

a , ∗

, Pekka Malo

, Kalyanmoy Deb

Production and Quantitative Methods, Indian Institute of Management Ahmedabad Vastrapur, Ahmedabad 380015, India

Department of Information and Service Economy, Aalto University School of Business, PO Box 21220, 0 0 076 Aalto, Helsinki, Finland

Department of Electrical and Computer Engineering, Michigan State University, East Lansing 48823, MI, USA

a r t i c l e i n f o

Article history:

Received 24 April 2015

Accepted 10 August 2016

Available online 17 August 2016

Keywords:

Bilevel optimization

Evolutionary algorithms

Quadratic approximations

a b s t r a c t

Bilevel optimization problems are a class of challenging optimization problems, which contain two levels

of optimization tasks. In these problems, the optimal solutions to the lower level problem become possi-

ble feasible candidates to the upper level problem. Such a requirement makes the optimization problem

diﬃcult to solve, and has kept the researchers busy towards devising methodologies, which can eﬃciently

handle the problem. Despite the effort s, there hardly exist s any effective methodology, which is capable

of handling a complex bilevel problem. In this paper, we introduce bilevel evolutionary algorithm based

on quadratic approximations (BLEAQ) of optimal lower level variables with respect to the upper level

variables. The approach is capable of handling bilevel problems with different kinds of complexities in

relatively smaller number of function evaluations. Ideas from classical optimization have been hybridized

with evolutionary methods to generate an eﬃcient optimization algorithm for a wide class of bilevel

problems. The performance of the algorithm has been evaluated on two sets of test problems. The ﬁrst

set is a recently proposed SMD test set, which contains problems with controllable complexities, and the

second set contains standard test problems collected from the literature. The proposed method has been

compared against three benchmarks, and the performance gain is observed to be signiﬁcant. The codes

related to the paper may be accessed from the website http://bilevel.org .

1. Introduction

Bilevel optimization is a branch of optimization, which con-

tains a nested optimization problem within the constraints of the

outer optimization problem. The outer optimization task is usually

referred to as the upper level optimization problem, and the in-

ner optimization task is referred to as the lower level optimiza-

tion problem. The lower level problem appears as a constraint,

such that only an optimal solution to the lower level optimization

problem is a possible feasible candidate to the upper level opti-

mization problem. Such a requirement makes bilevel optimization

problems diﬃcult to handle and have kept researchers and prac-

titioners busy alike. The hierarchical optimization structure may

introduce diﬃculties such as non-convexity and disconnectedness

even for simpler instances of bilevel optimization like bilevel lin-

ear programing problems. Bilevel linear programing is known to

be strongly NP-hard ( Hansen, Jaumard, & Savard, 1992 ), and it has

∗

Corresponding author.

E-mail addresses: asinha@iima.ac.in , ankur.sinha@gmail.com (A. Sinha), pekka.

malo@aalto.ﬁ (P. Malo), kdeb@egr.msu.edu (K. Deb).

been proven that merely evaluating a solution for optimality is also

a NP-hard task ( Vicente, Savard, & Judice, 1994 ). This gives us an

idea about the kind of challenges offered by bilevel problems with

complex (non-linear, non-convex, discontinuous etc.) objective and

constraint functions.

In the ﬁeld of classical optimization, a number of studies have

been conducted on bilevel programing ( Colson, Marcotte, & Savard,

2007; Dempe, Dutta, & Lohse, 2006; Vicente & Calamai, 2004 ). So-

lution techniques commonly employed to handle bilevel problems

often require simplifying assumptions like smoothness, linearity or

convexity. Some of the classical approaches used to handle bilevel

problems include the Karush–Kuhn–Tucker approach ( Bialas &

Karwan, 1984; Bianco, Caramia, & Giordani, 2009; Chen & Florian,

1992; Herskovits, Leontiev, Dias, & Santos, 20 0 0 ), Branch-and-

bound techniques ( Bard & Falk, 1982; Fortuny-Amat & McCarl,

1981 ), and the use of penalty functions ( Aiyoshi & Shimizu, 1981 ).

Most of these solution methodologies are rendered inapplicable,

as soon as the bilevel optimization problem becomes complex.

Heuristic procedures such as evolutionary algorithms have also

been developed for handling bilevel problems with higher levels

of complexity ( Wang, Wan, Wang, & Lv, 20 08; Yin, 20 0 0 ). Most

of the existing evolutionary procedures often involve enormous

http://dx.doi.org/10.1016/j.ejor.2016.08.027

396 A. Sinha et al. / European Journal of Operational Research 257 (2017) 395–411

computational expense, which limits their utility to solving bilevel

optimization problems with smaller number of variables.

There are a number of practical problems which are bilevel in

nature. They are often encountered in transportation (network de-

sign, optimal pricing) ( Brotcorne, Labbe, Marcotte, & Savard, 2001;

Constantin & Florian, 1995; Migdalas, 1995 ), economics (Stackel-

berg games, principal-agent problem, taxation, policy decisions)

( Cecchini, Ecker, Kupferschmid, & Leitch, 2013; Fudenberg & Ti-

role, 1993; Kovacevic & Pﬂug, 2013; Sinha, Malo, Frantsev, & Deb,

2013; 2014; Wang & Periaux, 2001 ), management (network facil-

ity location, coordination of multi-divisional ﬁrms) ( Bard, 1983;

Kkaydin, Aras, & Altnel, 2011; Sun, Gao, & Wu, 2008 ), engineer-

ing (optimal design, optimal chemical equilibria) ( Kirjner-Neto, Po-

lak, & Kiureghian, 1998; Smith & Missen, 1982 ) etc. Many of the

real-world bilevel optimization problems contain diﬃculties like,

non-linearity, discreteness, non-differentiability and non-convexity

for which the classical methods fail. Evolutionary methods are not

very useful either, because of their enormous computational ex-

pense. Under such a scenario, a hybrid strategy could be solution.

Acknowledging the drawbacks associated with the two approaches,

in this paper we propose a hybrid strategy that utilizes ideas from

classical bilevel programing into an evolutionary algorithm. Some

existing mathematical results have been discussed that serve as a

motivation in designing the evolutionary algorithm. The proposed

method is a bilevel evolutionary algorithm based on quadratic ap-

proximations (BLEAQ) of the lower level optimal variables as a

function of upper level variables. The algorithm proposed in this

paper is not targeted towards problems that can be solved by exact

methods, but for problems where the exact methods fail because

of aforementioned real-world diﬃculties. Most of the test problems

chosen in our study cannot be solved by classical bilevel program-

ing algorithms, and on the other hand, solving them using evolu-

tionary algorithms alone in a nested manner would prove to be

computationally very expensive. Computational studies have been

performed to justify our claims.

The remainder of the paper is organized as follows. In the next

section, we provide a review of the past work on bilevel optimiza-

tion using evolutionary algorithms, followed by description of a

general bilevel optimization problem. Thereafter, we provide a sup-

porting evidence that a strategy based on iterative quadratic ap-

proximations of the lower level optimal variables with respect to

the upper level variables could be used to converge towards the

bilevel optimal solution for a special class of problems. This is fol-

lowed by the description of the BLEAQ methodology that utilizes

the proposed quadratic approximation principle within the evo-

lutionary algorithm to solve more general problem. The proposed

ideas are further supported by results on a number of test prob-

lems. Firstly, BLEAQ is evaluated on recently proposed SMD test

problems ( Sinha, Malo, & Deb, 2012 ), where the method is shown

to successfully handle test problems with 10 decision variables. A

performance comparison is performed against a nested evolution-

ary strategy, and the eﬃciency gain is provided. Secondly, BLEAQ

is evaluated on a set of standard test problems chosen from the

literature ( Aiyoshi & Shimuzu, 1984; Amouzegar, 1999; Bard, 1998;

Liu, 1998; Oduguwa & Roy, 2002; Outrata, 1990; Shimizu & Aiyoshi,

1981; Wang, Li, & Dang, 2011 ). Most of the standard test problems

are constrained problems with relatively smaller number of vari-

ables. In order to evaluate the performance of BLEAQ, we choose

the algorithms proposed in Wang, Jiao, and Li (2005) , and Wang

et al. (2011) for comparison.

2. Past research on bilevel optimization using evolutionary

algorithms

Evolutionary algorithms for bilevel optimization have been

proposed as early as in the 1990s. One of the ﬁrst evolutionary

algorithm for handling bilevel optimization problems was pro-

posed by Mathieu, Pittard, and Anandalingam (1994) . The proposed

algorithm was a nested strategy, where the lower level was han-

dled using a linear programing method, and the upper level was

solved using a genetic algorithm (GA). Nested strategies are a pop-

ular approach to handle bilevel problems, where for every upper

level vector a lower level optimization task is executed. However,

they are computationally expensive and not feasible for large scale

bilevel problems. Another nested approach was proposed in Yin

(20 0 0) , where the lower level was handled using the Frank–Wolfe

algorithm (reduced gradient method). The algorithm was success-

ful in solving non-convex bilevel optimization problems, and the

authors claimed it to be better than the classical methods. In 2005,

Oduguwa and Roy (2002) proposed a co-evolutionary approach for

ﬁnding optimal solution for bilevel optimization problems. Their

approach utilizes two populations. The ﬁrst population handles

upper level vectors, and the second population handles lower

level vectors. The two populations interact with each other to

converge towards the optimal solution. An extension of this study

can be found in Legillon, Liefooghe, and Talbi (2012) , where the

authors solve a bilevel application problem with linear objectives

and constraints. Calvete, Gal, and Mateo (2008) proposed a genetic

algorithm for linear bilevel problems. The authors claimed that

their approach is also capable of handling quasi-concave bilevel

problems with a linear lower level objective function.

Wang et al. (2005) proposed an evolutionary algorithm based

on a constraint handling scheme, where they successfully solved

a number of standard test problems. Their approach ﬁnds better

solutions for a number of test problems, as compared to what is

reported in the literature. The algorithm is able to handle non-

differentiability at the upper level objective function; however,

the method is not able to handle non-differentiability in the con-

straints, or the lower level objective function. Later on, Wang et al.

(2011) provided another algorithm that was able to handle non-

differentiable upper level objective function and non-convex lower

level problem. Their new algorithm was shown to perform better

than the one proposed in Wang et al. (2005) . Given the robust-

ness of the two approaches ( Wang et al., 2005; Wang et al., 2011 )

in handling a variety of standard test problems, we choose these

methods as benchmarks. Another evolutionary algorithm proposed

in Li, Tian, and Min (2006) utilizes particle swarm optimization to

solve bilevel problems. Even this approach is nested as it solves

the lower level optimization problem for each upper level vector.

The authors show that the approach is able to handle a number

of standard test problems with smaller number of variables. How-

ever, they do not report the computational expense of the nested

procedure. A hybrid approach proposed in Li and Wang (2007) ,

which is also nested, utilizes simplex-based crossover strategy at

the upper level, and solves the lower level using one of the clas-

sical approaches. In Li and Wang (2007) , the authors report the

number of generations and population sizes required by the algo-

rithm that may be used to compute the function evaluations at

the upper level, but they do not explicitly report the total number

of function evaluations required at the lower level. Other studies

where authors have relied on a nested strategy include ( Angelo,

Krempser, & Barbosa, 2013; Sinha, Malo, Frantsev, & Deb, 2014 ). In

both of these studies an evolutionary algorithm has been used at

both levels to handle bilevel problems.

Researchers in the ﬁeld of evolutionary algorithms have also

tried to convert the bilevel optimization problem into a single level

optimization problem using the Karush–Kuhn–Tucker (KKT) condi-

tions ( Li & Wang, 2007; 2011; Wang et al., 2008 ). However, such

conversions are possible only for those bilevel problems, where

the lower level is smooth and the KKT conditions can be eas-

ily produced. Recently, there has also been an interest in multi-

objective bilevel optimization using evolutionary algorithms. Some

A. Sinha et al. / European Journal of Operational Research 257 (2017) 395–411 397

of the studies in the direction of solving multi-objective bilevel

optimization problems using evolutionary algorithms are ( Deb &

Sinha, 2010; Halter & Mostaghim, 2006; Ruuska & Miettinen, 2012;

Sinha & Deb, 2009; Sinha, Malo, Deb, Korhonen, & Wallenius, 2016;

Xia, 2001; Zhang, Hu, Zheng, & Guo, 2012 ).

3. Bilevel optimization problem

Bilevel optimization is a nested optimization problem that in-

volves two levels of optimization tasks. The structure of a bilevel

optimization problem demands that the optimal solutions to the

lower level optimization problem may only be considered as feasi-

ble candidates for the upper level optimization problem. The prob-

lem contains two classes of variables: the upper level variables

x ∈ X ⊂ R

, and the lower level variables y ∈ Y ⊂ R

. For the lower

level problem, the optimization task is performed with respect to

variables y , and the variables x act as parameters. A different x

leads to a different lower level optimization problem, whose opti-

mal solution needs to be determined. In the following we provide

two equivalent deﬁnitions of a bilevel optimization problem:

Deﬁnition 1. At the upper-level the objective function and con-

straints are deﬁned by F : R

× R

→ R and at the lower-level the

objective function and constraints are deﬁned by f : R

× R

→ R

as follows:

minimize

x ∈ X,y ∈ Y

(x, y )

subject to y ∈ argmin

{ f

(x, y ) : f

(x, y ) ≤ 0 , j = 1 , . . . , J}

(x, y ) ≤ 0 , k = 1 , . . . , K

The above deﬁnition can be stated in terms of set-valued map-

pings as follows:

Deﬁnition 2. Let  : R

⇒ R

be a set-valued mapping,

(x ) = argmin

{ f

(x, y ) : f

(x, y ) ≤ 0 , j = 1 , . . . , J} ,

which represents the constraint deﬁned by the lower-level opti-

mization problem, i.e. ( x ) ⊂Y for every x ∈ X . Then the bilevel

optimization problem can be expressed as a general constrained

optimization problem:

minimize

x ∈ X,y ∈ Y

(x, y )

subject to y ∈ (x )

(x, y ) ≤ 0 , k = 1 , . . . , K

where ( x ) can be interpreted as a rational reaction set ( Bard,

1998 ) of the follower for a given x .

The graph of the feasible-decision mapping, which is commonly

referred as inducible region ( Bard, 1998 ) in the context of bilevel

optimization, is interpreted as a subset of X × Y

gph  = { (x, y ) ∈ X ×Y | y ∈ (x ) } ,

which displays the connections between the upper-level decisions

and corresponding optimal lower-level decisions. The domain of ,

which is obtained as a projection of gph  on the upper-level deci-

sion space X represents all the points x ∈ X , where the lower-level

problem has at least one optimal solution, i.e.

dom  = { x | (x )  = ∅} .

Similarly, the range is given by

rge  = { y | y ∈ (x ) for some x } ,

which corresponds to the projection of gph  on the lower-level

decision space Y . In the case of multiple optimal solutions at the

Fig. 1. Graphical representation of a simple bilevel optimization problem. The mid-

dle ﬁgure shows the lower level function with respect to upper and lower level

variables. The bottom ﬁgure shows the

-mapping for x and optimal y . The top

most ﬁgure shows the upper level function with respect to upper level variables

and optimal lower level variables.

lower level, there is an ambiguity as to which solution is the fol-

lower going to choose. To overcome this, one often assumes an

optimistic position, i.e. the follower cooperates with the leader by

choosing a solution y ∈ ( x ) that is the best from the perspec-

tive of the leader. The formulation considered in this paper is also

optimistic.

Fig. 1 provides a graphical representation of a simple bilevel

optimization problem. The middle ﬁgure provides the relationship

of the lower level function ( f

) with respect to the upper ( x ) and

lower ( y ) level variables. The surface of the lower level function

has been sliced with three planes at x

(1)

, x

∗

and x

(2)

. It is clear that

for x

(1)

there are multiple lower level optimal solutions, while for

∗

and x

(2)

the lower level optimal solutions are unique. The bot-

tom ﬁgure describes the structure of a bilevel problem in terms

of gph , which is the mapping between optimal lower level vari-

ables and corresponding upper level variables, or in other words

398 A. Sinha et al. / European Journal of Operational Research 257 (2017) 395–411

it is the graph of the lower level decision-mapping  as a subset

of X × Y . The shaded area in the bottom ﬁgure denotes that the

region has multiple lower level optimal solutions corresponding to

any upper level vector. On the other hand, the non-shaded parts

of the graph represent the regions where there is a single lower

level optimal vector corresponding to any upper level vector. The

top most ﬁgure shows the upper level objective function with re-

spect to upper level vector x , when the lower level is optimal, y ∈

( x ). Since gph  is the domain of F

, we have interpreted F

en-

tirely as a function of x , i.e. F

( x , ( x )). Therefore, whenever  is

multi-valued, we see a corresponding shaded region in the plot of

as well. The minimum of F

( x , ( x )) corresponds to x

∗

, which

becomes the bilevel optimal solution.

Example 3. To provide a further insight into bilevel optimization,

we consider a simple example with non-differentiable objective

functions at upper and lower levels. The problem has a single up-

per and lower level variable, and does not contain any constraints

at either of the two levels.

minimize

x,y

(x, y ) = | x | + y −1

subject to

y ∈ argmin

{ f

(x, y ) = (x )

+ | y − e

For a given upper level variable x , the optimum of the lower

level problem in the above example is given by y = e

. Therefore,

this problem has a single-valued  mapping, such that (x ) =

{ e

} . The  mapping reduces this problem to a simple single-

level optimization problem as a function of x . The optimal so-

lution to the bilevel optimization problem is given by (x



, y



) =

(0 , 1) . In this example, the lower level optimization problem is

non-differentiable at the optimum for any given x , and the up-

per level objective function is non-differentiable at the bilevel opti-

mum. Even though the problem involves simple objective functions

at both levels, most of the KKT-based methods will face diﬃcul-

ties in handling such a problem. It is noteworthy that even though

the objective functions at both levels are non-differentiable, the

-mapping is continuous and smooth. For complex examples hav-

ing disconnected or non-differentiable -mapping one can refer to

Dempe (2002) .

4. Localization of the lower level problem

Ideally, the analysis of a bilevel problem would be greatly sim-

pliﬁed if the optimal solution mapping  could be treated as if it

were an ordinary function. In particular, for the design of an ef-

ﬁcient bilevel algorithm, it would be valuable to identify the cir-

cumstances under which single-valued functions can be used to

construct local approximations for the optimal solution mapping.

Given that our study of solution mappings is closely related to

sensitivity analysis in parametric optimization, there already exists

considerable research on the regularity properties of solution map-

pings, and especially on the conditions for obtaining single-valued

localizations of general set-valued mappings. To formalize the no-

tions of localization and single-valuedness in the context of set-

valued mappings, we have adopted the following deﬁnition from

Dontchev and Rockafellar (2009) :

Deﬁnition 4 (Localization and single-valuedness) . For a given set-

valued mapping  : X ⇒ Y and a pair (x, y ) ∈ gph , a graphical

localization of  at x for y is a set-valued mapping 

loc

such

that

gph 

loc

= (U × L ) ∩ gph 

for some upper-level neighborhood U of x and lower-level neigh-

borhood L of y , i.e.

Fig. 2. Localization around x

(0)

for y

(0)



loc

(x ) =



(x ) ∩ L for x ∈ U,

∅ otherwise.

If 

loc

is actually a function with domain U , it is indicated by re-

ferring to a single-valued localization ψ

loc

: U → Y around x for y .

Obviously, graphical localizations of the above type can be de-

ﬁned for any lower level decision mapping. However, it is more

interesting to ask when is the localization not only a single-valued

function but also possesses convenient properties such as conti-

nuity and certain degree of smoothness. In this section, our plan

is to study how the lower-level solution mappings behave under

small perturbations, and clarify the regularity conditions in which

the solution mapping can be locally characterized by a Lipschitz-

continuous single-valued function. We begin the discussion from

simple problems with convex set-constraints in Section 4.1 and

gradually extend the results to problems with general non-linear

constraints in Section 4.2 .

As an example, Fig. 2 shows the  mapping and its localization

loc

around x

(0)

for y

(0)

. The notations discussed in the previous

deﬁnition are shown in the ﬁgure to develop a graphical insight

for the theory discussed above.

4.1. Localization with convex constraints

To motivate the development, suppose that the lower level

problem is of the form

minimize f

(x, y ) overall y ∈ C , (1)

where lower-level variables are restricted by a simple set-

constraint C which is assumed to be non-empty, convex, and

closed in Y .

When the lower-level objective function f

is continuously dif-

ferentiable, the necessary condition for y to be a local minimum

for the lower level problem is given by the standard variational

inequality

∇

(x, y ) + N

(y )  0 , (2)

where

(y ) = { v | v , y



− y  ≤ 0 , for all y



∈ C} (3)

is the normal cone to C at y and ∇

denotes the gradient of f

with respect to the lower-level decision vector. The solutions to the

inequality are referred to as stationary points with respect to min-

imizing over C , regardless of whether or not they correspond to

local or global minimum. Of course, in the special case when f

is also convex, the inequality yields a suﬃcient condition for y to

A. Sinha et al. / European Journal of Operational Research 257 (2017) 395–411 399

be a global minimum, but in other cases the condition is not suﬃ-

cient to guarantee lower-level optimality of y . Rather the inequality

is better interpreted as a tool for identifying quasi-solutions, which

can be augmented with additional criteria to ensure optimality. In

particular, as discussed by Dontchev and Rockafellar (2009) , signif-

icant effort s have been done to develop tools that help to under-

stand the behavior of solutions under small perturbations which

we are planning to utilize while proposing our solution for solving

the bilevel problem. With this purpose in mind, we introduce the

following deﬁnition of a quasi-solution mapping for the lower level

problem:

Deﬁnition 5 (Quasi-solution mapping) . The solution candidates

(stationary points) to the lower level problem of form (1) can be

identiﬁed by set-valued mapping 



: X ⇒ Y,





(x ) = { y |∇

(x, y ) + N

(y )  0 } ,

which represents the set of stationary lower-level decisions for the

given upper-level decision x . When f

is convex, 



coincides to

the optimal solution mapping, i.e. 



= .

Whereas direct localization of  is diﬃcult, it is easier to obtain

a well-behaved localization for the quasi-solution mapping ﬁrst,

and then establish the conditions under which the obtained solu-

tions furnish a lower-level local minimum. The approach is moti-

vated by the fact that for variational inequalities of the above type,

there are several variants of implicit function theorem that can be

readily applied to obtain localizations with desired properties. Be-

low, we present a simple localization-theorem under the additional

assumption that C is polyhedral, which is suﬃcient to guarantee

that for all points in the neighborhood of x



there is a strong local

minimum in the lower level problem (1) . A convexity assumption

is required to guarantee global optimum.

Deﬁnition 6 (Lipschitz) . A single-valued localization ψ

loc

: X → Y

is said to be Lipschitz continuous around an upper-level decision

when there exists a neighborhood U of

and a constant γ ≥ 0

such that

| ψ

loc

(x ) − ψ

loc



) | ≤ γ | x − x



| for all x, x



∈ U .

Theorem 7 (Localization with polyhedral constraints) . Suppose in

the lower-level optimization problem (1) , with y



∈ 



( x



), that

(i) C is a polyhedral convex set in Y , i.e. it can be expressed as

an intersection of ﬁnitely many closed half-spaces, C = { y ∈

Y |  b

, y  ≤ α

for i = 1 , . . . , m } , and

(ii) f

is twice continuously differentiable with respect to y , such

that

 w, ∇



, y



) w  > 0 for all non-zero w ∈ K −K,

where

K = { w | w ⊥ ∇



, y



) and  b

, w  ≤ 0 for i ∈ I(y



) }

is the critical cone for the constraint set C , and I ( y



) denotes

the set of indices of the constraints that are active at y



. The

notation K − K denotes the set of difference of two objects be-

longing to K.

Then the quasi-solution mapping 



has a Lipschitz continuous

single-valued localization ψ around x



for y



. Furthermore, for all x

in some neighborhood of x



, there is a strong local minimum at y =

ψ (x ) , i.e. for some ε > 0

(x, y



) ≥ f

(x, y ) +

| y



− y |

for all y



∈ C near y .

Proof. The result follows from Theorems 2G.2 and 2G.3 in

Dontchev and Rockafellar (2009) and the deﬁnition of the criti-

cal cone for polyhedral sets, K = { w ∈ T



) | w ⊥ ∇



, y



) } ,

where T

( y



) denotes the tangent cone for the polyhedral set

C at y



. The above form for the critical cone in (ii) is obtained by

noting that in the case of polyhedral convex sets the tangent cone

can be expressed as T



) = { w |  b

, w  ≤ 0 for i ∈ I(y



) } , where

I(y



) = { i |  b

, y



 = α

} . 

4.2. Localization with nonlinear constraints

Until now, we have considered the simple class of lower level

problems where the constraint set is not allowed to depend on the

upper-level decisions. In practice, however, the lower level con-

straints are often dictated by the upper level choices. Therefore,

the above discussion needs to be extended to cover the case of

general non-linear constraints that are allowed to be functions of

both y and x . Fortunately, this can be done by drawing upon the

results available for constrained parametric optimization problems.

Consider the lower level problem of the form

minimize

y ∈ Y

(x, y )

subject to f

(x, y ) ≤ 0 , j = 1 , . . . , J

where the functions f

, f

, . . . , f

are assumed to be twice contin-

uously differentiable. Let

L (x, y, z) = f

(x, y ) + z

(x, y ) + ···+ z

(x, y )

denote the Lagrangian function. Then the necessary ﬁrst-order op-

timality condition is given by the following generalized equation

f (x, y, z) + N

(y, z)  (0 , 0) ,

where

⎧

⎨

⎩

f (x, y, z) = (∇

L (x, y, z) , −∇

L (x, y, z)) ,

E = Y × R

(y, z) = { v |



v , (y



, z



) − (y, z)



≤ 0 , for all (y



, z



) ∈ E}

The pairs ( y , z ) which solve the above problem are called the

Karush–Kuhn–Tucker pairs corresponding to the upper-level deci-

sion x . Now in the similar fashion as done in Section 4.1 , our in-

terest is to establish the conditions for the existence of a mapping

loc

which can be used to capture the behavior of the y compo-

nent of the Karush–Kuhn–Tucker pairs as a function of the upper-

level decisions x .

Theorem 8 (Localization with nonlinear constraints) . For a given

upper-level decision x



, let ( y



, z



) denote a corresponding Karush–

Kuhn–Tucker

pair. Suppose that the above problem for twice contin-

uously differentiable functions f

is such that the following regularity

conditions hold

(i) the gradients ∇

( x , y ), i ∈ I are linearly independent,

(ii) the lower level problem is convex with respect to the lower level

variable y , and

(iii)  w, ∇

L (x



, y



, z



) w  > 0 for ev ery w  = 0 , w ∈ M

where



I = { i ∈ [1 , J] | f



, y



) = 0 , z



> 0 } ,

= { w ∈ R

| w ⊥ ∇



, y



) for all i ∈ I } .

Then the Karush–Kuhn–Tucker mapping S : X ⇒ Y × R

S (x ) := { (y, z) | f (x, y, z) + N

(y, z)  (0 , 0) } ,

has a Lipschitz-continuous single-valued localization s around x



for

( y



, z



s (x ) = (ψ

loc

(x ) , z(x )) ,

where ψ

loc

: X → Y and z : X → R

. Moreover, for every x in some

neighborhood of x



the lower-level decision component y = ψ

loc

(x )

gives a strong local minimum.

评论收藏

内容反馈

版权申诉

快点叫我嘎嘣脆

2022-04-30

用户下载后在一定时间内未进行评价，系统默认好评。
qq_2608694283

2022-06-18

用户下载后在一定时间内未进行评价，系统默认好评。
weixin_40852661

2022-04-30

用户下载后在一定时间内未进行评价，系统默认好评。
weixin_40110114

2022-06-25

用户下载后在一定时间内未进行评价，系统默认好评。
qunimabidashabi

2022-11-22

超级好的资源，很值得参考学习，对我启发很大，支持！

前往

页

电磁MATLAB

粉丝: 4079
资源: 36

bilevel optimization using approximations.zip

基于双层优化算法求解多目标优化文题附matlab代码Bilevel Optimization Algorithm.zip

和大家分享一个求解bilevel问题的算法本人已试过-bilevel算法.rar

BilevelOptimization.jl：基于JuMP的工具箱，用于解决双层优化问题

Practical Bilevel Optimization

bigM-master.zip_Big!_Bilevel_big m_bigm

GA-for-Bilevel-Programming.rar_bilevel programming_双层_双层模型_双层规划源

Bilevel-approach-for-optimal.zip_分布发电_分布式_分布式发电_双层 规划_定价 位置

利用电价和天然气市场的灵活性：基于价格的方法.zip

双层优化算法_matlabBilevel Optimization Algorithm

bilevel:双层分区 D3 Vis

A Stochastic Bilevel Model for the Energy Hub Manager Problem

A new solution algorithm for solving rule-sets based bilevel decision problems

双层优化算法：双层优化算法-matlab开发

A note on the definition of linear bilevel programming solution

Equivalent Bilevel Programming Form for the Generalized Nash Equilibrium Problem

A Bilevel Programming Reformulation for a Single-leg Flight Capacity Control Problem

Improved Electromagnetism-like Algorithm for Nonlinear Bilevel Programming Problem

信赖域最优化的改进算法

带有离网目标的互素数组中DOA估计的Bilevel-JointOMP

python大作业 含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar

仿真电路以及操作方法

【纯干货啊】华为IPD流程管理(完整版).pptx

可编程语言标准IEC61131-3中文版.pdf

OFDM完整仿真过程与教程.zip

信号与系统——保研复习资料.pdf

Landsat_WRS2.zip

最全的Visio形状/图形库

AxureRP9项目原型50套、案例20个、元件库1套.zip

北理工+成电+东南——通信/信号保研面试真题.pdf

最新资源

Bilevel-approach-for-optimal.zip_分布发电_分布式_分布式发电_双层规划_定价位置

python大作业含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar