# Branch-and-Reduction Algorithm for Indefinite Quadratic Programming Problem

Authors: Yongjian Qiu; Yuming Zhu; Jingben Yin
Journal: Complexity
 (2021)

---

## Abstract

This paper presents a rectangular branch-and-reduction algorithm for globally solving indefinite quadratic programming problem (IQPP), which has a wide application in engineering design and optimization. In this algorithm, first of all, we convert the IQPP into an equivalent bilinear optimization problem (EBOP). Next, a novel linearizing technique is presented for deriving the linear relaxation programs problem (LRPP) of the EBOP, which can be used to obtain the lower bound of the global optimal value to the EBOP. To obtain a global optimal solution of the EBOP, the main computational task of the proposed algorithm involves the solutions of a sequence of LRPP. Moreover, the global convergent property of the algorithm is proved, and numerical experiments demonstrate the higher computational performance of the algorithm.


---

## Body

## 1. Introduction

This paper considers the following indefinite quadratic programming problem:(1)IQPP:minfs=sTΘs+cTs,s.t.s∈D=s∈Rn|As≤b,where Θ=Θjkn×n is an n×n real symmetric matrix; A=ajkm×n is an m×n real matrix, c∈Rn, s∈Rn, and b∈Rm.The IQPP is a class of important nonlinear and nonconvex optimization problems; it has attracted the attention of many scholars for many years. On the one hand, it is because the IQPP has a wide range of applications in management science, optimal control, financial optimization, engineering design, production plan, and so on [1, 2]. On the other hand, it is because many nonlinear and nonconvex optimization problems can be transformed into this form of the IQPP [3–6], such as linear multiplicative programs problem, generalized linear multiplicative programs problem, and 0-1 programs problem. In addition, since the IQPP usually produces many local optimum solutions which are not global optimum, which puts forward many important theories and computational difficulties, that it is very necessary to propose a feasible and effective algorithm for globally solving the IQPP.In the last decades, many algorithms have been proposed for globally solving the IQPP and its special forms. In these algorithms, most of them adopt the branch-and-bound framework, for example, the branch-and-bound algorithm based on parametric linear relaxation [7], branch-and-bound outer approximation algorithm [8], branch-and-reduce algorithms based on linear relaxation [9–18], and branch-and-cut algorithm [19]. In these algorithms, to be specified, Gao et al. [10, 11] propose two novel branch-and-reduce approaches for the IQPP by employing a new rectangle partitioning method and some reducing tactics. By using linear relaxation approach or parametric linear relaxation method to derive the more reliable lower bound, Jiao et al. [14, 16] present two range division and reduction algorithms for the quadratically constrained sum of quadratic ratios problem, which acquire the efficient lower bounds without introducing additional new variables and constraints, which can be also used to globally solve the IQPP; by using a new parametric linearizing technique, Jiao et al. [9] give a parametric linear relaxation algorithm for globally solving nonconvex quadratic programming problem with linear constraints; by employing a new accelerating technique, Ge and Liu [12] propose an accelerating algorithm for globally solving the indefinite quadratic programming problem with quadratic constraints. In addition to the algorithms mentioned above, some algorithms for linear multiplicative programming, nonlinear multiplicative programming, generalized linear multiplicative programming, and generalized geometric programming can be also used to solve these classes of IQPP; see [4, 20–40] for details.Although many solution algorithms have been proposed for the IQPP, the global optimization algorithm for solving the IQPP with the assumption thatΘ=Θjkn×n is an arbitrary n×n real symmetric matrix is rarely studied in the literature. Thus, it is still very necessary to propose a potential practical algorithm for globally solving the IQPP.In this paper, based on the branch-and-bound framework and new linear relaxation technique, we will present a new branch-and-reduction algorithm for globally solving the IQPP. Firstly, we convert the IQPP into an EBOP. Secondly, we construct a new linear relaxation technique, which can be used to derive the LRPP of the EBOP. Thirdly, a new deleting technique is constructed for reducing the scope of the investigated rectangle. Finally, the global convergence of the proposed algorithm is proved, and comparing with the known methods, numerical experimental results show that the proposed algorithm in this paper works as well as or better than the currently known methods.The remaining sections of this paper are organized as follows: in Section2, first of all, we convert the IQPP into the EBOP. Next, a new linearizing technique is proposed for deriving the LRPP of the EBOP. In Section 3, a reduction technique is derived for improving the computational efficiency, based on the branch-and-bound framework, by combing the derived LRPP with the deleting technique, a branch-and-reduction algorithm is established for globally solving the IQPP in Section 4, and its global convergence is derived in this section. In Section 5, comparing with the existing methods, some numerical examples in the recent literature are used to verify the feasibility and computational efficiency of the algorithm. Finally, some conclusions are presented.


## 2. Linear Relaxation Programming Problems

