# American Institute of Mathematical Sciences

• Previous Article
Formal analysis of the Schulz matrix inversion algorithm: A paradigm towards computer aided verification of general matrix flow solvers
• NACO Home
• This Issue
• Next Article
Quasilinear iterative method for the boundary value problem of nonlinear fractional differential equation
June  2020, 10(2): 165-175. doi: 10.3934/naco.2019046

## Quadratic optimization with two ball constraints

 Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

* Corresponding author: Maziar Salahi

Received  December 2018 Revised  July 2019 Published  September 2019

Fund Project: The authors are grateful to the reviewers for their comments and suggestions and University of Guilan for partially supporting this research

In this paper, the minimization of a general quadratic function subject to two ball constraints, called two ball trust-region subproblem (TBTRS), is studied. It is shown that the global optimal solution can be found by solving two extended trust-region subproblems. Strong duality conditions for two special cases are discussed. Finally, a comparison of results of the new algorithm with the other two recently proposed algorithms and CVX software are presented for several classes of randomly generated test problems.

Citation: Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 165-175. doi: 10.3934/naco.2019046
##### References:

show all references

##### References:
$+$: global solution of $Pc_1$ and $Pc_2$, $\Box$: LNGMs of $Pc_1$ and $Pc_2$
Notations in the tables
 Notation Description n Dimension of problem Den Density of A CPU Run time $F_{TB}$ Objective value of the new algorithm $F_{AD}$ Objective value of ADMM algorithm [2] $F_{SD}$ Objective value of SDP relaxation $F_{SA}$ Objective value of Sakaue et. al's algorithm [25] $x_{TB}^*$ Optimal solution of the new algorithm $x_{SA}^*$ Optimal solution of Sakaue et. al's algorithm [25]
 Notation Description n Dimension of problem Den Density of A CPU Run time $F_{TB}$ Objective value of the new algorithm $F_{AD}$ Objective value of ADMM algorithm [2] $F_{SD}$ Objective value of SDP relaxation $F_{SA}$ Objective value of Sakaue et. al's algorithm [25] $x_{TB}^*$ Optimal solution of the new algorithm $x_{SA}^*$ Optimal solution of Sakaue et. al's algorithm [25]
Comparison of the new algorithm with ADMM algorithm [2] (first class)
 n Den CPU(TBTRS) CPU(ADMM) $F_{TB}-F_{AD}$ 50 1 0.23 0.36 -9.31e-11 100 1 0.28 0.47 -1.39 e-10 200 1 0.55 0.79 2.33e-11 300 1 0.80 1.75 1.86 e-10 400 1 1.58 2.63 4.66e-10 500 1 2.72 3.99 8.73e-10 700 0.1 1.49 5.174 4.54e-10 1000 0.1 3.27 20.64 3.49e-10 2000 0.01 2.48 7.64 2.79e-10 5000 0.001 2.74 6.59 -1.16e-10 10000 0.0001 4.62 7.29 -1.46e-11
 n Den CPU(TBTRS) CPU(ADMM) $F_{TB}-F_{AD}$ 50 1 0.23 0.36 -9.31e-11 100 1 0.28 0.47 -1.39 e-10 200 1 0.55 0.79 2.33e-11 300 1 0.80 1.75 1.86 e-10 400 1 1.58 2.63 4.66e-10 500 1 2.72 3.99 8.73e-10 700 0.1 1.49 5.174 4.54e-10 1000 0.1 3.27 20.64 3.49e-10 2000 0.01 2.48 7.64 2.79e-10 5000 0.001 2.74 6.59 -1.16e-10 10000 0.0001 4.62 7.29 -1.46e-11
