Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems

被引:2
作者
Zhang, Bo [1 ,2 ]
Gao, YueLin [3 ,4 ]
Liu, Xia [2 ]
Huang, XiaoLi [4 ]
机构
[1] Ningxia Univ, Sch Civil & Hydraul Engn, Yinchuan 750021, Peoples R China
[2] Ningxia Univ, Sch Math & Stat, Yinchuan 750021, Peoples R China
[3] North Minzu Univ, Ningxia Prov Key Lab Intelligent Informat & Data P, Yinchuan 750021, Peoples R China
[4] North Minzu Univ, Sch Math & Informat Sci, Yinchuan 750021, Peoples R China
基金
中国国家自然科学基金;
关键词
Global optimization; Quadratic program; Branch-and-bound; Outcome space; CUT ALGORITHM; OPTIMIZATION; RELAXATION; SDP;
D O I
10.1007/s10898-022-01255-8
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
The quadratically constrained quadratic programming problem often appears in various fields such as engineering practice, management science and network communication. This paper mainly considers a non-convex quadratic programming problem with convex quadratic constraints. Firstly, the objective function of the problem is reconstructed into a form composed of only one convex function and several linear functions by using the eigenvalue decomposition technique of matrix. Then the reconstructed problem is converted to the equivalent problem with simple concave quadratic objective function in the outcome space by introducing appropriate auxiliary variables, and its feasible domain is convex. Based on the branch-and-bound framework which can guarantee the global optimality of the solution, a global optimization algorithm for solving the equivalent problem is proposed, which integrates the effective relaxation process and the branching process related to the outer approximation technique. Finally, the effectiveness and feasibility of the algorithm are illustrated by numerical experiments.
引用
收藏
页码:61 / 92
页数:32
相关论文
共 50 条
[41]   A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs [J].
Vielma, Juan Pablo ;
Ahmed, Shabbir ;
Nemhauser, George L. .
INFORMS JOURNAL ON COMPUTING, 2008, 20 (03) :438-450
[42]   An efficient branch-and-bound algorithm using an adaptive branching rule with quadratic convex relaxation for globally solving general linear multiplicative programs [J].
Zhang, Yanzhen ;
Shen, Peiping ;
Huang, Bingdi ;
Deng, Yaping .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2024, 450
[43]   A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation [J].
Luo, Hezhi ;
Chen, Sikai ;
Wu, Huixian .
NUMERICAL ALGORITHMS, 2021, 88 (02) :993-1024
[44]   Penalty boundary sequential convex programming algorithm for non-convex optimal control problems [J].
Zhang, Zhe ;
Jin, Gumin ;
Li, Jianxun .
ISA TRANSACTIONS, 2018, 72 :229-244
[45]   Effective outcome space branch-and-bound algorithm for solving the sum of affine ratios problem [J].
Shi, Yan ;
Zheng, Qunzhen ;
Yin, Jingben .
AIMS MATHEMATICS, 2024, 9 (09) :23837-23858
[46]   Output-space branch-and-bound reduction algorithm for generalized linear fractional-multiplicative programming problem [J].
Gao, Yuelin ;
Zhang, Bo .
CHAOS SOLITONS & FRACTALS, 2023, 175
[47]   A Branch-and-Bound Algorithm for Representative Integer Efficient Solutions in Multiple Objective Network Programming Problems [J].
Sun, Minghe .
NETWORKS, 2013, 62 (01) :56-71
[48]   IMAGE SPACE BRANCH-AND-BOUND ALGORITHM FOR GLOBALLY SOLVING MINIMAX LINEAR FRACTIONAL PROGRAMMING PROBLEM [J].
Jiao, Hongwei ;
Ma, Junqiao ;
Shang, Youlin .
PACIFIC JOURNAL OF OPTIMIZATION, 2022, 18 (01) :195-212
[49]   Branch-Relaxation-Bound Algorithm for Minimizing a Class of Sum of Affine Ratios Programming Problems [J].
Huang, Xiaoli ;
Ma, Xiaohua ;
Gao, Yuelin ;
Liu, Xia .
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2025,
[50]   Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems [J].
Jiao, Hongwei ;
Wang, Wenjie ;
Yin, Jingben ;
Shang, Youlin .
RAIRO-OPERATIONS RESEARCH, 2022, 56 (03) :1533-1552