LetΘi be the ith row of the matrix Θ, and let(2)ti=Θis=∑k=1nΘiksk,i=1,2,…,n,s¯i0=mins∈Ds,s¯i0=maxs∈Ds,i=1,2,…,n,t¯i0=mins∈D∩H0Θis,t¯i0=maxs∈D∩H0Θis,i=1,2,…,n,H0=s∈Rn|s¯i0≤si≤s¯i0,i=1,2,…,n,T0=t∈Rn|t¯i0≤ti≤t¯i0,i=1,2,…,n.By introducing new variablesti,i=1,…,n, we can convert the IQPP into the following EBOP:(3)EBOP:minfs,t=∑i=1ncisi+∑i=1nsitis.t.As≤b,ti=∑k=1nθiksk,i=1,2,…,n,s∈H0,t∈T0.In the following, the main work is to solve the EBOP. As everyone knows, in a branch-and-bound procedure, to globally solving the EBOP, the principal operation is the computation of lower bounds for the EBOP and its subproblems. The lower bounds of the global optimal values of the EBOP and its subproblems can be obtained by solving a series of LRPP of the EBOP, which can be established by the following linear relaxation technique.Without loss of generality, we let(4)H=s∈Rn|s¯i≤si≤s¯i,i=1,2,…,n⊆H0,T=t∈Rn|t¯i≤ti≤t¯i,i=1,2,…,n⊆T0.And without loss of generality, for anys∈H, t∈T and define the following functions:(5)gsi=si2,glsi=s¯i+s¯isi−s¯i+s¯i24,gusi=s¯i+s¯isi−s¯is¯i,gti=ti2,glti=t¯i+t¯iti−t¯i+t¯i24,guti=t¯i+t¯iti−t¯it¯i,gsi,ti=siti,gusi,ti=12s¯i+s¯iti+t¯i+t¯isi+s¯i−t¯i+s¯i−t¯i24−s¯is¯i−t¯it¯i,glsi,ti=12s¯i+s¯iti+t¯i+t¯isi+s¯i−t¯is¯i−t¯i−s¯i+s¯i24−t¯i+t¯i24.As we know, the functiongsi=si2 is a convex function about si over s¯i,s¯i; we have that its affine concave envelope is(6)gusi=s¯i+s¯isi−s¯is¯i,and its tangential approximation function is(7)glsi=si¯+s¯isi−s¯i+s¯i24,which is parallel to gusi and the tangential approximation point occurs at s¯i+s¯i/2.Therefore, from the geometric property of the functiongsi=si2 over s¯i,s¯i, we have(8)glsi=si¯+si¯si−si¯+si¯24≤si2≤s¯i+s¯isi−s¯is¯i=gusi.Similarly, we consider the functiongti=ti2 over t¯i,t¯i; it can follow that(9)glti=t¯i+t¯iti−t¯i+t¯i24≤gti≤t¯i+t¯iti−t¯it¯i=guti.Furthermore, if we suppose thatsi−ti is a single variable, then si−ti2 is a convex function about si−ti over s¯i−t¯i,s¯i−t¯i. By the above conclusions, we can get that(10)s¯i−t¯i+s¯i−t¯isi−ti−s¯i−t¯i+s¯i−t¯i24≤si−ti2,(11)si−ti2≤s¯i−t¯i+s¯i−t¯isi−ti−s¯i−t¯is¯i−t¯i.By (8)–(11), it follows that(12)gsi,ti=12si2+ti2−si−ti2≥12s¯i+s¯isi−s¯i+s¯i24+12t¯i+t¯iti−t¯i+t¯i24−12s¯i−t¯i+s¯i−t¯isi−ti−s¯i−t¯is¯i−t¯i=12t¯i+t¯isi+s¯i+s¯iti−t¯i+t¯i24−s¯i+s¯i24+s¯i−t¯is¯i−t¯i=glsi,ti,gsi,ti=12si2+ti2−si−ti2≤12s¯i+s¯isi−s¯is¯i+t¯i+t¯iti−t¯it¯i−12s¯i−t¯i+s¯i−t¯isi−ti−s¯i−t¯i+s¯i−t¯i24=12s¯i+s¯iti+t¯i+t¯isi+s¯i−t¯i+s¯i−t¯i24−s¯is¯i−t¯it¯i=gusi,ti.Thus, we have that(13)glsi,ti≤gsi,ti≤gusi,ti.In the following, for anys∈H⊆H0,t∈T0, without loss of generality, we define the function(14)fLs,t=∑i=1ncisi+∑i=1nglsi,ti.By the above conclusions, for anys∈H⊆H0,t∈T0, it is obvious that we have(15)fLs,t≤fs,t.Thus, based on the former discussions, we can construct the corresponding LRPP of the EBOP as follows:(16)LRPP:minfLs,t=∑i=1ncisi+∑i=1nglsi,ti,s.t.As≤b,ti=∑k=1nΘiksk,i=1,2,…,n,s∈H,t∈T0.Remark 1.
Based on the above constructing method of the LRPP, it is obvious that each feasible solution of the IQPP over subrectangleH is also feasible to the LRPP, and the global optimal value of the LRPP is less than or equal to that of the EBOP over subrectangle H. Thus, the LRPP can provide a reliable lower bound for the global optimal value of the IQPP over subrectangle H.


## 3. New Rectangular Reduction Technique

For improving the convergent speed of the algorithm, in this section, we will construct a new rectangular reduction technique. Without loss of generality, for any rectangleH⊆H0, we want to investigate whether or not H contains the global optimal solution of the EBOP over H0. The detailed discussions are given by Theorem 1.Theorem 1.
Suppose thatUB is a known upper bound of the global optimal value of the EBOP, for any subrectangle H⊆H0; then, we have the following conclusions:(a)
If∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i>UB, then there exists no global optimal solution of the EBOP.(b)
If∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i≤UB, then we get, for each τ∈1,2,…,n, if cτ>0, then the subrectangle H¯=s∈Rn|s¯i≤si≤s¯i,i≠τ;ρτ<sτ≤s¯τ does not include any global optimal solution of the EBOP; if cτ<0, then the subrectangle H¯¯=s∈Rn|s¯i≤si≤s¯i,i≠τ;s¯τ≤sτ<ρτ does not include any global optimal solution of the EBOP, where(17)ρτ=UB−∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i+mincτs¯τ,cτs¯τcτ,τ=1,…,n,t¯i=mins∈D∩HΘis,t¯i=maxs∈D∩HΘis,i=1,2,…,n.Proof.
(a)
For anys∈H, if ∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i>UB, then we have(18)fs,t=∑i=1ncisi+∑i=1nsiti≥∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i>UB.Therefore, the subrectangleH does not produce the global optimal solution for the EBOP.(b)
If∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i≤UB, for each τ∈1,2,…,n, then we have the following conclusions:(i)
Ifcτ>0, for any s∈H¯, we have sτ>ρτ, that is, cτsτ>UB−∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i+mincτs¯τ,cτs¯τ. Moreover, we can follow that(19)fs,t=∑i=1,i≠τncisi+cτsτ+∑i=1nsiti≥∑i=1,i≠τnmincis¯i,cis¯i+cτsτ+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i>∑i=1,i≠τnmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i+UB−∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i+mincτs¯τ,cτs¯τ=UB.That is, we havefs,t>UB. Therefore, the subrectangle H¯ does not include the global optimal solution of the EBOP.(ii)
: Ifcτ<0, then, for any s∈H¯¯, we have sτ<ρτ, that is, cτsτ>UB−∑i=1nmincis¯i,cis¯i+∑i=1nmins¯it¯i,s¯it¯i,s¯it¯i,s¯it¯i+mincτs¯τ,cτs¯τ. Similar to the proof of the above case (i), it follows that fs,t>UB; thus, the subrectangle H¯¯ does not include the global optimal solution of the EBOP, and the proof is completed. □
From Theorem1, we can construct a rectangular reduction technique to delete a part of the investigated subrectangle H, which does not include the global optimal solution of the EBOP.


