Branch-delete-bound algorithm for globally solving quadratically constrained quadratic programs

• Autorzy: Zhisong Hou , Hongwei Jiao , Lei Cai , Chunyang Bai
• Języki publikacji: EN

Abstrakty

EN

This paper presents a branch-delete-bound algorithm for effectively solving the global minimum of quadratically constrained quadratic programs problem, which may be nonconvex. By utilizing the characteristics of quadratic function, we construct a new linearizing method, so that the quadratically constrained quadratic programs problem can be converted into a linear relaxed programs problem. Moreover, the established linear relaxed programs problem is embedded within a branch-and-bound framework without introducing any new variables and constrained functions, which can be easily solved by any effective linear programs algorithms. By subsequently solving a series of linear relaxed programs problems, the proposed algorithm can converge the global minimum of the initial quadratically constrained quadratic programs problem. Compared with the known methods, numerical results demonstrate that the proposed method has higher computational efficiency.

Słowa kluczowe

EN

Quadratically constrained quadratic programs; Global optimization; Linearizing method; Deleting technique; Branch-delete-bound algorithm

Kategorie tematyczne

• 65K05: Mathematical programming methods
• 90C20: Quadratic programming
• 90C26: Nonconvex programming, global optimization

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2017
• Tom: 15
• Numer: 1
• Strony: 1212-1224

Daty

wydano

2017-01-01

otrzymano

2017-01-21

zaakceptowano

2017-07-25

online

2017-10-03

Twórcy

autor

Zhisong Hou

• , , ,

autor

Hongwei Jiao

• , , ,

autor

Lei Cai

• , , ,

autor

Chunyang Bai

• , , ,

Identyfikatory

DOI

10.1515/math-2017-0099