Optimality conditions for the bilevel programming problem

Naval Research Logistics QuarterlyPublished 1 March 1984

Jonathan F. Bard

Citations168

Abstract

Abstract The bilevel programming problem (BLPP) is a sequence of two optimization problems where the constraint region of the first is determined implicitly by the solution to the second. In this article it is first shown that the linear BLPP is equivalent to maximizing a linear function over a feasible region comprised of connected faces and edges of the original polyhedral constraint set. The solution is shown to occur at a vertex of that set. Next, under assumptions of differentiability, first‐order necessary optimality conditions are developed for the more general BLPP, and a potentially equivalent mathematical program is formulated. Finally, the relationship between the solution to this problem and Pareto optimality is discussed and a number of examples given.

Keywords

Computer ScienceEngineering

Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Nonlinear programming: sequential unconstrained minimization techniques

2,272 Citations1968Anthony V. Fiacco, Garth P. McCormick

Journal of Optimization Theory and ApplicationsOn the Stackelberg strategy in nonzero-sum games

757 Citations1973Marwan A. Simaan, J.B. Cruz

Several game problems, such as games where one of the two players does not know the other's performance criterion or games with different speeds in computing the strategies, are best modeled and solved within this solution concept.

Lecture notes in economics and mathematical systemsLinear Multiobjective Programming

595 Citations1974Milan Zelený

The Origin of the Multiobjective Problem and a Short Historical Review are reviewed and a method for Generating Adjacent Extreme Points - A Second Approach (Multicriteria Simplex Method).

Computers & Operations ResearchAn explicit solution to the multi-level programming problem

503 Citations1982Jonathan F. Bard, James E. Falk

The bi-level linear case is addressed in detail and the reformulated optimization problem is linear save for a complementarity constraint of the form 〈u, g〉 = 0.

SIAM Journal on Applied MathematicsThe Theory of Max-Min, with Applications

423 Citations1966John M. Danskin

Computers & Operations ResearchA linear two-level programming problem

389 Citations1982Wilfred Candler, Robert Townsley

This paper includes a discussion of algorithmic principles, presentation of and comments on an algorithm which allows an implicit search of policies which affect resource availabilities for the behavioural problem, and a numerical example.

Mathematical ProgrammingA cutting plane algorithm for solving bilinear programs

241 Citations1976Hiroshi Konno

A cutting plane algorithm is proposed to solve a special class of nonconvex quadratic program referred to as a bilinear program in the literature and the preliminary results of numerical experiments are encouraging.

IEEE Transactions on Automatic ControlOn two-level optimization

237 Citations1982Wayne F. Bialas, Mark H. Karwan

Characterizations and algorithmic approaches for a class of two-level problems are discussed and a formulation to help model this type of decision making hierarchy is offered.

Management ScienceComparative Evaluation of Some Interactive Approaches to Multicriterion Optimization

218 Citations1975Jyrki Wallenius

This paper describes the results of a laboratory experiment to compare from a human decision-maker's point of view the performance of the interactive methods for multicriterion optimization recently developed by Geoffrion and Benayoun et al. (STEP-method), and a simple trial-and-error procedure for solving the multiple criteria problem.

Mathematical ProgrammingA linear max—min problem

132 Citations1973James E. Falk

This work considers a two person max—min problem in which the maximizing player moves first and the minimizing player has perfect information of the outcome of this move.