## 4. New Branch-and-Reduction Algorithm

In this section, combining the former LRPP and the rectangular reduction technique, we will construct a new branch-and-reduction algorithm to globally solve the IQPP.


### 4.1. Branching Method

In this paper, we will adopt a standard rectangular bisection method, which is adequate to guarantee the global convergence of the proposed algorithm; the detailed branching idea is given as follows.Consider the selected subrectangleH′=s¯′,s¯′⊆H0, and denote by q∈argmaxs¯i′−s¯i′:i=1,2,…,n; then, we can partition H′ into two subrectangles H1′ and H2′ by subdividing s¯q′,s¯q′ into s¯q′,s¯q′+s¯q′/2 and s¯q′+s¯q′/2,s¯q′. By the above branching idea, we can see that the interval t¯′,t¯′ of t never is partitioned by the branching operation; it is to say, the branching process only takes place in a space of n dimension.


### 4.2. Branch-and-Reduction Algorithm

Without loss of generality, we assume thatfLsrH,trH and srH,trH be the global optimal value and the global optimal solution of the problem (LRPP) over the subrectangle H, respectively. Combining the former linear relaxation method and branching method with the rectangular reduction technique together, we can establish a branch-and-reduction algorithm for globally solving the IQPP as follows:(i)
Branch-and-reduction algorithm:(ii)
Step 0 (initialization). Initializek:=0, Λ0=H0, ε=10−6, and F:=∅.(iii)
Solve the LRPP overH0 to obtain its corresponding optimal solution s0:=sH0, t0:=tH0 and optimal value LB0:=fLs0,t0. Let UB=fs0,t0 and F=F∪s0,t0. If UB−LB0≤ε, then the algorithm stops, and we get that s0,t0 is an ε−global optimum solution for the IQPP. Otherwise, proceed with Step 1.(iv)
Step 1 (regional reduction). For each selected subrectangleHk, use the former rectangular reduction technique of Section 3 to compress its range and still denote by the remaining subrectangle Hk.(v)
Step 2 (regional partition). Partitioning the selected rectangleHk into two new subrectangles, denote by the set of new subdivided subrectangles H^k.(vi)
Step 3 (updating the lower bound and the upper bound). For eachH∈H^k, solve the LRPP over H to obtain its corresponding optimal value fLsrH,trH and optimal solution srH,trH. Let LBH:=fLsrH,trH. If LBH>UB, then let H^k:=H^k∖H. Denote bythe residual partitioning set Λk:=Λk∖Hk∪H^k, and update the lower bound by LBk:=infH∈ΛkLBH.(vii)
If the midpointsmid of H is feasible to the EBOP, then let tmid=Qsmid and F:=F∪smid,tmid. Moreover, since srH,trH is always feasible to the EBOP, we let F:=F∪srH,trH.(viii)
At the same time, we update the upper bound byUB:=mins,t∈Ffs,t, and denote by the known best feasible solution sbest,tbest≔argmins,t∈Ffs,t.(ix)
Step 4 (termination judgment). IfUB−LBk≤ε, the algorithm stops, and UB and sbest are the ε−global optimal value and the global optimal solution of the IQPP, respectively. Otherwise, let k:=k+1, select a new active node Hk+1 satisfying Hk+1=argminH∈ΛkLBH, and return to step 1.


### 4.3. Global Convergence of the Proposed Algorithm

