Abstract
When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Aiyoshi and K. Shimizu, Hierarchical decentralized systems and its new solution by a barrier method, IEEE Trans. Systems, Man, and Cybernetics SMC-11(1981)444–449.
E. Aiyoshi and K. Shimizu, A solution method for the static constrained Stackelberg problem via penalty method, IEEE Trans. Auto. Control AC-29(1984)1111–1114.
F.A. Al-Khayyal and J.E. Falk, Jointly constrained biconvex programming, Math. Oper. Res. 8(1983)273–286.
R.M. Arana, Programming with some linear and one quadratic economic activities, Cahiers du C.E.R.P. 21, 3(1979)247–255.
J.F. Bard, An algorithm for solving the general bilevel programming problem, Math. Oper. Res. 8(1983)260–272.
J.B. Bard, Convex two-level programming, Math. Progr. 40(1988)15–28.
J.F. Bard, Coordination of a multidivisional firm through two levels of management, Omega 11(1983) 457–468.
J.F. Bard and J.E. Falk, An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9(1982)77–100.
T. Basar and G.J. Olsder,Dynamic Noncooperative Games (Academic Press, New York, 1982).
T. Basar and H. Selbuz, Closed loop Stackelberg strategies with applications in optimal control of multilevel systems, IEEE Trans. Auto. Control AC-24(1979)166–178.
W.F. Bialas and W.F. Karwan, Two-level linear programming, Manag. Sci. 30(1984)1004–1020.
R.M. Burton and B. Obel, The multilevel approach to organizational issues of the firm: A critical review, Omega 5(1977)395–444.
W. Candler and R. Townsley, A linear two-level programming problem, Comput. Oper. Res. 9(1982)59–76.
W. Candler, J. Fortuny-Amat and B. McCarl, The potential role of multilevel programming in agricultural economics, Amer. J. Agricult. Econ. 63(1981)521–531.
J.B. Cruz, Jr., Leader-follower strategies for multilevel systems, IEEE Trans. Auto. Control AC-23(1978)244–255.
D.P. Baron, Quadratic programming with quadratic constraints, Naval Res. Logist. Quart. 19(1972)253–260.
J.G. Ecker and R.D. Niemi, A dual method for quadratic programs with quadratic constraints, SIAM J. Appl. Math. 28(1975)568–576.
J.E. Falk, Lagrange multipliers and nonconvex programming, SIAM J. Control 7(1969)534–545.
J.E. Falk, An algorithm for locating approximate global solutions of nonconvex separable problems, Working Paper T-262, The George Washington University, Washington, DC 20052 (1972).
J.E. Falk and K.L. Hoffman, A successive underestimation method for concave minimization, Math. Oper. Res. 1(1976)251–259.
J. Fortuny-Amat and B. McCarl, A representation and economic interpretation of a two-level programming problem, J. Oper. Res. Soc. 32(1981)783–792.
P. Hansen, B. Jaumard and G. Savage, New branching and bounding rules for linear bilevel programming, SIAM J. Sci. Statist. Comput., to appear.
R. Horst, A general class of branch and bound methods in global optimization with some new approaches for concave minimization, JOTA 51(1986)271–291.
R. Horst and H. Tuy,Global Optimization: Deterministic Approaches (Springer, Berlin, 1990).
R.G. Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Progr. 32(1985)146–164.
D.G. Kabe, Quadratic constrained linear programming, Ind. Math. 33, pt. 2 (1983) 115–125.
L.J. Leblanc and D.E. Boyce, A bilevel programming algorithm for exact solution of the network design problem with user-optimal flows, Transport. Res. 20B(1986)259–265.
M.S. Mahoud, Multilevel systems control and applications: A survey, IEEE Trans. Systems, Man, and Cybernetics SMC-7(1977)125–143.
K. Maling, S.H. Mueller and W.R. Heller, On finding most optimal rectangular package plans,Proc. 19th Design Automation Conf. (1982), pp. 663–670.
P. Marcotte, Network design problem with congestion effects: A case of bilevel programming, Math. Progr. 34(1986)142–162.
C.E. Miller, The simplex method for local separable programming, in:Recent Advances in Mathematical Programming, ed. R.L. Graves and P. Wolfe (McGraw-Hill, New York, 1965), pp. 89–100.
C. Van de Panne, Programming with a quadratic constraint, Manag. Sci. 12(1966)709–815.
P.M. Pardalos, Objective function approximation in nonconvex programming,Proc. 18th Modeling and Simulation Conf. (1987), pp. 1605–1610.
P.M. Pardalos, J.H. Glick and J.B. Rosen, Global minimization of indefinite quadratic problems, Computing 39(1987)281–291.
P.M. Pardalos and J.B. Rosen, Methods for global concave minimization: A bibliographic survey, SIAM Rev. 28, 3(1986)367–379.
P.M. Pardalos and J.B. Rosen,Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science 268 (Springer, 1987).
H. Phan, Quadratically constrained quadratic programming: Some applications and a method of solution, Z. Oper. Res. 26(1982)105–119.
J.B. Rosen and P.M. Pardalos, Global minimization of large-scale constrained concave quadratic problems by separable programming, Math. Progr. 34(1986)163–174.
G.R. Reeves, Global minimization in nonconvex all-quadratic programming, Manag. Sci. 22(1975)76–86.
S. Sahni, Computationally related problems, SIAM J. Comput. 3(1974)262–279.
H.D. Sherali, A multiple-leader Stackelberg model analysis, Oper. Res. 32(1984)390–404.
H.D. Sherali, A.L. Soyster and F.H. Murphy, Stackelberg-Nash-Cournot equilibria: Characterization and computations, Oper. Res. 31(1983)253–276.
M. Simaan and J.B. Cruz, Jr., On the Stackelberg strategy in nonzero-sum games, J. Optim. Theory Appl. 11(1973)533–555.
H. Von Stackelberg,The Theory of the Market Economy (Oxford University Press, 1952).
R.M. Soland, An algorithm for separable nonconvex programming problems II: Nonconvex constraints, Manag. Sci. 17(1971)759–773.
K. Swarup, Indefinite quadratic programming with a quadratic constraint, Ekonomickomatem. Obzor 4, 1(1966)69–75.
K. Tarvainen and Y.Y. Haimes, Coordination of hierarchical multiobjective systems: Theory and methodology, IEEE Trans. Systems, Man, and Cybernetics SMC-7(1977)125–143.
B. Tolwinski, Closed-loop Stackelberg solution to multi-stage linear-quadratic game, J. Optim. Theory Appl. 34(1981)485–501.
H. Tuy, Global minimization of a difference of two convex functions, Math. Progr. Study 30(1987)150–182.
R.E. Wendell, Multiple criteria decision making with multiple decision makers, Oper. Res. 28(1980)1100–1111.
E.P. Winkofsky, N.R. Baker and D.J. Sweeney, A decision process model of R&D resource allocation in hierarchical organizations, Manag. Sci. 27(1981)268–283.
M. Zeleny,Multiple Criteria Decision Making (McGraw-Hill, New York, 1982).
Author information
Authors and Affiliations
Additional information
Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida.
Rights and permissions
About this article
Cite this article
Al-Khayyal, F.A., Horst, R. & Pardalos, P.M. Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming. Ann Oper Res 34, 125–147 (1992). https://doi.org/10.1007/BF02098176
Issue Date:
DOI: https://doi.org/10.1007/BF02098176