IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v54y2013i3p517-554.html
   My bibliography  Save this article

On convex quadratic programs with linear complementarity constraints

Author

Listed:
  • Lijie Bai
  • John Mitchell
  • Jong-Shi Pang

Abstract

The paper shows that the global resolution of a general convex quadratic program with complementarity constraints (QPCC), possibly infeasible or unbounded, can be accomplished in finite time. The method constructs a minmax mixed integer formulation by introducing finitely many binary variables, one for each complementarity constraint. Based on the primal-dual relationship of a pair of convex quadratic programs and on a logical Benders scheme, an extreme ray/point generation procedure is developed, which relies on valid satisfiability constraints for the integer program. To improve this scheme, we propose a two-stage approach wherein the first stage solves the mixed integer quadratic program with pre-set upper bounds on the complementarity variables, and the second stage solves the program outside this bounded region by the Benders scheme. We report computational results with our method. We also investigate the addition of a penalty term y T Dw to the objective function, where y and w are the complementary variables and D is a nonnegative diagonal matrix. The matrix D can be chosen effectively by solving a semidefinite program, ensuring that the objective function remains convex. The addition of the penalty term can often reduce the overall runtime by at least 50 %. We report preliminary computational testing on a QP relaxation method which can be used to obtain better lower bounds from infeasible points; this method could be incorporated into a branching scheme. By combining the penalty method and the QP relaxation method, more than 90 % of the gap can be closed for some QPCC problems. Copyright Springer Science+Business Media, LLC 2013

