American Institute of Mathematical Sciences

Advanced
  • 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

Saeid Ansary Karbasy and  Maziar Salahi ,

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.

Keywords: Quadratic optimization, global optimization, extended trust region subproblem, two trust region subproblem.
Mathematics Subject Classification: Primary: 90C20, 90C26.
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:
[1]

S. Adachi, S. Iwata, Y. Nakatsukasa and A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM Journal on Optimization, 27 (2017), 269-291.  doi: 10.1137/16M1058200.  Google Scholar

[2]

S. Ansary Karbasy and M. Salahi, A hybrid algorithm for the two-trust-region subproblem, Computational and Applied Mathematics, https://doi.org/10.1007/s40314-019-0864-y doi: 10.1007/s40314-019-0864-y.  Google Scholar

[3]

H. T. Banks and K. Kunisch, Estimation Techniques for Distributed Parameter Systems, Springer Science and Business Media, 2012. doi: 10.1007/978-1-4612-3700-6.  Google Scholar

[4]

A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM Journal on Optimization, 17 (2006), 844-860.  doi: 10.1137/050644471.  Google Scholar

[5]

Im. Bomze and Ml. Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Mathematical Programming, 151 (2015), 459-476.  doi: 10.1007/s10107-014-0836-3.  Google Scholar

[6]

S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems, SIAM Journal on Optimization, 23 (2013), 432-451.  doi: 10.1137/110826862.  Google Scholar

[7]

S. Burer and B. Yang, The trust-region subproblem with non-intersecting linear constraints, Mathematical Programming, 149 (2015), 253-264.  doi: 10.1007/s10107-014-0749-1.  Google Scholar

[8]

M. R. Celis, J. E. Dennis and R. A. Tapia, A trust-region strategy for nonlinear equality constrained optimization, Numerical Optimization, (1984), 71–82.  Google Scholar

[9]

A. R. Conn, N. I. Gould and P. L. Toint, Trust-Region Methods, SIAM Philadelphia, Vol: 1, 2000. doi: 10.1137/1.9780898719857.  Google Scholar

[10]

J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM publisher, Vol: 16, 1996. doi: 10.1137/1.9781611971200.  Google Scholar

[11]

S. Fallahi, M. Salahi and S. Ansary Karbasy, On SOCP/SDP formulation of the extended trust-region subproblem, to appear in Iranian Journal of Operations Research, 2019. doi: 10.1007/s40314-019-0864-y.  Google Scholar

[12]

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 2.1, March 2017. Available from: http://cvxr.com/cvx. Google Scholar

[13]

S. Gugercin, A. C. Antoulas and H. P. Zhang, An approach to identification for robust control, IEEE Transactions on Automatic Control, 48 (2003), 1109-1115.  doi: 10.1109/TAC.2003.812821.  Google Scholar

[14]

M. Heinkenschloss, Mesh independence for nonlinear least squares problems with norm constraints, SlAM Journal on Optimization, 3 (1993), 81-117. doi: 10.1137/0803005.  Google Scholar

[15]

M. Heinkenschloss, On the solution of a two ball trust-region subproblem, Mathematical Programming, 64 (1994), 249-276.  doi: 10.1007/BF01582576.  Google Scholar

[16]

V. Jeyakumar and G. Y. Li, Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization, Mathematical Programming, 147 (2014), 171-206.  doi: 10.1007/s10107-013-0716-2.  Google Scholar

[17]

B. Kaltenbacher, F. Rendl and E. Resmerita, Computing quasisolutions of nonlinear inverse problems via efficient minimization of trust region problems, Journal of Inverse and Ill-Posed Problems, 24 (2016), 435-447.  doi: 10.1515/jiip-2015-0087.  Google Scholar

[18]

C. Kravaris and J. H. Seinfeld, Identification of parameters in distributed parameter systems by regularization, SIAM Journal on Control and Optimization, 23 (1985), 217-241.  doi: 10.1137/0323017.  Google Scholar

[19]

G. Kristensson, Inverse problems for acoustic waves using the penalised likelihood method, Inverse Problems, 2 (1986), 461.  Google Scholar

[20]

J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM Journal on Optimization, 4 (1994), 159-176.  doi: 10.1137/0804009.  Google Scholar

[21]

Y. Nesterov, H. Wolkowicz and Y. Ye, Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization, Handbook of Semidefinite Programming, Springer, Boston, (2000), 361–419. doi: 10.1007/978-1-4615-4381-7_13.  Google Scholar

[22] S. Omatu and J. H. Seinfeld, Distributed Parameter Systems: Theory and Applications,, Clarendon Press, 1989.   Google Scholar
[23]

F. O'Sullivan and G. Wahba, A cross validated Bayesian retrieval algorithm for nonlinear remote sensing experiments, Journal of Computational Physics, 59 (1985), 441-455.   Google Scholar

[24]