In the section, the global convergence of the proposed algorithm is discussed as follows.If the proposed algorithm terminates going through finite iterations, without loss of generality, we assume that it terminates at thekth iteration, k≥0. By steps of the former algorithm, we can obtain that UB−LBk≤ε. By the method of the updating upper bound, there must exist a feasible solution s∗ of the IQPP such that UB=gs∗. By the structure of the branch-and-reduction algorithm, we have that LBk≤v. Since s∗ is a feasible solution for the IQPP, it follows that fs∗≥v. Combining the above inequalities and equalities together, it follows that v≤fs∗≤LBk+ε≤v+ε. Thus, we can get that s∗ is a global ε− optimum solution for the IQPP. If the proposed algorithm does not terminate after finite iterations, then we have the following conclusions.Theorem 2.
(i)
The functional differences△si,ti=gsi,ti−glsi,ti⟶0and△¯si,ti=gusi,ti−gsi,ti⟶0,ass¯−s¯⟶0.(ii)
The functional differencefs,t−fLs,t⟶0ass¯−s¯⟶0.(iii)
If the proposed algorithm does not finitely terminate, then the proposed algorithm generates an infinite sequencesk of which any accumulation point will be a global optimal solution of the IQPP.Proof.
(i)
Without loss of generality, we define the following functional differences:(20)△si=gsi−glsi,△¯si=gusi−gsi,△ti=gti−glti,△¯ti=guti−gti.(ii)
Since△si is a convex function of si over s¯i,s¯i, it follows that △si can attain maximum value at the point s¯i or s¯i. Then,(21)maxsi∈s¯i,s¯i△si=gs¯i−gls¯i=gs¯i−gls¯i=s¯i−s¯i24.(iii)
On the other hand, since△si is a concave function of si over s¯i,s¯i , △si can attain maximum value at the point, that is,(22)maxsi∈s¯i,s¯i△¯si=gus¯i+s¯i2−gs¯i+s¯i2=s¯i−s¯i24.(iv)
So, we have(23)maxsi∈s¯i,s¯i△si=maxsi∈s¯i,s¯i△¯si⟶0,ass¯i−s¯i⟶0.(v)
That is to say,△si,△¯si⟶0,ass¯−s¯⟶0.(vi)
Similar to the above proof, we can also prove that(24)maxti∈t¯i,t¯i△ti=maxti∈t¯i,t¯i△¯ti⟶0,ast¯i−t¯i⟶0.(vii)
And△ti,△¯ti⟶0,ast¯−t¯⟶0. Also, since t¯−t¯⟶0ass¯−s¯⟶0, therefore we have(25)maxti∈t¯i,t¯i△ti=maxti∈t¯i,t¯i△¯ti⟶0,ass¯−s¯⟶0.(viii)
Define(26)△si−ti=si−ti2−12t¯i+t¯isi+s¯i+s¯iti−t¯i+t¯i24−s¯i+s¯i24+s¯i−t¯is¯i−t¯i,△¯si−ti=12t¯i+t¯isi+s¯i+s¯iti−s¯is¯i−t¯it¯i+s¯i−t¯i+s¯i−t¯i24−si−ti2.(ix)
Using similar methods to the above proof, we can draw the following conclusions, ass¯−s¯⟶0:(27)maxsi−ti∈s¯i−t¯i,s¯i−t¯i△si−ti=maxsi−ti∈s¯i−t¯i,s¯i−t¯i△¯si−ti⟶0.(x)
Consider(28)△si,ti=gsi,ti−glsi,ti=siti−12s¯i+s¯iti+t¯i+t¯isi−s¯i+s¯i24−t¯i+t¯i24+s¯i−t¯is¯i−t¯i=12si2+ti2−si−ti2−12s¯i+s¯iti+t¯i+t¯isi−s¯i+s¯i24−t¯i+t¯i24+s¯i−t¯is¯i−t¯i=12si2+ti2−si−ti2−12s¯i+s¯isi−s¯i+s¯i24+t¯i+t¯iti−t¯i+t¯i24+12s¯i−t¯i+s¯i−t¯isi−ti−s¯i−t¯is¯i−t¯i=12si2−s¯i+s¯isi−s¯i+s¯i24+12ti2−t¯i+t¯iti−t¯i+t¯i24+12s¯i−t¯i+s¯i−t¯isi−ti−s¯i−t¯is¯i−t¯i−si−ti2=12△si+12△ti+12△¯si−ti≤12maxsi∈s¯i,s¯i△si+12maxti∈t¯i,t¯i△ti+12maxsi−ti∈s¯i−t¯i,s¯i−t¯i△¯si−ti.(xi)
From (23)–(27), we follow that(29)△si,ti⟶0ass¯−s¯⟶0.(xii) Similarly, we can prove that△si,ti⟶0ass¯−s¯⟶0.(xiii)
By conclusion (i), we have(30)fs,t−fLs,t=∑k=1ncisi+∑k=1nsiti−∑k=1ncisi+∑k=1nglsi,ti=∑k=1ngsi,ti−glsi,ti=∑k=1n△si,ti.(xiv)
By (29), we have that △si,ti⟶0, as s¯−s¯⟶0.(xv)erefore, we have that(31)fs,t−fLs,t⟶0ass¯−s¯⟶0.(xvi)
When the algorithm is infinite, first of all, by the exhaustiveness of the bisection method, we have that(32)limk⟶∞s¯k−s¯k=0.
Secondly, by conclusions (i) and (ii) of the theorem, sincelimk⟶∞s¯k−s¯k⟶0, it follows that limk⟶∞UB−LBk=0; therefore, the bounding operation is consistent.
By Theorem 4.3 in [25], the sufficient condition of the global convergence of the branch-and-reduction algorithm is satisfied. Therefore, the algorithm is globally convergent to the optimal solution of the IQPP. □


### 4.4. Computational Complexity of the Algorithm

Definition 1.
Assume thatH=s¯1,s¯1×⋯×s¯n,s¯n⊂Rn be a compact subhyperrectangle, the diameter of the hyperrectangle H⊂Rn is defined by(33)δH=maxα−α′2:α,α′∈H=s¯1−s¯12+⋯+s¯n−s¯n2.Theorem 3.
For the proposed branch-and-reduction algorithm, for any given subhyperrectangleH, without loss of generality, we assume that there exist a fixed positive constant C and a given accuracy error ϵ and assume that the branching operation will eventually subdivide the subhyperrectangle H into η=2n the smaller subhyperrectangles. Then, by subdividing the subhyperrectangle H, the number of iterations of the proposed branch-and-reduction algorithm in the worst case can be given as follows:(34)∑i=0r2n.i,wherer=log2C.δHɛ,δH=maxδHl:l∈1,2,…,η.
We callOn=∑t=0r2n.i to be the convergence rate of the branch-and-reduction algorithm by subdividing space Rn.Proof.
The proof of the theorem is similar to Theorem 5 in Liu et al. [41]; thus, it is omitted here.Remark 2.
From the above discussions, we know thatOn is a function of exponential growth, the branch-and-bound search of the proposed algorithm takes place in space Rn. Therefore, the proposed algorithm has the same computational complexity as that of [12, 21–23, 26].


## 4.1. Branching Method

In this paper, we will adopt a standard rectangular bisection method, which is adequate to guarantee the global convergence of the proposed algorithm; the detailed branching idea is given as follows.Consider the selected subrectangleH′=s¯′,s¯′⊆H0, and denote by q∈argmaxs¯i′−s¯i′:i=1,2,…,n; then, we can partition H′ into two subrectangles H1′ and H2′ by subdividing s¯q′,s¯q′ into s¯q′,s¯q′+s¯q′/2 and s¯q′+s¯q′/2,s¯q′. By the above branching idea, we can see that the interval t¯′,t¯′ of t never is partitioned by the branching operation; it is to say, the branching process only takes place in a space of n dimension.


## 4.2. Branch-and-Reduction Algorithm

Without loss of generality, we assume thatfLsrH,trH and srH,trH be the global optimal value and the global optimal solution of the problem (LRPP) over the subrectangle H, respectively. Combining the former linear relaxation method and branching method with the rectangular reduction technique together, we can establish a branch-and-reduction algorithm for globally solving the IQPP as follows:(i)
Branch-and-reduction algorithm:(ii)
Step 0 (initialization). Initializek:=0, Λ0=H0, ε=10−6, and F:=∅.(iii)
Solve the LRPP overH0 to obtain its corresponding optimal solution s0:=sH0, t0:=tH0 and optimal value LB0:=fLs0,t0. Let UB=fs0,t0 and F=F∪s0,t0. If UB−LB0≤ε, then the algorithm stops, and we get that s0,t0 is an ε−global optimum solution for the IQPP. Otherwise, proceed with Step 1.(iv)
Step 1 (regional reduction). For each selected subrectangleHk, use the former rectangular reduction technique of Section 3 to compress its range and still denote by the remaining subrectangle Hk.(v)
Step 2 (regional partition). Partitioning the selected rectangleHk into two new subrectangles, denote by the set of new subdivided subrectangles H^k.(vi)
Step 3 (updating the lower bound and the upper bound). For eachH∈H^k, solve the LRPP over H to obtain its corresponding optimal value fLsrH,trH and optimal solution srH,trH. Let LBH:=fLsrH,trH. If LBH>UB, then let H^k:=H^k∖H. Denote bythe residual partitioning set Λk:=Λk∖Hk∪H^k, and update the lower bound by LBk:=infH∈ΛkLBH.(vii)
If the midpointsmid of H is feasible to the EBOP, then let tmid=Qsmid and F:=F∪smid,tmid. Moreover, since srH,trH is always feasible to the EBOP, we let F:=F∪srH,trH.(viii)
At the same time, we update the upper bound byUB:=mins,t∈Ffs,t, and denote by the known best feasible solution sbest,tbest≔argmins,t∈Ffs,t.(ix)
Step 4 (termination judgment). IfUB−LBk≤ε, the algorithm stops, and UB and sbest are the ε−global optimal value and the global optimal solution of the IQPP, respectively. Otherwise, let k:=k+1, select a new active node Hk+1 satisfying Hk+1=argminH∈ΛkLBH, and return to step 1.


## 4.3. Global Convergence of the Proposed Algorithm

In the section, the global convergence of the proposed algorithm is discussed as follows.If the proposed algorithm terminates going through finite iterations, without loss of generality, we assume that it terminates at thekth iteration, k≥0. By steps of the former algorithm, we can obtain that UB−LBk≤ε. By the method of the updating upper bound, there must exist a feasible solution s∗ of the IQPP such that UB=gs∗. By the structure of the branch-and-reduction algorithm, we have that LBk≤v. Since s∗ is a feasible solution for the IQPP, it follows that fs∗≥v. Combining the above inequalities and equalities together, it follows that v≤fs∗≤LBk+ε≤v+ε. Thus, we can get that s∗ is a global ε− optimum solution for the IQPP. If the proposed algorithm does not terminate after finite iterations, then we have the following conclusions.Theorem 2.
(i)
The functional differences△si,ti=gsi,ti−glsi,ti⟶0and△¯si,ti=gusi,ti−gsi,ti⟶0,ass¯−s¯⟶0.(ii)
The functional differencefs,t−fLs,t⟶0ass¯−s¯⟶0.(iii)
If the proposed algorithm does not finitely terminate, then the proposed algorithm generates an infinite sequencesk of which any accumulation point will be a global optimal solution of the IQPP.Proof.
(i)
Without loss of generality, we define the following functional differences:(20)△si=gsi−glsi,△¯si=gusi−gsi,△ti=gti−glti,△¯ti=guti−gti.(ii)
Since△si is a convex function of si over s¯i,s¯i, it follows that △si can attain maximum value at the point s¯i or s¯i. Then,(21)maxsi∈s¯i,s¯i△si=gs¯i−gls¯i=gs¯i−gls¯i=s¯i−s¯i24.(iii)
On the other hand, since△si is a concave function of si over s¯i,s¯i , △si can attain maximum value at the point, that is,(22)maxsi∈s¯i,s¯i△¯si=gus¯i+s¯i2−gs¯i+s¯i2=s¯i−s¯i24.(iv)
So, we have(23)maxsi∈s¯i,s¯i△si=maxsi∈s¯i,s¯i△¯si⟶0,ass¯i−s¯i⟶0.(v)
That is to say,△si,△¯si⟶0,ass¯−s¯⟶0.(vi)
Similar to the above proof, we can also prove that(24)maxti∈t¯i,t¯i△ti=maxti∈t¯i,t¯i△¯ti⟶0,ast¯i−t¯i⟶0.(vii)
And△ti,△¯ti⟶0,ast¯−t¯⟶0. Also, since t¯−t¯⟶0ass¯−s¯⟶0, therefore we have(25)maxti∈t¯i,t¯i△ti=maxti∈t¯i,t¯i△¯ti⟶0,ass¯−s¯⟶0.(viii)
Define(26)△si−ti=si−ti2−12t¯i+t¯isi+s¯i+s¯iti−t¯i+t¯i24−s¯i+s¯i24+s¯i−t¯is¯i−t¯i,△¯si−ti=12t¯i+t¯isi+s¯i+s¯iti−s¯is¯i−t¯it¯i+s¯i−t¯i+s¯i−t¯i24−si−ti2.(ix)
Using similar methods to the above proof, we can draw the following conclusions, ass¯−s¯⟶0:(27)maxsi−ti∈s¯i−t¯i,s¯i−t¯i△si−ti=maxsi−ti∈s¯i−t¯i,s¯i−t¯i△¯si−ti⟶0.(x)
Consider(28)△si,ti=gsi,ti−glsi,ti=siti−12s¯i+s¯iti+t¯i+t¯isi−s¯i+s¯i24−t¯i+t¯i24+s¯i−t¯is¯i−t¯i=12si2+ti2−si−ti2−12s¯i+s¯iti+t¯i+t¯isi−s¯i+s¯i24−t¯i+t¯i24+s¯i−t¯is¯i−t¯i=12si2+ti2−si−ti2−12s¯i+s¯isi−s¯i+s¯i24+t¯i+t¯iti−t¯i+t¯i24+12s¯i−t¯i+s¯i−t¯isi−ti−s¯i−t¯is¯i−t¯i=12si2−s¯i+s¯isi−s¯i+s¯i24+12ti2−t¯i+t¯iti−t¯i+t¯i24+12s¯i−t¯i+s¯i−t¯isi−ti−s¯i−t¯is¯i−t¯i−si−ti2=12△si+12△ti+12△¯si−ti≤12maxsi∈s¯i,s¯i△si+12maxti∈t¯i,t¯i△ti+12maxsi−ti∈s¯i−t¯i,s¯i−t¯i△¯si−ti.(xi)
From (23)–(27), we follow that(29)△si,ti⟶0ass¯−s¯⟶0.(xii) Similarly, we can prove that△si,ti⟶0ass¯−s¯⟶0.(xiii)
By conclusion (i), we have(30)fs,t−fLs,t=∑k=1ncisi+∑k=1nsiti−∑k=1ncisi+∑k=1nglsi,ti=∑k=1ngsi,ti−glsi,ti=∑k=1n△si,ti.(xiv)
By (29), we have that △si,ti⟶0, as s¯−s¯⟶0.(xv)erefore, we have that(31)fs,t−fLs,t⟶0ass¯−s¯⟶0.(xvi)
When the algorithm is infinite, first of all, by the exhaustiveness of the bisection method, we have that(32)limk⟶∞s¯k−s¯k=0.
Secondly, by conclusions (i) and (ii) of the theorem, sincelimk⟶∞s¯k−s¯k⟶0, it follows that limk⟶∞UB−LBk=0; therefore, the bounding operation is consistent.
By Theorem 4.3 in [25], the sufficient condition of the global convergence of the branch-and-reduction algorithm is satisfied. Therefore, the algorithm is globally convergent to the optimal solution of the IQPP. □