Suggested Citation

  • Lijie Bai & John Mitchell & Jong-Shi Pang, 2013. "On convex quadratic programs with linear complementarity constraints," Computational Optimization and Applications, Springer, vol. 54(3), pages 517-554, April.
  • Handle: RePEc:spr:coopap:v:54:y:2013:i:3:p:517-554
    DOI: 10.1007/s10589-012-9497-4
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-012-9497-4
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10589-012-9497-4?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. Jing Hu & John Mitchell & Jong-Shi Pang & Bin Yu, 2012. "On linear programs with linear complementarity constraints," Journal of Global Optimization, Springer, vol. 53(1), pages 29-51, May.
    2. B. Curtis Eaves, 1971. "On Quadratic Programming," Management Science, INFORMS, vol. 17(11), pages 698-711, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jong-Shi Pang & Meisam Razaviyayn & Alberth Alvarado, 2017. "Computing B-Stationary Points of Nonsmooth DC Programs," Mathematics of Operations Research, INFORMS, vol. 42(1), pages 95-118, January.
    2. Bai, Yun & Ouyang, Yanfeng & Pang, Jong-Shi, 2016. "Enhanced models and improved solution for competitive biofuel supply chain design under land use constraints," European Journal of Operational Research, Elsevier, vol. 249(1), pages 281-297.
    3. Jong-Shi Pang & Che-Lin Su & Yu-Ching Lee, 2015. "A Constructive Approach to Estimating Pure Characteristics Demand Models with Pricing," Operations Research, INFORMS, vol. 63(3), pages 639-659, June.
    4. Francisco Jara-Moroni & John E. Mitchell & Jong-Shi Pang & Andreas Wächter, 2020. "An enhanced logical benders approach for linear programs with complementarity constraints," Journal of Global Optimization, Springer, vol. 77(4), pages 687-714, August.
    5. Jing Zhou & Shu-Cherng Fang & Wenxun Xing, 2017. "Conic approximation to quadratic optimization with linear complementarity constraints," Computational Optimization and Applications, Springer, vol. 66(1), pages 97-122, January.
    6. Jacquet, Quentin & van Ackooij, Wim & Alasseur, Clémence & Gaubert, Stéphane, 2024. "Quadratic regularization of bilevel pricing problems and application to electricity retail markets," European Journal of Operational Research, Elsevier, vol. 313(3), pages 841-857.
    7. Yu-Ching Lee & Jong-Shi Pang & John Mitchell, 2015. "An algorithm for global solution to bi-parametric linear complementarity constrained linear programs," Journal of Global Optimization, Springer, vol. 62(2), pages 263-297, June.

    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. Karan N. Chadha & Ankur A. Kulkarni, 2022. "On independent cliques and linear complementarity problems," Indian Journal of Pure and Applied Mathematics, Springer, vol. 53(4), pages 1036-1057, December.
    2. Musshoff, Oliver & Hirschauer, Norbert, 2004. "Optimierung unter Unsicherheit mit Hilfe stochastischer Simulation und Genetischer Algorithmen – dargestellt anhand der Optimierung des Produktionsprogramms eines Brandenburger Marktfruchtbetriebes," German Journal of Agricultural Economics, Humboldt-Universitaet zu Berlin, Department for Agricultural Economics, vol. 53(07), pages 1-16.
    3. Erasmus, Barend & van Jaarsveld, Albert & van Zyl, Johan & Vink, Nick, 2000. "The effects of climate change on the farm sector in the Western Cape," Agrekon, Agricultural Economics Association of South Africa (AEASA), vol. 39(4), pages 1-15, December.
    4. Luo, Z-Q. & Zhang, S., 1997. "On the extensions of the Frank-Worfe theorem," Econometric Institute Research Papers EI 9748/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    5. Wei Xia & Juan C. Vera & Luis F. Zuluaga, 2020. "Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 40-56, January.
    6. Louhichi, Kamel & Flichman, Guillermo & Blanco Fonseca, Maria, 2009. "A generic template for FSSIM," Reports 57463, Wageningen University, SEAMLESS: System for Environmental and Agricultural Modelling; Linking European Science and Society.
    7. Jun Tong & Jian-Qiang Hu & Jiaqiao Hu, 2017. "A Computational Algorithm for Equilibrium Asset Pricing Under Heterogeneous Information and Short-Sale Constraints," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(05), pages 1-16, October.
    8. Paudel, K. P. & Lohr, L. & Martin, N. R., 2000. "Effect of risk perspective on fertilizer choice by sharecroppers," Agricultural Systems, Elsevier, vol. 66(2), pages 115-128, November.
    9. Just, Richard E., 2000. "Some Guiding Principles for Empirical Production Research in Agriculture," Agricultural and Resource Economics Review, Cambridge University Press, vol. 29(2), pages 138-158, October.
    10. Norton, George W., 1976. "Constraints To Increasing Livestock Production In Less Developed Countries: A Literature Review," Staff Papers 14043, University of Minnesota, Department of Applied Economics.
    11. Adams, Richard M. & Menkhaus, Dale J. & Woolery, Bruce A., 1980. "Alternative Parameter Specification In E, V Analysis: Implications For Farm Level Decision Making," Western Journal of Agricultural Economics, Western Agricultural Economics Association, vol. 5(1), pages 1-8, July.
    12. Anderson, Jock R., 1975. "Programming For Efficient Planning Against Non-Normal Risk," Australian Journal of Agricultural Economics, Australian Agricultural and Resource Economics Society, vol. 19(2), pages 1-14, August.
    13. Lei, Chao & Jiang, Zhoutong & Ouyang, Yanfeng, 2020. "Path-based dynamic pricing for vehicle allocation in ridesharing systems with fully compliant drivers," Transportation Research Part B: Methodological, Elsevier, vol. 132(C), pages 60-75.
    14. Hardaker, J. Brian & Pandey, Sushil & Patten, Louise H., 1991. "Farm Planning under Uncertainty: A Review of Alternative Programming Models," Review of Marketing and Agricultural Economics, Australian Agricultural and Resource Economics Society, vol. 59(01), pages 1-14, April.
    15. Walker, Odell L. & Hardin, Mike L. & Mapp, Harry P., Jr. & Roush, Clint E., 1979. "Farm Growth And Estate Transfer In An Uncertain Environment," Southern Journal of Agricultural Economics, Southern Agricultural Economics Association, vol. 11(1), pages 1-12, July.
    16. Gomez-Limon, Jose Antonio & Arriaza Balmón, Manuel, 2000. "Socio-Economic and Environmental Impact of AGENDA 2000 and Alternative Policy Choices for Market Liberalization on an Irrigated Area in Northwestern Spain," Agricultural Economics Review, Greek Association of Agricultural Economists, vol. 1(2), pages 1-14, August.
    17. Brown, Colin G. & Drynan, Ross G., 1986. "Plant Location Analysis Using Discrete Stochastic Programming," Australian Journal of Agricultural Economics, Australian Agricultural and Resource Economics Society, vol. 30(1), pages 1-22, April.
    18. Francisco Jara-Moroni & John E. Mitchell & Jong-Shi Pang & Andreas Wächter, 2020. "An enhanced logical benders approach for linear programs with complementarity constraints," Journal of Global Optimization, Springer, vol. 77(4), pages 687-714, August.
    19. Carvalho, Maria Leonor da Silva & Godinho, Maria de Lurdes Ferro, 2005. "Consequences of the 2003 CAP Reform on a Mediterranean Agricultural System of Portugal," 2005 International Congress, August 23-27, 2005, Copenhagen, Denmark 24719, European Association of Agricultural Economists.
    20. Breitenbach, Marthinus C. & Meyer, Nicolas G., 2000. "Modelling fertiliser use in the grain crop and oilseed sectors of South Africa," Agrekon, Agricultural Economics Association of South Africa (AEASA), vol. 39(3), pages 1-19, September.

    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:spr:coopap:v:54:y:2013:i:3:p:517-554. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.