Comparison of the new algorithm with Sakaue et. al's algorithm [25] (first class)
 n CPU(TBTRS) CPU(Sakaue et. al's algorithm [25]) $F_{TB}-F_{SA}$ $||x^*_{TB}-x^*_{SA}||$ 5 0.10 0.07 -2.27e-14 3.24e-14 10 0.12 0.46 -1.71e-11 1.45e-13 15 0.23 5.94 -3.87e-12 1.78e-14 20 0.18 33.12 -1.82e-09 8.06e-08 25 0.23 130.96 -2.96e-11 9.50e-14 30 0.22 428.21 -6.58e-09 1.26e-10
 n CPU(TBTRS) CPU(Sakaue et. al's algorithm [25]) $F_{TB}-F_{SA}$ $||x^*_{TB}-x^*_{SA}||$ 5 0.10 0.07 -2.27e-14 3.24e-14 10 0.12 0.46 -1.71e-11 1.45e-13 15 0.23 5.94 -3.87e-12 1.78e-14 20 0.18 33.12 -1.82e-09 8.06e-08 25 0.23 130.96 -2.96e-11 9.50e-14 30 0.22 428.21 -6.58e-09 1.26e-10
Comparison of the new algorithm with ADMM algorithm [2] (second class)
 n Den CPU(TBTRS) CPU(ADMM) $F_{TB}-F_{AD}$ 50 1 0.091 2.46 -3.69e-08 100 1 0.12 3.0022 -1.63e-07 200 1 0.15 4.70 -3.81e-07 300 1 0.24 6.71 -4.61e-07 500 1 0.68 13.5 -6.15e-07 700 1 1.17 21.43 -2.05e-06 1000 1 2.82 47.35 -1.69e-06 2000 0.1 2.39 39.16 -9.22e-07 5000 0.01 2.96 55.92 -1.61e-06 10000 0.001 3.14 132.33 -4.85e-06
 n Den CPU(TBTRS) CPU(ADMM) $F_{TB}-F_{AD}$ 50 1 0.091 2.46 -3.69e-08 100 1 0.12 3.0022 -1.63e-07 200 1 0.15 4.70 -3.81e-07 300 1 0.24 6.71 -4.61e-07 500 1 0.68 13.5 -6.15e-07 700 1 1.17 21.43 -2.05e-06 1000 1 2.82 47.35 -1.69e-06 2000 0.1 2.39 39.16 -9.22e-07 5000 0.01 2.96 55.92 -1.61e-06 10000 0.001 3.14 132.33 -4.85e-06
Comparison of the new algorithm with Sakaue et. al's algorithm [25] (second class)
 n CPU(TBTRS) CPU(Sakaue et. al's algorithm [25]) $F_{TB}-F_{SA}$ $||x^*_{TB}-x^*_{SA}||$ 5 0.06 0.051 1.42e-11 1.22e-06 10 0.06 0.42 2.58e-10 3.69e-06 15 0.12 6.18 -1.72e-10 2.89e-06 20 0.08 35.03 2.84e-09 1.07e-05 25 0.13 139.93 2.96e-09 1.02e-05 30 0.14 449.08 4.73e-08 3.45e-05
 n CPU(TBTRS) CPU(Sakaue et. al's algorithm [25]) $F_{TB}-F_{SA}$ $||x^*_{TB}-x^*_{SA}||$ 5 0.06 0.051 1.42e-11 1.22e-06 10 0.06 0.42 2.58e-10 3.69e-06 15 0.12 6.18 -1.72e-10 2.89e-06 20 0.08 35.03 2.84e-09 1.07e-05 25 0.13 139.93 2.96e-09 1.02e-05 30 0.14 449.08 4.73e-08 3.45e-05
Comparison of the new algorithm with SDP relaxation (third class)
 n Den CPU(TBTRS) CPU(ADMM) CPU(CVX) $F_{TB}-F_{AD}$ $F_{TB}-F_{SD}$ 50 1 0.09 2.04 0.97 2.30e-09 -1.58e-05 100 1 0.18 2.01 2.93 1.75e-08 -7.33e-05 200 1 0.16 4.05 5.41 3.82e-07 -9.45e-04 300 1 0.24 6.16 14.39 5.71e-07 -2.23e-4 400 1 0.41 10.78 38.06 1.35e-06 -3.78e-4 500 1 0.67 11.87 63.26 4.67e-07 -4.67e-4 700 0.1 0.32 8.39 132.96 1.43e-07 -2.75e-4 800 0.1 0.39 9.02 206.75 2.42e-07 -2.904e-4 900 0.1 0.44 9.67 268.47 8.91e-07 -4.88e-4 1000 0.1 0.52 11.21 427.06 3.29e-07 -5.71e-4 2000 0.1 2.69 39.09 $-$ 5.28e-05 $-$ 3000 0.1 5.27 82.52 $-$ 3.85e-05 $-$ 5000 0.01 2.99 57.99 $-$ 6.16e-05 $-$ 10000 0.001 2.34 121.13 $-$ 7.12e-05 $-$
 n Den CPU(TBTRS) CPU(ADMM) CPU(CVX) $F_{TB}-F_{AD}$ $F_{TB}-F_{SD}$ 50 1 0.09 2.04 0.97 2.30e-09 -1.58e-05 100 1 0.18 2.01 2.93 1.75e-08 -7.33e-05 200 1 0.16 4.05 5.41 3.82e-07 -9.45e-04 300 1 0.24 6.16 14.39 5.71e-07 -2.23e-4 400 1 0.41 10.78 38.06 1.35e-06 -3.78e-4 500 1 0.67 11.87 63.26 4.67e-07 -4.67e-4 700 0.1 0.32 8.39 132.96 1.43e-07 -2.75e-4 800 0.1 0.39 9.02 206.75 2.42e-07 -2.904e-4 900 0.1 0.44 9.67 268.47 8.91e-07 -4.88e-4 1000 0.1 0.52 11.21 427.06 3.29e-07 -5.71e-4 2000 0.1 2.69 39.09 $-$ 5.28e-05 $-$ 3000 0.1 5.27 82.52 $-$ 3.85e-05 $-$ 5000 0.01 2.99 57.99 $-$ 6.16e-05 $-$ 10000 0.001 2.34 121.13 $-$ 7.12e-05 $-$
Comparison of the new algorithm with Sakaue et. al's algorithm [25] (third class)
 n CPU(TBTRS) CPU(Sakaue et. al's algorithm [25]) $F_{AD}-F_{SA}$ $||x^*_{AD}-x^*_{SA}||$ 5 0.08 0.059 1.32e-13 9.59e-08 10 0.06 0.36 1.86e-09 1.08e-05 15 0.06 5.69 5.12e-09 1.66e-05 20 0.07 32.62 1.25e-09 6.09e-06 25 0.14 130.46 7.24e-10 3.75e-06 30 0.14 419.58 8.38e-09 1.72e-05
 n CPU(TBTRS) CPU(Sakaue et. al's algorithm [25]) $F_{AD}-F_{SA}$ $||x^*_{AD}-x^*_{SA}||$ 5 0.08 0.059 1.32e-13 9.59e-08 10 0.06 0.36 1.86e-09 1.08e-05 15 0.06 5.69 5.12e-09 1.66e-05 20 0.07 32.62 1.25e-09 6.09e-06 25 0.14 130.46 7.24e-10 3.75e-06 30 0.14 419.58 8.38e-09 1.72e-05
 [1] Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A socp relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 [2] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [3] Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050 [4] Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115 [5] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [6] Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098 [7] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [8] Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119 [9] Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100 [10] Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109 [11] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [12] Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117 [13] Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081 [14] M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 [15] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [16] Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243 [17] Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374 [18] Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015 [19] Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020049 [20] Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

Impact Factor: