IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v249y2016i1p41-54.html
   My bibliography  Save this article

Feasibility problems with complementarity constraints

Author

Listed:
  • Andreani, R.
  • Júdice, J.J.
  • Martínez, J.M.
  • Martini, T.

Abstract

A Projected-Gradient Underdetermined Newton-like algorithm will be introduced for finding a solution of a Horizontal Nonlinear Complementarity Problem (HNCP) corresponding to a feasible solution of a Mathematical Programming Problem with Complementarity Constraints (MPCC). The algorithm employs a combination of Interior-Point Newton-like and Projected-Gradient directions with a line-search procedure that guarantees global convergence to a solution of HNCP or, at least, a stationary point of the natural merit function associated to this problem. Fast local convergence will be established under reasonable assumptions. The new algorithm can be applied to the computation of a feasible solution of MPCC with a target objective function value. Computational experience on test problems from well-known sources will illustrate the efficiency of the algorithm to find feasible solutions of MPCC in practice.

Suggested Citation

  • Andreani, R. & Júdice, J.J. & Martínez, J.M. & Martini, T., 2016. "Feasibility problems with complementarity constraints," European Journal of Operational Research, Elsevier, vol. 249(1), pages 41-54.
    • Handle: RePEc:eee:ejores:v:249:y:2016:i:1:p:41-54
    DOI: 10.1016/j.ejor.2015.09.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715008723
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.09.030?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kovacevic, Raimund M. & Pflug, Georg Ch., 2014. "Electricity swing option pricing by stochastic bilevel optimization: A survey and new approaches," European Journal of Operational Research, Elsevier, vol. 237(2), pages 389-403.
    2. Jane J. Ye, 2011. "Necessary Optimality Conditions for Multiobjective Bilevel Programs," Mathematics of Operations Research, INFORMS, vol. 36(1), pages 165-184, February.
    3. Lin, Gui-Hua & Zhang, Dali & Liang, Yan-Chao, 2013. "Stochastic multiobjective problems with complementarity constraints and applications in healthcare management," European Journal of Operational Research, Elsevier, vol. 226(3), pages 461-470.
    4. X. M. Hu & D. Ralph, 2004. "Convergence of a Penalty Method for Mathematical Programming with Complementarity Constraints," Journal of Optimization Theory and Applications, Springer, vol. 123(2), pages 365-390, November.
    5. Toyasaki, Fuminori & Daniele, Patrizia & Wakolbinger, Tina, 2014. "A variational inequality formulation of equilibrium models for end-of-life products with nonlinear constraints," European Journal of Operational Research, Elsevier, vol. 236(1), pages 340-350.
    6. Daniel Ralph & Oliver Stein, 2011. "The C-Index: A New Stability Concept for Quadratic Programs with Complementarity Constraints," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 504-526, August.
    7. Jian Yao & Ilan Adler & Shmuel S. Oren, 2008. "Modeling and Computing Two-Settlement Oligopolistic Equilibrium in a Congested Electricity Network," Operations Research, INFORMS, vol. 56(1), pages 34-47, February.
    8. Holger Scheel & Stefan Scholtes, 2000. "Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensitivity," Mathematics of Operations Research, INFORMS, vol. 25(1), pages 1-22, February.
    9. Bomze, Immanuel M., 2012. "Copositive optimization – Recent developments and applications," European Journal of Operational Research, Elsevier, vol. 216(3), pages 509-520.
    10. Yao, Jian & Oren, Shmuel S. & Adler, Ilan, 2007. "Two-settlement electricity markets with price caps and Cournot generation firms," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1279-1296, September.
    11. Xinmin Hu & Daniel Ralph, 2007. "Using EPECs to Model Bilevel Games in Restructured Electricity Markets with Locational Prices," Operations Research, INFORMS, vol. 55(5), pages 809-827, October.
    12. Andreas Ehrenmann & Karsten Neuhoff, 2009. "A Comparison of Electricity Market Designs in Networks," Operations Research, INFORMS, vol. 57(2), pages 274-286, April.
    13. Garcia-Rodenas, Ricardo & Verastegui-Rayo, Doroteo, 2008. "A column generation algorithm for the estimation of origin-destination matrices in congested traffic networks," European Journal of Operational Research, Elsevier, vol. 184(3), pages 860-878, February.
    14. J. S. Pang, 2007. "Partially B-Regular Optimization and Equilibrium Problems," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 687-699, August.
    15. J. J. Júdice & H. D. Sherali & I. M. Ribeiro & A. M. Faustino, 2007. "Complementarity Active-Set Algorithm for Mathematical Programming Problems with Equilibrium Constraints," Journal of Optimization Theory and Applications, Springer, vol. 134(3), pages 467-481, September.
    16. R. Andreani & C. Dunder & J. Martínez, 2005. "Nonlinear-programming reformulation of the order-value optimization problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 61(3), pages 365-384, July.
    17. Wu, Di & Yin, Yafeng & Lawphongpanich, Siriphong, 2011. "Pareto-improving congestion pricing on multimodal transportation networks," European Journal of Operational Research, Elsevier, vol. 210(3), pages 660-669, May.
    18. Walpen, Jorgelina & Mancinelli, Elina M. & Lotito, Pablo A., 2015. "A heuristic for the OD matrix adjustment problem in a congested transport network," European Journal of Operational Research, Elsevier, vol. 242(3), pages 807-819.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hu, X. & Ralph, R., 2006. "Using EPECs to model bilevel games in restructured electricity markets with locational prices," Cambridge Working Papers in Economics 0619, Faculty of Economics, University of Cambridge.
    2. Huifu Xu & Dali Zhang, 2013. "Stochastic Nash equilibrium problems: sample average approximation and applications," Computational Optimization and Applications, Springer, vol. 55(3), pages 597-645, July.
    3. Joaquim Júdice, 2012. "Algorithms for linear programming with linear complementarity constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 20(1), pages 4-25, April.
    4. Grimm, Veronika & Martin, Alexander & Schmidt, Martin & Weibelzahl, Martin & Zöttl, Gregor, 2016. "Transmission and generation investment in electricity markets: The effects of market splitting and network fee regimes," European Journal of Operational Research, Elsevier, vol. 254(2), pages 493-509.
    5. Xinmin Hu & Daniel Ralph, 2007. "Using EPECs to Model Bilevel Games in Restructured Electricity Markets with Locational Prices," Operations Research, INFORMS, vol. 55(5), pages 809-827, October.
    6. Grimm, Veronika & Schewe, Lars & Schmidt, Martin & Zöttl, Gregor, 2017. "Uniqueness of market equilibrium on a network: A peak-load pricing approach," European Journal of Operational Research, Elsevier, vol. 261(3), pages 971-983.
    7. Andreas Ehrenmann & Karsten Neuhoff, 2009. "A Comparison of Electricity Market Designs in Networks," Operations Research, INFORMS, vol. 57(2), pages 274-286, April.
    8. Filippo Pecci & Edo Abraham & Ivan Stoianov, 2017. "Penalty and relaxation methods for the optimal placement and operation of control valves in water supply networks," Computational Optimization and Applications, Springer, vol. 67(1), pages 201-223, May.
    9. Dongyan Chen & Chunying Tian & Zhaobo Chen & Ding Zhang, 2022. "Competition among supply chains: the choice of financing strategy," Operational Research, Springer, vol. 22(2), pages 977-1000, April.
    10. Moiseeva, Ekaterina & Wogrin, Sonja & Hesamzadeh, Mohammad Reza, 2017. "Generation flexibility in ramp rates: Strategic behavior and lessons for electricity market design," European Journal of Operational Research, Elsevier, vol. 261(2), pages 755-771.
    11. Daniel Ralph & Oliver Stein, 2011. "The C-Index: A New Stability Concept for Quadratic Programs with Complementarity Constraints," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 504-526, August.
    12. Giandomenico Mastroeni & Letizia Pellegrini & Alberto Peretti, 2021. "Some numerical aspects on a method for solving linear problems with complementarity constraints," Working Papers 16/2021, University of Verona, Department of Economics.
    13. H. Z. Luo & X. L. Sun & Y. F. Xu, 2010. "Convergence Properties of Modified and Partially-Augmented Lagrangian Methods for Mathematical Programs with Complementarity Constraints," Journal of Optimization Theory and Applications, Springer, vol. 145(3), pages 489-506, June.
    14. Krebs, Vanessa & Schewe, Lars & Schmidt, Martin, 2018. "Uniqueness and multiplicity of market equilibria on DC power flow networks," European Journal of Operational Research, Elsevier, vol. 271(1), pages 165-178.
    15. Hoai An Thi & Thi Minh Tam Nguyen & Tao Pham Dinh, 2023. "On solving difference of convex functions programs with linear complementarity constraints," Computational Optimization and Applications, Springer, vol. 86(1), pages 163-197, September.
    16. Hélène Le Cadre, 2019. "On the efficiency of local electricity markets under decentralized and centralized designs: a multi-leader Stackelberg game analysis," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(4), pages 953-984, December.
    17. Uday V. Shanbhag & Gerd Infanger & Peter W. Glynn, 2011. "A Complementarity Framework for Forward Contracting Under Uncertainty," Operations Research, INFORMS, vol. 59(4), pages 810-834, August.
    18. Lei Guo & Gui-Hua Lin, 2013. "Notes on Some Constraint Qualifications for Mathematical Programs with Equilibrium Constraints," Journal of Optimization Theory and Applications, Springer, vol. 156(3), pages 600-616, March.
    19. Suhong Jiang & Jin Zhang & Caihua Chen & Guihua Lin, 2018. "Smoothing partial exact penalty splitting method for mathematical programs with equilibrium constraints," Journal of Global Optimization, Springer, vol. 70(1), pages 223-236, January.
    20. Lei Guo & Gui-Hua Lin & Jane J. Ye, 2013. "Second-Order Optimality Conditions for Mathematical Programs with Equilibrium Constraints," Journal of Optimization Theory and Applications, Springer, vol. 158(1), pages 33-64, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:249:y:2016:i:1:p:41-54. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.