J.-M. Peng and Y. Yuan, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM Journal on Optimization, 7 (1997), 579-594.  doi: 10.1137/S1052623494261520.  Google Scholar

[25]

S. Sakaue, Y. Nakatsukasa, A. Takeda and S. Iwata, Solving generalized CDT problems via two-parameter eigenvalues, SIAM Journal on Optimization, 26 (2016), 1669-1694.  doi: 10.1137/15100624X.  Google Scholar

[26]

M. Salahi and A. Taati, A fast eigenvalue approach for solving the trust-region subproblem with an additional linear inequality, Computational and Applied Mathematics, 37 (2018), 329-347.  doi: 10.1007/s40314-016-0347-3.  Google Scholar

[27]

M. Salahi, A. Taati and H. Wolkowicz, Local nonglobal minima for solving large scale extended trust-region subproblems, Computational Optimization and Applications, 66 (2016), 223-244.  doi: 10.1007/s10589-016-9867-4.  Google Scholar

[28]

M. Salah and S. Fallahi, Trust-region subproblem with an additional linear inequality constraint, Optimization Letters, 10 (2016), 821-832.  doi: 10.1007/s11590-015-0957-5.  Google Scholar

[29]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[30]

C. R. Vogel, A constrained least squares regularization method for nonlinear iii-posed problems, SIAM Journal on Control and Optimization, 28 (1990), 34-49.  doi: 10.1137/0328002.  Google Scholar

[31]

A. Zhang and S. Hayashi, Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints, Numerical Algebra, Control and Optimization, 1 (2011), 83-98.  doi: 10.3934/naco.2011.1.83.  Google Scholar

show all references

References:
[1]

S. Adachi, S. Iwata, Y. Nakatsukasa and A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM Journal on Optimization, 27 (2017), 269-291.  doi: 10.1137/16M1058200.  Google Scholar

[2]

S. Ansary Karbasy and M. Salahi, A hybrid algorithm for the two-trust-region subproblem, Computational and Applied Mathematics, https://doi.org/10.1007/s40314-019-0864-y doi: 10.1007/s40314-019-0864-y.  Google Scholar

[3]

H. T. Banks and K. Kunisch, Estimation Techniques for Distributed Parameter Systems, Springer Science and Business Media, 2012. doi: 10.1007/978-1-4612-3700-6.  Google Scholar

[4]

A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM Journal on Optimization, 17 (2006), 844-860.  doi: 10.1137/050644471.  Google Scholar

[5]

Im. Bomze and Ml. Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Mathematical Programming, 151 (2015), 459-476.  doi: 10.1007/s10107-014-0836-3.  Google Scholar

[6]

S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems, SIAM Journal on Optimization, 23 (2013), 432-451.  doi: 10.1137/110826862.  Google Scholar

[7]

S. Burer and B. Yang, The trust-region subproblem with non-intersecting linear constraints, Mathematical Programming, 149 (2015), 253-264.  doi: 10.1007/s10107-014-0749-1.  Google Scholar

[8]

M. R. Celis, J. E. Dennis and R. A. Tapia, A trust-region strategy for nonlinear equality constrained optimization, Numerical Optimization, (1984), 71–82.  Google Scholar

[9]

A. R. Conn, N. I. Gould and P. L. Toint, Trust-Region Methods, SIAM Philadelphia, Vol: 1, 2000. doi: 10.1137/1.9780898719857.  Google Scholar

[10]

J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM publisher, Vol: 16, 1996. doi: 10.1137/1.9781611971200.  Google Scholar

[11]

S. Fallahi, M. Salahi and S. Ansary Karbasy, On SOCP/SDP formulation of the extended trust-region subproblem, to appear in Iranian Journal of Operations Research, 2019. doi: 10.1007/s40314-019-0864-y.  Google Scholar

[12]

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 2.1, March 2017. Available from: http://cvxr.com/cvx. Google Scholar

[13]

S. Gugercin, A. C. Antoulas and H. P. Zhang, An approach to identification for robust control, IEEE Transactions on Automatic Control, 48 (2003), 1109-1115.  doi: 10.1109/TAC.2003.812821.  Google Scholar

[14]

M. Heinkenschloss, Mesh independence for nonlinear least squares problems with norm constraints, SlAM Journal on Optimization, 3 (1993), 81-117. doi: 10.1137/0803005.  Google Scholar

[15]

M. Heinkenschloss, On the solution of a two ball trust-region subproblem, Mathematical Programming, 64 (1994), 249-276.  doi: 10.1007/BF01582576.  Google Scholar

[16]

V. Jeyakumar and G. Y. Li, Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization, Mathematical Programming, 147 (2014), 171-206.  doi: 10.1007/s10107-013-0716-2.  Google Scholar

[17]

B. Kaltenbacher, F. Rendl and E. Resmerita, Computing quasisolutions of nonlinear inverse problems via efficient minimization of trust region problems, Journal of Inverse and Ill-Posed Problems, 24 (2016), 435-447.  doi: 10.1515/jiip-2015-0087.  Google Scholar

