L
CIC14 Ri=oRT Co~LEGTION . ()/5
Los Alamos National Laboratory IS operated
A
REP]cTION cow
by the University of California for the United States Department of Energy under contract W7405 ENG.36.
.... . . . — 
. .
.!
...
.,,<.. ..—. . . ,..—  .. . . .. . . .——.._
. —..... . 
,.7
!.. ..
.,
. . .,.  ..— . . . ....— .. ..’. . .
.
A Review of the Literature .— —.on Bi=Level Mathematical Programming
,.
‘m—.
‘.:: ..
.
.

;Z+.

.m, Tr,.!’.).,.,....,=.. . . .. . .
.m ... —.
.
. 
.
.
.

.. ——.. .
7su=T——
—  .. ....——.—.
.
4 ... . .
. .
:.,
=(V
—,. . .... ..—.. .—.
~ ~.m ~~? =.::=: ——=
.,.
 :. .
———
:0
,.
.,
.. . .....  <,..  . . . . . . Ku,”, ~.: ‘,’ .IP’.’
.r.
,
. L—
.. .....
LosALalmos
mm
LosAlamos NationalLaboratory LosAlamos,New Mexico 87545
An Affirmative
Action/Equal
Opportunity
Employer
DISCLAIMER This repoti was prepared as an account of work sponsored by an agency of[he United !3a!es Government. Nei!her the United S[alcs Govcrnmcn[ or usefulness ofany information, by iradc name. trademark, cndorsemen!. Government nor any agency thereof, noranyoftheiremployecs, makes any warranty. express or implied. or assumes any legal liability or responsibility for the accuracy, completeness, product. process, or service imply its or any agency thereof. The
apparatus. product. or process disclosed. or represents that its use would or otherwise. does not necessarily conslituieor
not infringe privately owned rights. Reference herein to any specific commercial manufacmrer, recommendation. or favoring by the Uniwd States Government
views and opinions ofau[ hors expressed herein do not necessarily slate or reflect those of the Uniled Slates or any agency thereof.
LA10284MS UC32 Issued: October 1985
A Review of the Literature on BiLevel Mathematical Programming
Charles D.Kolstad*
J
““””’
L.
“Consultant LosAlamos. niversityf Illinois UrbanaChampaign, at U o at Urbana,L61801. I x, ., 
Page I. II. INTRODUCTION. .
q
.
.
q
q
.
.
.
.
.
. . . . . .
q
q
q
. . . . . . . .
q q
q
q
.
q
1 2 8 8 9 10 11 11 12 12 13 15 15 16 17 18
APPLICATIONSOF BILEVEL PROGRAMMING . . . . . .
q
III. ALGORITHMICDEVELOPMENTS . . . . A.
. . . . . . . . . . . . . . . .
q q
. . . . . . . . . . . . . .
q q
Extreme Point Search . . . . . . . . 1. CandlerTownsley. . . . . . . . 2. Kth Best Algorithm . . . . . . 3. Papavassilopoulos . . . . . . . B. KuhnTuckerKarush Methods . . . . . 1. Bard and Falk . . . . . . . . . 2. FortunyAmatand McCarl . . . . 3. ParametricComplementaryPivot c. Descent Methods . . . . . . . . . Penalty/BarrierFunction Methods ;: Direct Gradient Methods . . . . 3. Optimal Value Functions
q q
q
. . . . . . . . . . .
q
. . . . . . . . . . . . .
q q q q
q I
q q
q q
q q q q
q q
q q
REFERENCES . . . . . . .
q
. . . . . . .
.
q
q
iv
A REVIEW OF THE LITERATUREON BILEVE.L MATHEMATICALPROGRAMMING by Charles D. Kolstad ABSTRACT This paper reviews the recent literatureon applications and algorithms in bilevel programming. Bilevel programming involves tio mathematicalprograms. One math program is concerned with minimizing w(x,t) over some region by varying the vector t. The variable x is actually a function x(t) and is defined implicitlyas the solution vector to the second math program, which minimizes s(x,t) over some region by varying x. The review is divided into two main sections. One section covers applied problems that have been presented in the literatureas bilevel math programs. Most such applications are in economics but some are in warfare planning. Another section of the paper concerns the many diverse algorithms that have been developed to solve the biIevel programmingproblem.
I.
INTRODUCTION Over the past decade there has been an increase in interest in multiprogramming, and in particular bilevel mathematical
level mathematical
programming. The bilevel problem consists of two parts, an upper and lower part. Define the upperlevelproblem (denoted henceforthas “Pi”) as (Pi:) min w(x,t) t (la)
(lb) where x(t) is implicitlydefined by the lowerlevelproblem: (Bl:) x(t): min s(x,t) x 39(xst) : o (lC)
,
(id)
where all variables and constraint functions may be vectors. bilevel math programs.
A tremendous
variety of applied problems, particularlyeconomic problems, can be viewed as A Stackelberg duopoly or leaderfollowercontinuous game (Chen and Cruz, 1972; Cruz, 1978; Papavassilopoulos, 1981) can be viewed as bilevel programming problems with the follower’sproblem correspondingto B1 and the leader’s problem correspondingto P1. Many applicationsare in economic planning where the planner’s problem is P1 and the economy responds according to B1. Related to this is the principal agent problem where the principal (Pl ) tries to induce his agent (Bl) to act in the principal’sinterest. Outside the economics literature,the maxmin problem (Danskin,1966) is that of maximizing the minimum of some function and is thus a special case of bilevel programming. Unfortunately,good solution methods for the bilevel problem are not generally available. for a global optimum. The purpose of this paper is to provide a review of recent progress on bilevel programming (through 1982). The review covers both applicationsand algorithms. There has been a fair amount of work in both these areas with many algorithms springing from the need to solve specific applied problems. In the next section we review applications,some of which have appeared explicitly in the literature and others of which have only been suggested. This is followed bya section on algorithmic developments in multilevel programming. Most Soviet and Eastern European literature is not reviewed here (however, see Findeisen, 1982).
In fact,
without significant restrictionson the sub
problem, the overall problem may well be nonconvex and thus difficult to solve
II.
APPLICATIONS BILEVEL OF PROGRAMMING In this section we provide a fairly comprehensive review of past
applications of bilevel mathematicalprogramming. The purpose of this section is to demonstrate the wide applicabilityof bilevel programming and thus its importanceas a problem in mathematicalprogramming. Unfortunately,because of the variety of disciplines in which applications occur, we have undoubtedly omitted some importantwork from our review. The bulk of applicationsof bilevel programming that have appeared in the literature is in the economics realm, particularly central economic planning. The typical situation is that there is a planner with some social objective and a set of policy instruments to use for controllingone (or more) economic agents with different objectives. 2
In the context of the previously defined bilevel problem, the “policy problem” (PI) is given by Eqn. (lab),where the planner minimizes w(x,t) subject to the constraintsof Eqn. (lb). instrument. The planner can only effect his objective and, following Given a by adjusting the vector t, which may be a set of taxes, quotas, or some other The subordinate problem is given by Eqn. (lcd) Candler and Townsley (1982), is termed the “behavioral”problem (Bl).
vector of policies, t, the subordinateagent must optimize his objective s(x,t) by adjusting the vector x. Obviously,whatever x is chosen in the subordinate problem influences the planner’s objective. It is important to realize the distinctionbet~een the bilevel problem and the common decomposition of large planning problems into multilevel problems (e.g., Dantzig and Wolfe, 1961; Kornai and Liptak, 1965; Geoffrion, 1970). These methods are all concernedwith breaking down a large math program into a number of smaller, more tractable units. An important aspect of these methods is a coincidence between the objectives of the multiple levels and the objective of the overall problem. The fact that the decomposed problem can be written as a single convex programmingproblem distinguishesdecompositionfrom the general problem considered here.
In the economics literature the subordinateproblem (Bl) often serves a
very specific purpose, i.e., that of a simulator of a market economy. It has been known for some time that the operation of a portion of a competitive economy can be simulated using mathematical programming (Samuelson, 1952; Takayama and Judge, 1971). In short, in.a market for a single good, if there are i = 1,..., I consumerseach consuming qi and j = 1,..., J producers each producing ~j, then a market equilibrium can be associated with the solution .
max
A
~s~ i=l o
I A X Jqi
‘i‘X)dx 
JX Jqj
j=l ~ ‘j(x)dx
(2a)
1.
3 x
J.
(2b)
q.  z qj < 0 i=l 1 j=l — (2C) (2d)
3
where Pi(x) is the inverse demand function for consumer i and Sj(x) is the supply or marginal cost function for producer j. This suggests that very often the subordinate problem (Bl)
in bilevel
math programs is a single math program
The
simulating the decentralizedmarket processes of a competitive economy.*
effect of a perunit tax on such an economy can be simulatedby subtractinga term for tax payments from Eqn. (2a). A quota system applied in an economically efficient manner can be simulated by adding appropriate constraintsto Eqn. (2).** It is within this framework that most economic applicationsof bilevel mathematical programming occur: an overall social objective (the planning problem) subject to equilibriumin a market economy (the behavioral problem) with communication between the two levels through taxes, quotas, or some other set of policy instruments.
In spirit, the bilevel problem has a long history in economics  social
objectives vs objectives of individual economic agents. identify the earliest treatment of bilevel problems. It is difficult to Stackelberg’s(1952)
leaderfollowerduopoly model is fundamentallya bilevel problem. The leader’s problem is P1 and the follower’sproblem is B1. Marschak (1953) considers the problem of governmentalcontrol of a monopolistwith zero marginal costs facing linear demand for a single good. The policy problem is that of the governmnt choosing a perunit tax on the monopolist’s output in order to optimize a governmental objective. Two objectivesare considered. One is simply to maximize tax revenue. The other is to maximize output subject to a lower limit on tax revenue. The earliest explicit discussionin the economics literatureof bilevel math programming appears to be Candler and Norton (1977a). They consider a numerical example of a milkproducingmonopoly in the Netherlands,regulated by the government.
x
The
behavioral problem represents the objectives of
the
The formulation of Eqn. (2) can obviously be nnde more complicated. The most common extension is to introducemultiple products and the notion of space where products are distinguished. ** A quota is a restrictionon overall output from a particular sector of the economy. Within an optimizationmodel of a competitiveeconomy, it would be represented as a constrainton aggregate output. In practice, the quota would have to be translated to the firm level through a license system or some other mechanism. For an aggregate constraint to realisticallyrepresent the action of a quota, the licenses must be allocated to firms in an economicallyefficient manner. This can be assured by allowing private trading of licenses among firms. 4
monopoly that seeks to maximize revenue from sales of milk, butter, and cheeses. The Dutch governmnt controls a milk subsidy and duties on imported butter. The governrmt is assumed to have a composite objective consisting of consumer prices, governmentoutlay (the less, the better), and farm income (the more, the better). Other applicationsof bilevel programminghave been suggestedby Candler et al. (1981), principal in the area of development planning. IY They suggest that the market problem be a model of a sector of a developingeconomy (such as the agricultural sector), simulatingthe competitive interactions of economic agents in that sector in response to a number of governmentalpolicies such as price supports or controls, taxes, subsidies,or productionquotas. The policy problem can involve a variety of objectives includingemployment generation, economic growth, nutrition, or simply output. A specific problem examined by Candler et al. (1981) is that of irrigationpolicy. The behavioralmodel is of an agriculturalregion served by a single irrigation system. The behavioral Farmers model simulates the decisions of farmers as to how much water to use when subject to policies imposed by administratorsof the irrigation system. are assumed to maximize profit given local prices. Policies consideredare (a) system water allocations to be distributedefficientlyamong the farmers and (b) a cotton production quota. Two objectivesare considered: (a) maximizationof valueaddedtax at internationalprices (as opposed to local prices) and (b) maximization of employment. programming. Candler and Norton (1977b) have utilized a previously developed largescale model of Mexican agriculture as the behavioral subproblem. For policy objectives, they examine employment, farm income, corn and wheat production (all to be maximized),and governnmtal expenses (to be minimized). Policy variables used to influence the subprobleminclude subsidies on fertilizeruse, subsidies on irrigation investment loans, support prices on wheat and corn, and water taxes. The contributionof this work is not only in their realistic policy application but also in their computational experience. Although they came up with improved policies through bilevel optimization, they did discover some nonconvexitiesin their overall problem which made it difficult for them to find a global optimum (for som objectives). This has turned out to be a significant problem in bilevel programming. Although the data used in their analyses were hypothetical,the example illustratesa major area of application of bilevel
5
FortunyAmatand McCarl (1981) consider the problem of a fertilizer supplier who monopolizes a specific region. Farmers in that region have an inelastic demand but can buy from distant sellers. Thus, the behavioralproblem is that of the farmers’ decision process. The behavioralproblem is complicated by five variationson the basic productfertilizer. These variations have to do with whether or not fertilizerapplicationequipment is loaned with the fertilizer and whether or not prices are FOB the fertilizerplant or delivered to the farm. The policy problem is that of the monopolistwho must decide how much to charge for his product and product variations in order to maximize monopoly rent subject to constraintson availabilityof capital and labor. Another set of problems in the area of environmental regulation has motivated this author and apparently Wayne Bialas to research the question of bilevel programming. The problem is to drive polluters to efficient levels of emissions through an emissions tax. The same tax (per unit of emissions)applies to many different sources of pollution in a region even though each source contributes in a different way to concentrationsof pollution in the environment, due to locational differences and transport environment. of pollutants by the Thus the subproblem (Bl) simulates the market’s response to a tax
or set of taxes. The policy problem (PI) seeks to minimize real social costs while meeting pollution concentrationstandards (constraints). This problem was encounteredby Bialas for the case of water pollution and Kolstad (1982) for air pollution. A very different problem was explored by Falk and McCormick (1982’ that : of a cooperative game. The problem is that of an imperfect cartel of several countries in ,theinternationalcoal market. Since in an imperfect cartel, sidepayments are not permitted, cartel objectives may not be to maximize joint profits. Falk and McCormick utilize Nash’s solution to this bargainingproblem. th If Ui is the i cartel member’s gain from joining the cartel (relativeto his profit in a noncooperativesetting), then the Nash solution is to maximize ~ui, the product of the Ui’s. problem B1. Falk and McCormick formulate this as a bil~vel
problem, utilizing a very simple competitive model of coal trade as the subThe upperlevelproblem (PI) is Nash’s product of individualgains from cartelization,IIu.o Using a nunwical example with a twomember cartel, il Falk and McCormick demonstrate that two relative maxima exist for the overall problem, only one of which is a global maximum. Kolstad and Lasdon (1985) have examined a similar problem in the sam market. 6
De Silva (1978) has examined the regulation of the oil industry in the United States. The problem is to choose optimal price ceilings for oil discovered before and after a base point in time. The subproblem (Bl) is that of a profitmaximizing oil company faced with price ceilings. The policy problem (PI) is that of the federal government choosing price ceilings in order to mxi mize a composite objective, including the value of oil discoveredand produced during the planning period. Cassidy et al. (1971) analyze the problem of bilevel planning where states (of the US) develop an optimal set of public works projects using money from the federal government. The subproblem (Bl) is that of a state deciding on a set of projects which maximize a linear welfare function. The policy problem
(Pl ) is that of allocating
resources to each state to optimize a Federal objec
tive couched in terms of the equity of the resource allocation. There has been a variety of other research concernedwith topics closely related to bilevel programming. In the early 1970s a series of articles appeared concerningprograms involving the optimal value function of a secondary math program (Brackenand McGill, 1973a, b, 1974a, b; Bracken et al., 1977). All of the applications cited in these papers are in the area of warfare, principally the optimal structureand location of strategic nuclear forces
If the problem is couched as a twoperson Stackelberg game, the subordinate problem (Bl) concerns one’s opponent’s
submarines, bombers, and missiles. objective (i.e., reducing one’s warmaking capability and causing other damage) while the upperlevelproblem (Pi) concerns one’s own objective (damage to your opponent). For their example of bomber basing, your opponent’s goal is to use its submarines to destroy as many of your bombers as possible (problem Bl). Your problem is to determine a leastcostbomber location pattern which assures that a given number of bombers survive. Applications in the area of dynamic Stickelberg games are more remotely related to bilevel programming. Luh et al. (1982) propose constantly varying timeofdaypricing for electric power. They propose the customer as the subordinate agent responding to prices and influenced by a variety of stochastic variables such as the weather. The upperleveldecisionmakeris the electric power producer who chooses a price at an instant in time so as to clear the market in a leastcostmanner. The large literature on maxmin problems is not considered here (see e.9., Danskin, 1966). As will become apparent in the next section, the maxmin problem is a special case of a bilevel math program.
7
III .
ALGORITHMIC DEVELOPMENTS Most of the applications reviewed in the previous section are accompanied
by algorithms for solving the particularproblem considered. At leasta dozen different algorithms appear in the literature,most of which will be discussed in this section. There are three classes into which most algorithms fall. One class of algorithms is concernedexclusivelywith the linear bilevel problem. These algorithms are concernedwith efficientlymoving from one extreme point to another until an optimum is found. Another set of algorithms utilizes the KuhnTuckerKarush program. conditions of the subproblem as constraints on the overall problem, thus turning the bilevel problem into a nonconvex single mathematical A third set of algorithms is based on various descent approaches for the policy problem with gradient informationfrom the subproblem acquired in a variety of ways. A. Extreme Point Search. All of these methods are concernedwith purely linear bilevel problems. All of the algorithms discussed in this section ignore constraintson the upperlevel problem PI). Consequently,we can write the upperlevelproblem as (P3:) min c+t + Cwx (3a)
(3b) and the subproblem, implicitlydefining x (t), as (B3:) min dxx x (3C)
3 AXX ~ b  Att
X>() — ,
(3d) (3e) zed in most of these
A basic result of Bialas and Karwan (1982) is uti algorithms:
Theorem 1 (Bialasand Karwan): Any solution to problem P3B3 occurs at an extreme point of the constraintset of problem B3. The various algorithmsare concernedwith efficient searches of these extreme points. 8 Three algorithms have been discussed in the 1 terature. The
algorithm due to Candler and Townsley (1982) is the most widely discussed, principally because of the large number of papers on bilevel programmingof which Candler is a coauthor. Other algorithms of this type are due to Bialas and I(arwan(1982) and Papavassilopoulos(1982). 1. CandlerTownsley. The CandlerTownsleyalgorithm is described in some depth in Candler and Townsley (1982) and with more brevity in Bard and Falk (1982). The algorithm focuses on the relationshipbetween P3B3 and the following LP:
(P4:)
~in ctt + c~; X,t
(4a)
3
B ~ ~ b  Att
(4b) (4C)
;>0 t>() .
(4d)
In P4, B is an “optimal”basis from Ax; i.e., B satisfies optimality conditions for B3 (nonnegativereduced costs). In P4, the vector x has been restricted to
~, corresponding to the columns of Ax in B. feasible for P3). Note that with B so defined, any solution of P4 is feasible for P3B3 (i.e., an optimal solution of B3 that is The algorithm thus involves moving from one such “optimal” basis B to another, solving P4 each time. If one ensures that the objective of P4 improves, and thus there is no cycling, then the following theorem assures that P3B3 will eventually be solved. Theorem 2 (Candlerand Townsley): If there exists an optimal solution to P3B3 (t*,x*), then there exists a basis B* of AX with nonnegativereduced costs with respect to B3 such that (t*,x*,B*)solves P4. Thus their algorithm focuses on searching the bases of Ax until a solution of P3B3 is found. We describe the process intuitivelysince the details of the search process are quite elaborate. Given a feasible solution to P3B3 (tfl,R) and a corresponding“optimal”basis Bg, solve P4. The nonbasic columns x of A)(which have negative reduced costs (with respect to the objective function of P4) are candidates for pivoting into a new basis; denote the set of these columns by TR. Candler and Townsley prove that any basis B2+I which improves They further define a the optimal value of P4 (and thus moves closer to an optimum of P3B3) must contain an element of each of the Tk, k = 1 ***.S t.
9
supplemental set of nonbasic columns of Ax so that one is guaranteedto find a basis which is feasible for P4. Thus, one sequentiallychanges B in P4 and then solves P4 until a solution to P3B3 is found. 2. Kth Best Algorithm. Bialas and Karwan (1982) take a slightly different approach focusing on the relationshipbetween P3B3 and P5: (P5:) min ctt+ Cxx t,x (5a)
3 Ax
x + Att < b .
(5b) (5C)
t,x > 0
Theorem 1 above indicates that a solution of P3B3 will occur at an extreme point of the constraint set of P5. The “Kth best” algorithm is an efficient way of searching these extreme points. Suppose that the entire set of M extreme points of the constraint set of P5 is enumerated in ascending order of objective function value [(il,;l ), (t2,i2 ),...,(tM,2M)]; iq .,
Ct?i + Cx$ ~ C~2i+~ +
A
Cxxi+l “
We know one of the extreme points will solve P3B3.
The algorithm
moves sequentiallythrough these ordered extreme points until one is found which is an optimal solution to B3. One seeks the index K* where
K* .
min[is(l,o.o,)l(~i,~i) solves B4] M
.
(6)
Obviously the first of the sequence of extreme ~oi~ts canAbe f~und by solving P5 directly. The mechanism for moving from (ti,xi) to (ti+~Sxi+l) ‘s straightforward. Define Ti = {(~,~k)l k ~ i}. DefineAWi = {(t,X) I<(t,~)CTi~s such that (t,x) is an adjacent extreme point to (t,x)}. Let Vi =Wi~T~,
where T; is the complement of Ti . In other words, Wi is the set of extreme & points adjacent to one of the previouslyexamined extreme points. The set Vi is that set less the previouslyexamined extreme points. It is easy to see that
A .
X,t minates when (ti, xi) solves B3. Since this algorithm approaches the optimal
AA
(t 1+1 ,xi+~ ) is the solution to min[cxx + cttl (x,t)di].
The algorithm ter
*
At an optimal solution, adjacent extrem points are obtained by pivoting into the basis each of the nonbasic variables.
10
solution from a region of infeasibi 1ity, the solution wi11 be a global solution even if P3B3 is not convex. 3. Papavassi 1opoul 0s.
In a recent paper, Papavassilopoulos(1982) presents
several algorithms for solving the linear bilevel program. Unfortunatelyit is not clear whether any computationalexperiencewith these algorithms exists. We focus on the first of his algorithms. As in the previous algorithmsa sequence of extreme points is generated, . . each of which will be feasible* for P3B3. For each extreme point (ti,xi)$the next extreme point of the sequence is chosen by examining all extreme points ad... A A jacent to (ti,xi). An adjacent extreme point is chosen, (ti+l,xi+l),which (a) strictly reduces the objective of P3 while (b) maintaining optimality of B3. Since this algorithm approaches the solution from a region of feasibility, global optimality is not assured. B. KuhnTuckerKarush Methods. A number of algorithms involve transforming the behavioral problem B1 into KuhnTuckerKarush necessary conditions for optimalityand then rewriting P1B1 as
(P7:)
min w(x,t) x,t,v 3f(x,t) :0 Vxs(x,t) + ll”vxg(x,t) o =
(7a)
(7b) (7C) (7d) (7e) (7f)
M“g(x,t) = o
g(x,t) < 0
Problem P7 is of course equivalent to P1B1 since any solution
to P7 will
satisfy Eqns. (7cf) and thus solve B1 (providing s is strictly quasiconvex with respect to x and g is quasiconvexwith respect to x). The difficulty is that the constraint set of P7 is not convex, principally because of Eqn. (7d).
%
For (t,x) to be feasible for P3B3, (t,x) must solve B3 while t~O.
17
Thus most conventionaldescent algorithms cannot be applied to P7. Also, if the subproblemB1 is large, then the number of constraintsand variables associated with the KuhnTuckerKarush conditionswill be large. Thus these techniquesdo not seem wellsuited to problems involving large subproblems. The three algorithms presented below solve P7 in differentways. All algorithms consider * the case of linear KuhnTuckerKarush conditionsfor the subproblem. 1. Bard and Falk. Bard and Falk (1982) consider the linear version of P7 for which the only problematicconstraintis Eqn. (7d). The core of their algorithm is to rewrite P7 as a separable convex program; i.e., for xc Rn, all functions can be written as
f(x) =
: fj(xj) j=l
.
Introducingthe variables A (equal in dimension to g), constraint (7d) is equivalent to Z[min(O,Ai)+ vi] = O i Ai +gi +lli =(), I/i (8a)
(8b) (8c)
Ai>o,v. —
1
.
Although Eqn. (8a) is not a nice smooth function, it does have the separability characteristicwhich Bard and Falk need to apply an existing algorithm for separable nonconvex programs. The algorithm uses a branchandboundtechnique and involves a partition of the feasible region. Computationaltests applied to small problems have produced good results although computationsincrease rapidly with the size of the constraintregion. Thus, the techniquemay be time consuming when applied to problems involvinglarge subproblems. 2. FortunyAmatand McCarl. As did Bard and Falk, FortunyAmat and McCarl (1981) focus on the complementaryslackness condition,Eqn. (7d). They examine ‘Bard (1983) has recently proposed an algorithm for solving the general problem P7. His method involves a grid search between estimated upper and lower bounds on w(x,t) in Eqn. 7a.
12
the case where P1 and Blare each quadratic programs. *
If we assume
that each
objective function is convex, then if constraint Eqr10 (id)
is ignored, problem
P7 is a convex program which can be easily solved. Introducing the variable ~ (with the same dimension as g) such that each ni is either O or 1, P7 can be transformedinto (P9:) min W(x,t) X,t,ll 3 f(x,t) ~ o Vxs(x,t) + Ll”vxg(x,t) o = P — Mn < g(x,t) –  M(l  n) > g(x,t) — 0 < B>o n. = O or 1 1 , (9a)
(9b) (9C)
(9d) (9e) (9f)
(9!3) (9h)
where M is a fixed, large positive number. For a fixed n, problem P9 is convex and can be readily solved (since in our example s is quadratic and g linear) for a global optimum. The FortunyAmatand McCarl algorithm uses a branchandbound technique to enumerate the possibilitiesfor n, solving P9 at each iteration. In commenting on their computational experience, the authors seem to suggest that for large subproblems (i.e., n of large dimension), their algorithm is not very satisfactory. Parametric ComplementaryPivot. Problem P7 involves finding x, t, and v 3 L which optimizes the objective function,w (Eqn. 7a). Bialas and Karwan reformulate P7 as that of finding a less than some upper bound U. feasible x, t, and v such that the objective is By solving the problem with successivelysmaller
upper bounds until no feasible solution can be found, a solution to P7 will obviously be obtained. Thus the reformulatedproblem is * A quadratic program involves a quadratic objective and linear constraints.
13
(Plo:)
Find x(a), t(a), ~(~) ~w(x,t) ~ a f(x,t) :0 = v S(x,t) + 1l’vxg(x,t) o x (lOa)
(lOb) (1OC) (lOd) (lOe)
(lOf)
finding
P“g(x,t) = o g(x,t) U>cl.
For fixed a, it is relatively easy to write P1O as the problem of
z > Cl 3F(z)
<0
> — — 0, <z,F(z)> = O, the complementarily problem (see Cottle and Dantzig, 1974), for which algorithms are available. Although xand tare not explicitly restricted to be nonnegativein P1O, they can be easily written as the difference between two nonnegativevariables. For convenience,assume t >
0..—x > 0.
Then P1O DIUS these restrictionson t and x can be written in com
plementarityform as (Pll:) <a  w(x,t)  v ~ O, v ~ O> = O < A  f(x,t) >0, <X>o, — t>o>=o — =0 A>o>=o
(ha) (llb) (llC) (lld) (he)
<t X>(), X>o>
<9(xst)~os
ll>o>=o — >0, )(>()>=()
< Vxs(x,t) ~vg(x,t) x Equations (ha)
.
(llf)
and (llb) are restatements of Eqns. (lOa) and (lOb) where
, “dummy” variables v and A have been introducedto be consistentwith complemen14
(with the dummyX) are complicated ways of writing t > 0. Equations (hef) correspond to Eqns. (lOcf). Thus for a given a, a solution to Pll (x,t,u,y,A,x) is feasible for P1O. The minimum a for which Pll has a solution will yield the optimal solution to P7 and thus the optimal solution to P1B1. Bialas and Karwan apparently only examine the linear version of P7 and
use their own algorithm to solve the resulting Pll and to choose successive a. They indicate that their algorithm has worked quite well for the small problem they have examined. c. Descent Methods. The workhorses of nonlinearprogramming have to be the descent methods where first derivative information is used to smoothly approach an optimum. There are two probable reasons these methods have not been more widely used for bilevel programming. One reason is the potential for multiple local optima. Another, possibly more fundamentalproblem, is the computation of derivatives associated with the subproblemB1. Although techniques for computing derivatives of solutions to mathematicalprograms with respect to parameters of those programs have been known for some time (see Fiacco and McCormick, 1968), they are not widely used. Referring back to P1B1, the basic approach is to apply one of the many descent methods to P1. plicitly by B1.
tarity format. Equations (llc)
and (lld)
x is viewed as a function of t, defined imGradients of w and f can be computed if Vtx* is known. (Vtx*
In Pl,
reflects changes in the solution to Bl, x*, from infinitesimal changes in t.) Of course x*(t) may not be uniquely defined nor be differentiableat all t, and Vtx* is unlikely to be Continuous These are potential problems1.
Penalty/Barrier Function Methods.
Shimizu and Aiyoshi (1981) propose
rewriting the subproblem B1 as an unconstrainedminimizationproblem through the use of a barrier function. Rewrite B1 as A solution to B1 can then satisfy a stationarity condition of this unconstrainedfunction.
(P12:)
min{Pr(x,t) ~ s(x,t) + r 41[g(x,t)ll
,
(12)
x
75
where r > 0 and $ is continuous and becomes infinite for (x,t) outside the feasible region. Thus if xr(t) solves P12, then under suitable conditions j~m xr(t) solves B1. Assuming Pr is strictly convex in x, then necessaryand suffi
cient conditionsfor a solution to P12 are the stationarityconditions
vxPr(x,t)
=o
q
(13)
If x is regarded as an implicit function of t, this can be solved for xr(t) providing VxxPr is nonsingular. Furthermore, Vxr(t) =  [v;xpr(x, t)]lV;tPr(x,) t Problem P1B1 can now be rewrittenas (P15:) min w(xr(t),t) t (15a) . (14)
3 f[xr(t) ,tl : o
,
(15b) Many methods are
where xr(t) and vxr(t) are given by Eqns. (13) and (14).
available for solving P15 since derivative informationon xr(t) is available. Shimizu and Aiyoshi (1981) show that if (xr,tr) solves P15 then lim(xr,tr) r+o solves P1B1. This method has been successfullyapplied to small problems. using this method. One difficulty not addressed by the authors is that only local solutionsare found
2.
Direct
Gradient
Methods.
De Silva (1978) has utilized a technique in Given an estimate of
which problem P1 is solved viewing x as a function of t.
t, problem B1 is solved to give both x(t) and Vx(t). In contrast to the barrier function approach of Shimizu and Aiyoshi (1981), in De Silva’s method x(t) can be computed using any nonlinear programming technique and Vx(t) calculated directly using methods developed by Fiacco (1976) for sensitivity analYsis. Thus one moves from one t to the next in P15 using any nonlinear programmingalgorithm that uses first derivative information on w and f. Given a t, any nonlinear programmingmethod can be used to find x(t) and thus Vx(t).
16
A more efficient descent algorithm, particularly appropriate for large problems, has been developed by Kolstad and Lasdon (1985). computation of Vx(t). compute. They focus on the If B1 is very large, this can be very difficult to
I
Following Murtagh and Saunders (1981), they partitionany solution
vector x*(t) of B1 into componentswhich are at bounds (nonbasic variablesx*) . Aand other components (basic and superbasicvariablesx*): X* ~ (x*,x*). If strict complementaryslackness is assumed, as t changes infinitesimally in Bl,
A
only x* will change; the X* will remain at their bounds. This structuringof the problems greatly facilitatesthe computationof Vx*(t) since most components are generally nonbasic. 3. Optimal Value Functions. A subclass of the P1B1 problem has been examined by several authors (P16:) min w($,t) t >f(+,t) & o where = f+(t) min s(x,t) x 39(x,t) ~ o (16c) (16a)
,
(16b)
.
(16d)
Since +(t) is defined as the optimal value function of problem Bl, we know in general that @ is convex (Mangasarianand Rosen, 1964). scalarvalued,V+ is relativelyeasy to compute. Thus, in many cases P16 is a strictly convex program which has a unique local optimum. Also, since $ is Bracken and McGill (1974b) solve such problems, computing VI$numerically. Geoffrion and Hogan (1972) examine a problem similar to P16 (actuallya problem with multiple subproblems), focusing on calculating the directionalderivativesof $(t), since $(t) is not everywhere differentiableeven though it is usually continuous.
77
REFERENCES
1.
2. 3. 4.
Jonathan F. Bard, “An Algorithm for Solving the General BiLevel ProgrammingProblem,”Math. of Ops. Res., ~ (2) 260272 (1983).
J.F.
Bard and J.E. Falk, “An Explicit Solution to the MultiLevel ProgrammingProblem,” Comput & Ops. Res., ~ (1), 77100 (1982).
W.F. Bialas and M.H. Karwan, “On TwoLevel Optimization,”IEEE Trans. Auto. Cont., AC27 (l), 211214 (Feb. 1982). W.F. Bialas and M.H. Karwan, “TwoLevelLinear Programming,”unpublished manuscript,Dept. of IndustrialEngineering,State Universityat New York, Buffalo (undated). J. Bracken and J.T. McGill, “A Convex Programming Model for Optimization Problems in the Constraints,”Oper. Res., — 21, 3036 (1973). J. Bracken and J.T. McGill, “Mathematical Programs With Optimization Problems in the Constraints,”Oper. Res., — 21, 3744 (1973). J. Bracken and J.T. McGill, “DefenseApplicationsof Mathematical Programs with Optimization Problems in the Constraints,”Oper. Res., — 22, 10861096 (1974).
5. 6. 7.
8.
J. Bracken and J.T. McGill, “A Method for :~lving MathematicalPrograms With Nonlinear Programs in the Constraints, Oper. Res., — 10971101 22 (1974).
J. Bracken, J.E. Falk, and F.A. Miercort, “A Strategic Weapons Exchange 25 Allocation Model,” Ops. Res., — (6), 968976 (1977). Wilfred Candler and Roger D. Norton, “MultiLevelProgramming,”World Bank Development Research Center Discussion Paper #20, Washington,DC (Jan. 1977). Wilfred Candler and Roger Norton, “MultiLevelProgrammingand Development Policy,” World Bank Staff Working Paper #258, Washington,DC (May 1977).
9.
10.
11.
12. W. Candler, J. FortunyAmat, and B. McCarl, “The Potential Role of Multilevel Programmingin Agricultural Economics,” Amer. J. Agric. Econ., — 63 (3), 521531 (1981). 13. W. Candler and R. Townsley, “A Linear TwoLevel Programming Problem,” Comput. & Ops. Res., ~ (1), 5976 (1982). Kirby, and W.M. Raike, “Efficient Distribution of 14. R.G. Cassidy, J.J.L. Resources Through Three Levels of Governnmt,” Mgmt. Sci., — (8), pp B46217 B473 (April 1971). 15. C.I. Chen and J.B. Cruz, Jr., ~StackelbergSolution for TwoPerson Games with Biased InformationPatterns, IEEE Trans. Auto. Cont., AC17 (6), 791798 (1972) . 18
16. R.W. Cottle ~nd G.B. Dantzig, “ComplementaryPivot Theory of Mathematical Programming, in Studies in Optimization,G.B. Dantzig and B.C. Eaves, Eds. (MathematicalAssociationot America, Buffalo, Ny, 1974), pp.2751, 17. J.B. Cruz, “LeaderFollower Strategies for Multilevel Systems,” IEEE Trans. Auto Cont., AC23 (2), 244254 (1978). 18. J.W. Danskin, “The Theory of MaxMin with Applications,” J. SIAM Appl. Math. — (4), 641664 (1966). 14 19. G. Dantzig and P. Wolfe, “Decomposition Algorithm for Linear Programs,” Econometric, — 29, 767778 (1961). 20. James E. Falk and Garth P. McCormick, “Mathematical Structure of the InternationalCoal Trade Model,” US Department of Energy Report DOE/NBB0025, Washington,DC (Sept. 1982). 21. A.V. Fiacco, “SensitivityAnalysis for Nonlinear ProgrammingUsing Penalty 10, 287311 (1976). Methods,” Math. Prog., — 22. A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential UnconstrainedMinimizationTechniques (John Wiley, New York, 1968). 23. W. Findeisen, “Decentralizedand HierarchicalControl Under Consistency or Disagreementof Interests,”Automatic, — (6), 647664 (Nov. 1982). 18 24. J. FortunyAmatand B. McCarl, “A Representationof a TwoLevel Programming Problem,” J. Ops. Res. Soc., — 32, 783792 (1981) . 25. A.M. Geoffrion, “Primal ResourceDirective Approaches for Optimizing Nonlinear DecomposableSystems,” Oper. Res., — (3), 375403 (1970). 18 26. A.M. Geoffrion and W.W. Hogan, “Coordination of TwoLevel Organizations with Multiple Objectives, ” in Techniques in Optimization,edited by A.V. Balakrishnan (AcademicPress, Lon~.972). 27. C.D. Kolstad, “An Empirical Analysis of Regulatory Efficiency in Air Pollution Control,” Los Alamos National Laboratory document LAUR811727, Los Alamos, NM (Nov. 1982). 28. C.D. Kolstad and L.S. Lasdon, “A Descent Algorithm for BiLevel MathematicalPrograms,” unpublishedmanuscript,Dept. Economics, University of Illinoisat UrbanaChampaign(1985), 29. J. Kornai and T. Liptak, “TwoLevel Planning,” Economtrica, — 33, 141169 (1965).
30.
Peter B. Luh, YuChi Ho, and Ramal Muralidharan,“Load Adaptive Pricing: An Emerging Tool for Electric Utilities,” IEEE Trans. Auto. Cont., AC27 (2), 320329 (April 1982).
31. O.L. Mangasarianand J.B. Rosen, “Inequalities for Stochastic Nonlinear ProgrammingProblems,”Ops. Res. — (l), 143154 (1964). 12
” 32. J. Marschak, “EconomicMeasurementfor Policy and Prediction, in W.C. Hood and T.C. Koopmans (eds.) Studies in EconometricMethod, Cowles Foundation c Monograph #14 (Yale UniversityPress, New Haven, 1953). 33. Bruce A. Murtagh and Michael A. Saunders, “A Projected LagrangianAlgorithm and its Implementation for Sparse Nonlinear Constraints, ” Systems Optimization Laboratory Report SOL 80lR, Department of Operations Research, Stanford University,Stanford, CA (February1981). 34. G.P. Papavassilopoulos, “Solution of Some Stochastic Nash and LeaderFollower Games,” SIAM J. Cont. & Opt., — (5), 651666 (Sept. 1981). 19 35. G.P. Papavassilopoulos, “Algorithms for Static Stackelberg Games with Linear Costs and Polyhefra Constraints,”Proc., IEEE Conf. on Decision and Control, Atlanta, GA, pp 647652 (Dec. 1982). 36. P.A. Samuelson, “Spatial Price Equilibriumand Linear Programming,” Amer. Econ. Rev. — 42, 283303 (1952). 37. K. Shimizu and E. Aiyoshi, “A New ComputationalMethod for Stackelberg and MinMax Problems by Use of a Penalty Method,” IEEE Trans. Auto. Cont., AC26 (2), 460466 (April 1981). 38. Anura H. de Silva, “Sensitivity Formulas for Nonlinear Factorable Programmingand Their Applicationto the Solution of an Implicitly Defined OptimizationModel of US Crude Oil Production,”D. Sc. dissertation,George Washington University,Washington,DC (January 1978).
39. 40.
H. von Stackelberg, The Theory of the Market Economy (OxfordUniversity Press, London, 1952). T. Takayama and G..Judge, Spatial and Temporal Price and AllocationModels (NorthHolland, Amsterdam, 1971).
+ US.GOVERNMENTPRINTINGOFFICE199567W134U0146
20
Printcdinthe United Ststesof Amxica Available from National Technical Information Service US Dcpartmmt of Commerce 528S Port ROyd Road Springfield,VA 22161 Microfiche (AO1)
Page Range 001.025 026050 051.075 076100 101.125 126.150
NTIS Prim Code A02 A03 A04 A05 A06 A07
Page Range 151. [7s 176.200 201.225 226250 251.275 276.300
NTIS Pikc Code A08 A09 A1O All A12 A13
Page Range 301.325 326350 351.375 376400 401.425 426450
NTIS Price Code A14 A15 A16 A17 A18 A19
Page Range 451475 476.500 501.52S .526.550 551.575 576.600 601.up”
NTIS Price code A20 A21 A22 A23 A24 A25 A99
“Cmtm
NTIS for a price quote.
—
.—
.
ILoswmms