## 4.4. Computational Complexity of the Algorithm

Definition 1.
Assume thatH=s¯1,s¯1×⋯×s¯n,s¯n⊂Rn be a compact subhyperrectangle, the diameter of the hyperrectangle H⊂Rn is defined by(33)δH=maxα−α′2:α,α′∈H=s¯1−s¯12+⋯+s¯n−s¯n2.Theorem 3.
For the proposed branch-and-reduction algorithm, for any given subhyperrectangleH, without loss of generality, we assume that there exist a fixed positive constant C and a given accuracy error ϵ and assume that the branching operation will eventually subdivide the subhyperrectangle H into η=2n the smaller subhyperrectangles. Then, by subdividing the subhyperrectangle H, the number of iterations of the proposed branch-and-reduction algorithm in the worst case can be given as follows:(34)∑i=0r2n.i,wherer=log2C.δHɛ,δH=maxδHl:l∈1,2,…,η.
We callOn=∑t=0r2n.i to be the convergence rate of the branch-and-reduction algorithm by subdividing space Rn.Proof.
The proof of the theorem is similar to Theorem 5 in Liu et al. [41]; thus, it is omitted here.Remark 2.
From the above discussions, we know thatOn is a function of exponential growth, the branch-and-bound search of the proposed algorithm takes place in space Rn. Therefore, the proposed algorithm has the same computational complexity as that of [12, 21–23, 26].


## 5. Numerical Experiment