[18]

C. Kravaris and J. H. Seinfeld, Identification of parameters in distributed parameter systems by regularization, SIAM Journal on Control and Optimization, 23 (1985), 217-241.  doi: 10.1137/0323017.  Google Scholar

[19]

G. Kristensson, Inverse problems for acoustic waves using the penalised likelihood method, Inverse Problems, 2 (1986), 461.  Google Scholar

[20]

J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM Journal on Optimization, 4 (1994), 159-176.  doi: 10.1137/0804009.  Google Scholar

[21]

Y. Nesterov, H. Wolkowicz and Y. Ye, Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization, Handbook of Semidefinite Programming, Springer, Boston, (2000), 361–419. doi: 10.1007/978-1-4615-4381-7_13.  Google Scholar

[22] S. Omatu and J. H. Seinfeld, Distributed Parameter Systems: Theory and Applications,, Clarendon Press, 1989.   Google Scholar
[23]

F. O'Sullivan and G. Wahba, A cross validated Bayesian retrieval algorithm for nonlinear remote sensing experiments, Journal of Computational Physics, 59 (1985), 441-455.   Google Scholar

[24]

J.-M. Peng and Y. Yuan, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM Journal on Optimization, 7 (1997), 579-594.  doi: 10.1137/S1052623494261520.  Google Scholar

[25]

S. Sakaue, Y. Nakatsukasa, A. Takeda and S. Iwata, Solving generalized CDT problems via two-parameter eigenvalues, SIAM Journal on Optimization, 26 (2016), 1669-1694.  doi: 10.1137/15100624X.  Google Scholar

[26]

M. Salahi and A. Taati, A fast eigenvalue approach for solving the trust-region subproblem with an additional linear inequality, Computational and Applied Mathematics, 37 (2018), 329-347.  doi: 10.1007/s40314-016-0347-3.  Google Scholar

[27]

M. Salahi, A. Taati and H. Wolkowicz, Local nonglobal minima for solving large scale extended trust-region subproblems, Computational Optimization and Applications, 66 (2016), 223-244.  doi: 10.1007/s10589-016-9867-4.  Google Scholar

[28]

M. Salah and S. Fallahi, Trust-region subproblem with an additional linear inequality constraint, Optimization Letters, 10 (2016), 821-832.  doi: 10.1007/s11590-015-0957-5.  Google Scholar

[29]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[30]

C. R. Vogel, A constrained least squares regularization method for nonlinear iii-posed problems, SIAM Journal on Control and Optimization, 28 (1990), 34-49.  doi: 10.1137/0328002.  Google Scholar

[31]

A. Zhang and S. Hayashi, Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints, Numerical Algebra, Control and Optimization, 1 (2011), 83-98.  doi: 10.3934/naco.2011.1.83.  Google Scholar

Figure 1.   $ + $: global solution of $ Pc_1 $ and $ Pc_2 $, $ \Box $: LNGMs of $ Pc_1 $ and $ Pc_2 $
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  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]
Table Options

Download as excel

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]
Table 2.  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
Table Options

Download as excel

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
Table 3.  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
Table Options

Download as excel

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
Table 4.  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
Table Options

Download as excel

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
Table 5.  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
Table Options

Download as excel

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
Table 6.  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 $ - $
Table Options

Download as excel

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 $ - $
Table 7.  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
Table Options

Download as excel

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]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[2]

Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117
[3]

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
[4]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919
[5]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309
[6]

Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial & Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321
[7]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223
[8]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169
[9]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117
[10]

Yannan Chen, Jingya Chang. A trust region algorithm for computing extreme eigenvalues of tensors. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 475-485. doi: 10.3934/naco.2020046
[11]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237
[12]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[13]

Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070
[14]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041
[15]

Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003
[16]

Luca Bisconti, Davide Catania. Global well-posedness of the two-dimensional horizontally filtered simplified Bardina turbulence model on a strip-like region. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1861-1881. doi: 10.3934/cpaa.2017090
[17]

Paolo Tilli. Compliance estimates for two-dimensional problems with Dirichlet region of prescribed length. Networks & Heterogeneous Media, 2012, 7 (1) : 127-136. doi: 10.3934/nhm.2012.7.127
[18]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[19]

Huimin Liu, Hui Yu. Fairness and retailer-led supply chain coordination under two different degrees of trust. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1347-1364. doi: 10.3934/jimo.2016076
[20]

Xiaojiao Tong, Felix F. Wu, Jifeng Su. Quadratic approximation and visualization of online contract-based available transfer capability region of power systems. Journal of Industrial & Management Optimization, 2008, 4 (3) : 553-563. doi: 10.3934/jimo.2008.4.553

 Impact Factor: 

Tools

Metrics

  • PDF downloads (366)
  • HTML views (660)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy