Skip to main content
SpringerLink
Log in

On the Quasiconcave Bilevel Programming Problem

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

Bilevel programming involves two optimization problems where the constraint region of the first-level problem is implicitly determined by another optimization problem. In this paper, we consider the case in which both objective functions are quasiconcave and the constraint region common to both levels is a polyhedron. First, it is proved that this problem is equivalent to minimizing a quasiconcave function over a feasible region comprised of connected faces of the polyhedron. Consequently, there is an extreme point of the polyhedron that solves the problem. Finally, it is shown that this model includes the most important case where the objective functions are ratios of concave and convex functions

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bialas, W. F., and Karwan, M. H., On Two-Level Optimization, IEEE Transactions on Automatic Control, Vol. 27, pp. 211–214, 1982.

    Google Scholar 

  2. Bard, J. F., Optimality Conditions for the Bilevel Programming Problem, Naval Research Logistics Quarterly, Vol. 31, pp. 13–26, 1984.

    Google Scholar 

  3. Bialas, W. F., and Karwan, M. H., Two-Level Linear Programming, Management Science, Vol. 30, pp. 1004–1024, 1984.

    Google Scholar 

  4. Candler, W., and Townsley, R. J., A Linear Two-Level Programming Problem. Computers and Operations Research, Vol. 9, pp. 59–76, 1982.

    Google Scholar 

  5. Hansen, P., Jaumard, B., and Savard, G., New Branch-and-Bound Rules for Linear Bilevel Programming, SIAM Journal on Scientific and Statistical Computing, Vol. 13, pp. 1194–1217, 1992.

    Google Scholar 

  6. JÚdice, J., and Faustino, A. M., A Sequential LCP Method for Bilevel Linear Programming, Annals of Operations Research, Vol. 34, pp. 89–106, 1992.

    Google Scholar 

  7. Ben-Ayed, O., Bilevel Linear Programming, Computers and Operations Research, Vol. 20, pp. 485–501, 1993.

    Google Scholar 

  8. Bard, J. F., Convex Two-Level Optimization, Mathematical Programming, Vol. 40, pp. 15–27, 1988.

    Google Scholar 

  9. Moore, J. T., and Bard, J. F., The Mixed Integer Linear Bilevel Programming Problem, Operations Research, Vol. 38, pp. 911–921, 1990.

    Google Scholar 

  10. Fortuny-Amat, J., and McCarl, B., A Representation and Economic Interpretation of a Two-Level Programming Problem, Journal of the Operational Research Society, Vol. 32, pp. 783–792, 1981.

    Google Scholar 

  11. Bard, J. F., and Falk, J. E., An Explicit Solution to the Multilevel Programming Problem, Computers and Operations Research, Vol. 9, pp. 77–100, 1982.

    Google Scholar 

  12. Bard, J. F., An Algorithm for Solving the General Bilevel Programming Problem, Mathematics of Operations Research, Vol. 8, pp. 260–272, 1983.

    Google Scholar 

  13. Bard, J. F., and Moore, J. T., A Branch-and-Bound Algorithm for the Bilevel Programming Problem, SIAM Journal of Scientific and Statistical Computing, Vol. 11, pp. 281–292, 1990.

    Google Scholar 

  14. Tuy, H., Migdalas, A., and VÄrbrand, P., A Global Optimization Approach for the Linear Two-Level Program, Journal of Global Optimization, Vol. 3, pp. 1–23, 1993.

    Google Scholar 

  15. Tuy, H., Migdalas, A., and VÄrbrand, P., A Quasiconcave Minimization Method for Solving Linear Two-Level Programs, Journal of Global Optimization, Vol. 4, pp. 243–263, 1994.

    Google Scholar 

  16. Ishizuka, Y., and Aiyoshi, E., Double Penalty Method for Bilevel Linear Programming, Annals of Operations Research, Vol. 34, pp. 73–88, 1992.

    Google Scholar 

  17. Kolstad, C. D., and Lasdon, L. S., Derivative Evaluation and Computational Experience with Large Bilevel Mathematical Programs, Journal of Optimization Theory and Applications, Vol. 65, pp. 485–499, 1990.

    Google Scholar 

  18. Vicente, L., Savard, G., and JÚdice, J., Descent Approaches for Quadratic Bilevel Programming, Journal of Optimization Theory and Applications, Vol. 81, pp. 379–399, 1994.

    Google Scholar 

  19. Clarke, P., and Westerberg, A., A Note on the Optimality Conditions for the Bilevel Programming Problem, Naval Research Logistics, Vol. 35, pp. 413–418, 1988.

    Google Scholar 

  20. Dempe, S., A Necessary and a Sufficient Optimality Condition for Bilevel Programming Problems, Optimization, Vol. 25, pp. 341–354, 1992.

    Google Scholar 

  21. Savard, G., and Gauvin, J., The Steepest Descent Direction for the Nonlinear Bilevel Programming Problem, Operations Research Letters, Vol. 15, pp. 265–272, 1994.

    Google Scholar 

  22. Vicente, L. N., and Calamai, P. H., Geometry and Local Optimality Conditions for Bilevel Programs with Quadratic Strictly Convex Lower Levels, Minimax and Applications, Nonconvex Optimization and Its Applications, Edited by D. Du and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Holland, Vol. 4, pp. 141–151, 1995.

    Google Scholar 

  23. Anandalingam, G., and Friesz, T. L., Editors, Hierarchical Optimization, Annals of Operations Research, Vol. 34, 1992.

  24. Vicente, L. N., and Calamai, P. H., Bilevel and Multilevel Programming: A Bibliography Review, Journal of Global Optimization, Vol. 5, pp. 291–306, 1994.

    Google Scholar 

  25. Schaible, S., Fractional Programming, Handbook of Global Optimization, Edited by R. Horst and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Holland, pp. 495–608, 1995.

    Google Scholar 

  26. Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970

    Google Scholar 

  27. Bazaraa, M. S., Sherali, H. D., and Shetty, C. M., Nonlinear Programming: Theory and Algorithms, 2nd Edition, John Wiley and Sons, New York, New York, 1993.

    Google Scholar 

  28. Hogan, W. W., Point-to-Set Maps in Mathematical Programming, SIAM Review, Vol 15, pp. 591–603, 1973.

    Google Scholar 

  29. Dantzig, G. B., Folkman, J., and Shapiro, N., On the Continuity of the Minimum Set of a Continuous Function, Journal of Mathematical Analysis and Applications, Vol. 17, pp. 519–548, 1967.

    Google Scholar 

  30. Naccache, P. H., Connectedness of the Set of Nondominated Outcomes in Multicriteria Optimization, Journal of Optimization Theory and Applications, Vol. 25, pp. 459–467, 1978.

    Google Scholar 

  31. Avriel, M., Diewert, W. E., Schaible, S., and Zang, I., Generalized Concavity, Plenum Press, New York, New York, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Métodos Estadísticos, Universidad de Zaragoza, Zaragoza, Spain

    H. I. Calvete (Associate Professor)

  2. Departamento de Métodos Estadísticos, Universidad de Zaragoza, Zaragoza, Spain

    C. Galé (Graduate Student (DGA-BCB/1094)

Authors
  1. H. I. Calvete
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. Galé
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Calvete, H.I., Galé, C. On the Quasiconcave Bilevel Programming Problem. Journal of Optimization Theory and Applications 98, 613–622 (1998). https://doi.org/10.1023/A:1022624029539

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1022624029539

Search

Navigation