To validate the computational performance of the algorithm, several numerical examples are used to test the algorithm. This algorithm is implemented in MATLAB 2014a software in a notebook computer with Intel (R) Core (TM) i7-6700HQ CPU@2.6 GHz Processor, 12 GB RAM Memory, and Win10 Operational System. In the MATLAB program, all linear programming problems are solved by linprog solver, and we set the convergent errorε=10−6. For all numerical examples 1–12, compared with the current known algorithms in recent literature, numerical results are listed in Tables 1 and 2. In Table 1, “Iter” denotes the number of iterations.Table 1
Numerical comparisons for test examples1–11.
ExamplesMethodsOptimal valueOptimal solutionIterTime (s)1Ours10.0000(2.0000, 8.0000)5914.9847[12]10.0000(2.0000, 8.0000)5615.8054[20]10.0000(2.0000, 8.0000)410.4856[21]10.0000(2.0000, 8.0000)2710.9297[22]10.0000(2.0000, 8.0000)530.3278SCIP solver10.0000(2.0000, 8.0000)10.31772Ours3.00000(0.0000, 4.0000)7116.4324[12]3.00000(0.0000, 4.0000)6817.9814[23]3.00000(0.0000, 4.0000)252.4936SCIP solver3.00000(0.0000, 4.0000)10.06783Ours0.87016(1.3148, 0.1396, 0.0, 0.4233)10.2889[12]0.87016(1.3148, 0.1396, 0.0, 0.4233)10.3894[22]0.8902(1.3148, 0.1396, 0.0, 0.4233)10.5432SCIP solver0.8902(1.3148, 0.1396, 0.0, 0.4233)110.29124Ours−16.22662(0.0, 3.6403, 0.0, 2.9029, 1.9388, 0.0)10.5949[12]−16.22662(0.0, 3.6403, 0.0, 2.9029, 1.9388, 0.0)10.7498SCIP solver−16.2266(0.0, 3.6403, 0.0, 2.9029, 1.9388, 0.0)10.08825Ours−3.00000(3.0000, 3.0000)326.2275[12]−3.00000(3.0000, 3.0000)306.3380SCIP solver−3.00000(3.0000, 3.0000)50.24386Ours−1.06250(0.7500, 2.0000)20.4150[12]−1.06250(0.7500, 2.0000)20.5638SCIP solver−1.0625(0.7500, 2.0000)10.11297Ours10(2, 8)184.5829[26]10(2, 8)30.6745SCIP solver10(2, 8)10.03698Ours4(0, 0)10.2276[26]4(0, 0)20.4219SCIP solver4(0, 0)10.12039Ours−4558(27, 20)357.4568SCIP solver−4558(27, 20)10.035910Ours2.39991(0.5828, 0.6969, 0.7515, 0.2685)10.5809SCIP solver2.39991(0.5828, 0.6969, 0.7515, 0.2685)110.618611Ours6.96376(0.7767, 0.7497, 0.9079, 0.0532)10.5354SCIP solver6.96376(0.7767, 0.7497, 0.9079, 0.0532)140.6093Table 2
Comparison of numerical results for example12.
(n,m)Ge and Liu [12]Our algorithmSCIP SolverAvg.NTAvg.TimeAvg.NTAvg.TimeAvg.NTAvg.Time(5, 5)1.20.51301.00.259225.90.7789(10, 10)1.21.15211.00.8972606.913.7890(15, 10)1.34.69581.22.89756250.464.2376(15, 15)1.34.79531.22.9978−−(20, 20)1.38.89761.38.8840−−(30, 30)1.38.91891.38.9678−−(40, 40)1.28.46781.28.4076−−(50, 50)2.521.45892.319.4939−−(80, 80)2.433.46782.231.8257−−(100, 50)3.629.38493.524.9980−−(100, 100)5.464.89374.259.5274−−(200, 20)3.228.78963.126.3436−−(200, 50)3.242.45683.140.4673−−(300, 50)3.589.89473.379.7875−−(300, 100)4.8436.34204.3365.8972−−(500, 50)3.5196.38763.5193.8970−−(1000, 50)3.31200.78563.21154.5867−−Examples1–11 are all deterministic examples with the quadratic objective function, which have deterministic global optimal solutions and optimal values. Moreover, examples 1-11 are all nonconvex optimization problems; they have multiple local minima that are not global optimal. Example 12 is a large-scale random example with large-size variables and constraints.Example 1.
(see [12, 20–22]).(35)mins1+s2s1−s2+7s.t.2s1+s2≤14,s1+s2≤10,−4s1+s2≤0,2s1+s2≥6,s1+2s2≥6,s1−s2≤3,s1≤5,s1+s2≥0,s1−s2+7≥0.Example 2.
(see [12, 23]).(36)mins1+2s1−3s2+13s1+s2−1s.t.−s1+2s2≤8,−s2≤−3,s1+2s2≤12,s1−2s2≤−5,s1,s2≥0.Example 3.
(see [12, 22]).(37)min0.813396s1+0.67440s2+0.305038s3+0.129742s4+0.217796×0.224508s1+0.063458s2+0.932230s3+0.528736s4+0.091947s.t.0.488509s1+0.063565s2+0.945686s3+0.210704s4≤3.562809,−0.324014s1−0.501754s2−0.719204s3+0.099562s4≤−0.052215,0.445225s1−0.346896s2+0.637939s3−0.257623s4≤0.427920,−0.202821s1+0.647361s2+0.920135s3−0.983091s4≤0.840950,−0.886420s1−0.802444s2−0.305441s3−0.180123s4≤−1.353686,−0.515399s1−0.424820s2+0.897498s3+0.187268s4≤2.137251,−0.591515s1+0.060581s2−0.427365s3+0.579388s4≤−0.290987,0.423524s1+0.940496s2−0.437944s3−0.742941s4≤0.373620,s1≥0,s2≥0,s3≥0,s4≥0.Example 4.
(see [12]).(38)min6.5s1−0.5s12−s2−2s3−3s4−2s5−s6s.t.s1+2s2+8s3+s4+3s5+5s6≤16,−8s1−4s2−2s3+2s4+4s5−s6≤−1,2s1+0.5s2+0.2s3−3s4−s5−4s6≤24,0.2s1+2x2+0.1s3−4s4+2s5+2s6≤12,−0.1s1−0.5s2+2s3+5s4−5s5+3s6≤3,0≤si≤10,i=1,2,…,6.Example 5.
(see [12]).(39)min2s1+3s2−2s12−2s22+2s1s2s.t.−s1+s2≤1,s1−s2≤1,−s1+2s2≤3,2s1−s2≤3,0≤s1≤15,0≤s2≤15.Example 6.
(see [12]).(40)minsTQs+cTss.t.As≤b,s∈S0=0≤s1≤2,0≤s2≤2,where(41)c=2,4T,b=1,2,4,3,1T,Q=−122−4,A=−420111101−4.Example 7.
(see [26]).(42)mins1+s2s1−s2+7s.t.2s1+s2≤14,s1+s2≤10,−4s1+s2≤0,2s1+s2≥6,s1+2s2≥6,s1−s2≤3,1.99≤s1≤2.01,7.99≤s2≤8.01.Example 8.
(see [26]).(43)min6s1+s2+1s1+2s2+1+−s1+3s1+s2+1s.t.−2s1+s2≤0,s1≤2.5,s1+s2≤8,s1,s2≥0.Example 9.
(see [26]).(44)mins1+2s2−2−2s1−s2+3+3s1−2s2+3s1−s2−1s.t.−2s1+3s2≤6,4s1−5s2≤8,4s1−3s2≤−12,s1,s2≥0.Example 10.
(45)minsTQs+cTs+ds.t.As≤b,si≥0,i=1,…,4,where(46)Q=0.20510.21690.46000.25600.21690.10630.79010.44680.46000.79010.28440.14110.25600.44680.14110.0686,b=4.562809,−1.052215,0.427920,0.840950,−1.353686,2.137251,−0.290987,0.373620T,c=0.1329,0.1678,0.2311,0.1271T,d=0.02,A=0.5885090.0635650.9456860.210704−0.324014−0.501754−0.7192040.0995620.445225−0.3468960.637939−0.257623−0.2028210.6473610.920135−0.983091−0.886420−0.802444−0.305441−0.180123−0.515399−0.4248200.8974980.187268−0.5915150.060581−0.4273650.5793880.4235240.940496−0.437944−0.742941.Example 11.
(47)minsTQs+cTss.t.As≤b,si≥0,i=1,…,4,where(48)Q=0.42960.36091.03840.63270.36090.16971.28800.74291.03841.28801.21660.87160.63270.74290.87160.5973,b=5.562809,−2.052215,1.427920,1.840950,−2.353686,3.137251,−1.290987,1.373620T,c=0.4493,0.3232,1.2553,0.7478T,d=0.1120,A=1.5885090.0635650.9456860.210704−1.324014−0.501754−0.7192040.0995621.445225−0.3468960.637939−0.257623−1.2028210.6473610.920135−0.983091−1.886420−0.802444−0.305441−0.180123−1.515399−0.4248200.8974980.187268−1.5915150.060581−0.4273650.5793881.4235240.940496−0.437944−0.742941.
A randomly generated test example12 with a large scale of variables and constraints is used to validate the robustness and effectiveness of this algorithm; the randomly generated problems are listed as follows and its computational results are listed in Table 2:Example 12.
(see [12]).(49)minsTQs+cTss.t.As≤b,s∈S0=−10≤si≤10,i=1,2,…,n,where Q is an n×n real symmetric matrix, A is an m×n real symmetric matrix, c∈Rn, and b∈Rm; all elements of Q, A, and c are randomly generated from −2,2; all elements of b are randomly generated in 1,10. Obviously, Q may be a positive semidefinite matrix; that is to say, the randomly generated test example 12 may be a nonconvex quadratic programming problem.
For example12, we solve 10 different random examples with the same parameters and present the numerical results in Table 2. Several notations have been used in column headers of Table 2: Ave.NT denote the average number of iterations; Avg.Time (s) denotes the average CPU execution time of this algorithm in seconds; m denotes the number of constraints; and n denotes the number of variables. In addition, in Table 2, “−” denotes the situation that some of the ten random instances failed to terminate in 3600s.
It should be noted that, in Tables1 and 2, since the existing algorithm in the literature [12, 20–24, 26] and the algorithm proposed in this paper use branch-and-bound relaxation structure, we compare our algorithm with the algorithm in the literature [12, 20–24, 26]. In Tables 1 and 2, the software “SCIP” is a commercial solver, which can be used to obtain the global optimal solutions of examples 1-12, so we give the computational comparisons among the proposed algorithm and the commercial solver “SCIP”.
From the numerical results of Table1, we can follow that, for the deterministic examples 1-11, the proposed algorithm in this paper can obtain the same global optimal solution and optimal value as the existing algorithms [12, 20–24, 26] and the commercial solver “SCIP”. In addition, when n≤3, the commercial solver “SCIP” has higher computational efficiency with less iterations and computation time. But, when n≥4, the computational performance of the proposed branch-and-reduction algorithm is significantly higher than that of commercial solver “SCIP”.
From the numerical results of Table2, with any given convergent error, we can follow that the proposed branch-and-reduction algorithm can be used to globally solve the IQPP with a large scale of constraints and variables. From Table 2, when m and n are less than 50, it can be seen that the algorithm can find the global optimal solution of the IQPP with a short time and a smaller number of iterations. As the problem size increases, the Ave.NT and the Avg.Time (s) also increase, but they are not very sensitive to the size of the IQPP.
From numerical results in Table2, for randomly generated large-size test example 12, compared with the algorithm of [12] and the commercial solver “SCIP”, the proposed branch-and-reduction algorithm has the higher computational efficiency. Especially with the increase of the scale of example 12, our algorithm is superior to the known commercial solver “SCIP”; this is because the commercial solver “SCIP” failed to terminate in 3600s, but the proposed algorithm can find the corresponding global optimal solution of each randomly generated large-size test instance.
In all, from the numerical results in Tables1 and 2, we can also draw the following conclusions: when the number of variables n≤3, the commercial solver “SCIP” has higher computational efficiency than the present algorithm in this paper. But when the number of variables n≥4, the present algorithm in this paper has higher computational efficiency than the commercial solver “SCIP.” Furthermore, from the numerical results of example 12, when the number of variables n≥5, the present algorithm in this paper has significantly higher computational efficiency than the commercial solver “SCIP”. In addition, with the increase of the scale of the IQPP, the proposed algorithm is superior to the known commercial solver “SCIP” for solving the IQPP. In all, from the numerical results in Tables 1 and 2, when the scale of the problem is small, for example, the number of variables being less than or equal to 2, the commercial solver is more efficient than the proposed algorithm in this paper, but when the number of variables is greater than or equal to 5, the present algorithm has an obvious advantage over the commercial solver “SCIP”. Especially when n is greater than or equal to 15, the SCIP solver failed to terminate in 3600s. Therefore, the proposed algorithm in this paper highly outperforms the commercial solver “SCIP” in computational performance.


## 6. Concluding Remarks

In this paper, we present and validate a novel rectangular branch-and-reduction algorithm for the IQPP. First of all, we transform the IQPP into the EBOP; then by utilizing the characters of quadratic function, we can construct a novel linearizing technique, and by utilizing the linearizing technique, we can derive the LRPP of the EBOP, which can be used to compute the lower bound of the global optimal value of the IQPP. For improving the convergent speed of the algorithm, a new rectangular reduction technique is introduced or constructed. And combining the constructed rectangular reduction technique with the LRPP in a branch-and-bound framework, a new rectangular branch-and-reduction algorithm is established. In order to obtain a global optimal solution of the EBOP, the main computational works of the algorithm involve solving a sequence of LRPP. Finally, the global convergent property of the algorithm is derived, and comparing with the known algorithms, numerical computational results demonstrate the higher computational efficiency and the better computational performance of the algorithm.In the future, the proposed linear relaxation method and the rectangular reduction method can be extended and applied to solve the generalized linear multiplicative programming problem, the integer quadratic programming problem, and the integer generalized linear multiplicative programming problem.



---

*Source: 5578427-2021-03-30.xml*