| Algorithm 1 A Spatial Branch-and-Bound Algorithm for Solving (QCQP) |
|
Require: An instance of (QCQP) and a given error tolerance $ \epsilon>0 $. Set iteration step $ p=1 $.
1: Solve (wj-Bound}) for $ l^0 $ and $ u^0 $. 2: If (wj-Bound) is infeasible, then 3: (QCQP) is infeasible and terminate. 4: end if 5: Solve (LowSDP) with $ [l^0, u^0] $ for its optimal value $ {lb}^0 $ and optimal solution $ (w^0,v^0,W^0) $. Let $ U^*=f\Big(F \begin{bmatrix} {w^{0}} \\ {v^{0}} \end{bmatrix}\Big) $ and $ x^*=F \begin{bmatrix} {w^{0}} \\{v^{0}} \end{bmatrix} $. 6: Construct a set $ \mathcal{D} $ and insert $ \{w^0,v^0,W^0,lb^0,l^0,u^0\} $ into it. 7: loop 8: If $ \mathcal{D}= \emptyset $, then 9: return $ (x^*,U^*) $ and terminate. 10: end if 11: Choose a problem from $ \mathcal{D} $ using the node selection strategy, denoted as $ \{w^p,v^p,W^p,lb^p,l^p,u^p\} $ such that $ lb^p=\min\{lb^k|lb^k \in \mathcal{D}\} $. Delete it from $ \mathcal{D} $. 12: if $ U^*-lb^p \leq \varepsilon $, then 13: return $ (x^*,U^*) $ and terminate. 14: end if 15: Set $ p\leftarrow p+1 $. 16: Choose $ j^* $ by the variable selection strategy. 17: Set $ l^a=l^p $, $ u^a=u^p $, $ u_{j^*}^a=\frac{l_{j^*}^p+u_{j^*}^p}{2} $, $ l^b=l^p $, $ u^b=u^p $, $ l_{j^*}^b=\frac{l_{j^*}^p+u_{j^*}^p}{2}. $ 18: if (LowSDP) with $ [l^a, u^a] $ is feasible, then 19: Solve (LowSDP) with $ [l^a, u^a] $ for its optimal value $ {lb}^a $ and optimal solution $ (w^a,v^a,W^a) $ and denote $ ub^a=f\Big(F \begin{bmatrix} {w^{a}} \\{v^{a}} \end{bmatrix}\Big) $. 20: if $ ub^a < U^* $, then 21: $ U^*=ub^a $ and $ x^*=F \begin{bmatrix}{w^{a}} \\{v^{a}} \end{bmatrix} $. 22: end if 23: if $ U^*-lb^a > \varepsilon $, then 24: insert $ \{w^a,v^a,W^a,{lb}^a,l^a,u^a\} $ into $ \mathcal{D} $. 25: end if 26: end if 27: if (LowSDP) with $ [l^b, u^b] $ is feasible, then 28: Solve (LowSDP) with $ [l^b, u^b] $ for its optimal value $ {lb}^b $ and optimal solution $ (w^b,v^b,W^b) $ and denote $ ub^b=f\Big(F \begin{bmatrix} {w^{b}} \\ {v^{b}} \end{bmatrix}\Big) $. 29: If $ ub^b < U^* $, then 30: $ U^*=ub^b $ and $ x^*=F \begin{bmatrix}{w^{b}} \\ {v^{b}} \end{bmatrix} $. 31: end if 32: if $ U^*-lb^b > \varepsilon $, then 33: insert $ \{w^b,v^b,W^b,{lb}^b,l^b,u^b\} $ into $ \mathcal{D} $. 34: end if 35: end if 36: end loop |
-
- AIMS Journals
- AIMS Press Math Journals
-
{{journal.titleEn}}
{{journal.titleEn}}
- Book Series
- {{book.nameEn}}
-
- AIMS Journals
-
{{journal.titleEn}}
{{journal.titleEn}}
- AIMS Press Math Journals
-
{{journal.titleEn}}
{{journal.titleEn}}
- Book Series
- {{book.nameEn}}
DownLoad: 
