IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i2p270-d726000.html
   My bibliography  Save this article

A Relaxed and Bound Algorithm Based on Auxiliary Variables for Quadratically Constrained Quadratic Programming Problem

Author

Listed:
  • Chenyang Hu

    (School of Mathematics and Information Sciences, North Minzu University, Yinchuan 750021, China
    Ningxia Province Cooperative Innovation Center of Scientific Computing and Intelligent Information Processing, North Minzu University, Yinchuan 750021, China)

  • Yuelin Gao

    (Ningxia Province Cooperative Innovation Center of Scientific Computing and Intelligent Information Processing, North Minzu University, Yinchuan 750021, China
    Ningxia Province Key Laboratory of Intelligent Information and Data Processing, North Minzu University, Yinchuan 750021, China)

  • Fuping Tian

    (School of Mathematics and Information Sciences, North Minzu University, Yinchuan 750021, China)

  • Suxia Ma

    (School of Mathematics and Information Sciences, North Minzu University, Yinchuan 750021, China
    Ningxia Province Key Laboratory of Intelligent Information and Data Processing, North Minzu University, Yinchuan 750021, China)

Abstract

Quadratically constrained quadratic programs (QCQP), which often appear in engineering practice and management science, and other fields, are investigated in this paper. By introducing appropriate auxiliary variables, QCQP can be transformed into its equivalent problem (EP) with non-linear equality constraints. After these equality constraints are relaxed, a series of linear relaxation subproblems with auxiliary variables and bound constraints are generated, which can determine the effective lower bound of the global optimal value of QCQP. To enhance the compactness of sub-rectangles and improve the ability to remove sub-rectangles, two rectangle-reduction strategies are employed. Besides, two ϵ -subproblem deletion rules are introduced to improve the convergence speed of the algorithm. Therefore, a relaxation and bound algorithm based on auxiliary variables are proposed to solve QCQP. Numerical experiments show that this algorithm is effective and feasible.

Suggested Citation

  • Chenyang Hu & Yuelin Gao & Fuping Tian & Suxia Ma, 2022. "A Relaxed and Bound Algorithm Based on Auxiliary Variables for Quadratically Constrained Quadratic Programming Problem," Mathematics, MDPI, vol. 10(2), pages 1-18, January.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:2:p:270-:d:726000
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/2/270/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/2/270/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Jiao, Hongwei & Liu, Sanyang & Lu, Nan, 2015. "A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming," Applied Mathematics and Computation, Elsevier, vol. 250(C), pages 973-985.
    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. Bo Zhang & YueLin Gao & Xia Liu & XiaoLi Huang, 2023. "Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems," Journal of Global Optimization, Springer, vol. 86(1), pages 61-92, May.

    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:gam:jmathe:v:10:y:2022:i:2:p:270-:d:726000. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.