\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem

  • * Corresponding author: Ye Tian

    * Corresponding author: Ye Tian 
Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by
  • This paper proposes a second-order cone programming (SOCP) relaxation for the generalized trust-region problem by exploiting the property that any symmetric matrix and identity matrix can be simultaneously diagonalizable. We show that our proposed SOCP relaxation can provide a lower bound as tight as that of the standard semidefinite programming (SDP) relaxation. Moreover, we provide a sufficient condition under which the proposed SOCP relaxation is exact. Since the standard SDP relaxation suffers from a much heavier computing burden, the proposed SOCP relaxation has a much higher efficiency in solving process. Then we design a branch-and-bound algorithm based on this SOCP relaxation to obtain the global optimal solution for a general problem. Three types of numerical experiments are carried out to demonstrate the effectiveness and efficiency of our proposed SOCP relaxation.

    Mathematics Subject Classification: Primary: 90C20, 90C26, 90C57.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  The trust-region problem with linear inequality constraints

    Case name $ n $ $ s $ NSOCP_BB ED BFS [3]
    nodes CPU(sec) nodes CPU(sec) nodes CPU(sec)
    Data_lin_8_20 8 20 19 0.5483 19 2.0817 3471 3.56
    Data_lin_10_11 10 11 5 0.3004 1 0.4391 155 0.238
    Data_30of90 90 60 1 0.6515 1 0.7701 3 0.0341
    Data3_100_10 100 10 11 6.5704 15 113.0250 93 0.29
    Data3_100_15 100 15 11 7.3087 33 281.2684 6439 21.11
    Data_200_10 200 10 2 9.6405 1 11.7755 255 0.96
    Data_200_15 200 15 10 27.6235 8 81.9576 2047 7.93
    Data3_300_10 300 10 22 31.8774 21 304.4157 287 3.75
    Data_300_15 300 15 29 40.7551 22 426.1334 8959 128.03
     | Show Table
    DownLoad: CSV

    Table 2.  The generalized Celis-Dennis-Tapia problem

    $ n $ $ m $ NSOCP_BB ED
    ave nodes ave CPU(sec) ave nodes ave CPU(sec)
    100 4 4.0 3.4839 2.1 12.0705
    150 4 3.8 5.6403 2.1 35.2577
    200 4 4.4 9.9031 2.7 110.9290
    250 4 3.5 15.3188 2.7 244.2893
    300 4 4.1 23.9567 3.3 594.1906
    350 4 6.8 44.4904 2.7 818.5657
    400 4 4.7 56.4051 3.0 1670.5532
    100 7 3.8 5.5790 2.9 19.0970
    150 7 3.7 10.1234 2.7 49.3179
    200 7 5.1 19.0962 3.0 141.8477
    250 7 4.3 29.4947 2.6 254.5980
    300 7 4.8 45.4383 2.7 554.2895
    350 7 3.3 64.0829 2.9 1336.9454
    400 7 4.0 91.8627 4.2 2551.6678
    100 10 4.9 9.3095 3.1 22.9624
    150 10 5.6 21.4694 2.3 53.6741
    200 10 5.3 32.4885 3.3 169.8376
    250 10 3.6 52.2134 3.0 317.0527
    300 10 5.3 80.7183 2.7 554.8825
    350 10 6.3 123.4788 2.4 884.3760
    400 10 8.3 181.5320 2.8 1584.7842
    100 20 7.9 93.9798 3.2 99.6843
    150 20 6.9 86.4431 2.8 120.1224
    200 20 5.6 140.9858 3.4 286.7472
    250 20 6.3 218.4065 2.5 430.6950
    300 20 6.2 326.3330 3.3 913.2317
    350 20 9.5 497.2161 3.8 1747.1609
    400 20 7.8 672.3612 3.0 2350.9039
     | Show Table
    DownLoad: CSV

    Table 3.  The subproblem of Sparse Source localization

    $ n $ $ m+p $ $ \delta $ NSOCP1_BB NSOCP_BB ACS
    ave nodes ave CPU(sec) ave nodes ave CPU(sec) ave nodes ave CPU(sec)
    3 6 0.1 6.7 0.2681 10.1 0.3792 12.2 2.4176
    3 6 1 10.7 0.3737 13.0 0.4631 15.3 3.1461
    3 10 0.1 9.1 0.3344 8.3 0.3251 13.2 2.6044
    3 10 1 13.2 0.4549 13.5 0.4847 17.3 2.9758
    3 13 0.1 7.5 0.2794 7.6 0.3015 15.5 3.1541
    3 13 1 22 0.6727 28.3 0.8975 18.1 3.2863
    4 6 0.1 13.6 0.4461 16.4 0.5690 12.6 2.7129
    4 6 1 22.9 0.6834 23.5 0.7513 13.9 2.8062
    4 10 0.1 15.5 0.5079 17.4 0.6016 24.1 6.3445
    4 10 1 21.1 0.6255 27.3 0.8490 25.3 5.1821
    4 13 0.1 13.4 0.4803 12.7 0.4958 17.1 4.1885
    4 13 1 25.1 0.8896 32.8 1.1869 25.3 7.1386
    5 6 0.1 37.1 1.0944 44.4 1.4771 22.6 5.2888
    5 6 1 33.7 0.8846 31.8 0.9472 42.2 10.4813
    5 10 0.1 20.5 0.6051 19.3 0.6300 26.3 7.5633
    5 10 1 25.5 0.7560 23.9 0.7938 20.5 5.4657
    5 13 0.1 16.1 0.6268 15.8 0.6625 24.2 6.8016
    5 13 1 36.0 1.1874 35.2 1.2666 26.6 8.3991
    6 6 0.1 49.6 1.6442 48.7 1.8016 24.6 4.5381
    6 6 1 9.6 0.4971 50.3 1.9330 236.8 23.6982
    6 10 0.1 25.4 0.9164 45.9 1.6842 57.0 13.6420
    6 10 1 48.3 1.5468 48.3 1.7473 63.8 16.7940
    7 6 0.1 99.0 2.8795 166.6 5.7123 189.2 46.6260
    7 6 1 53.6 1.6242 93.6 3.1935 174.2 53.2129
    7 10 0.1 76.1 2.3453 79.3 2.8579 78.7 20.8093
    7 10 1 342.6 9.6811 527.2 17.8453 58.8 14.7023
    8 6 0.1 186.2 5.2471 203.3 7.3216 602.2 72.8406
    8 6 1 60.9 1.8836 62.4 2.3540 202.9 47.0604
    8 10 0.1 51.5 1.7470 48.7 1.9087 17.4 3.5242
    8 10 1 117.0 3.4416 100.1 3.6475 62.0 16.2960
     | Show Table
    DownLoad: CSV
  • [1] W. Ai and S. Zhang, Strong duality for the CDT subproblem: A necessary and sufficient condition, SIAM J. Optim., 19 (2009), 1735-1756.  doi: 10.1137/07070601X.
    [2] A. I. Barvinok, Feasibility testing for systems of real quadratic equations, Discrete Comput. Geom., 10 (1993), 1-13.  doi: 10.1007/BF02573959.
    [3] A. Beck and D. Pan, A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, J. Global Optim., 69 (2017), 309-342.  doi: 10.1007/s10898-017-0521-1.
    [4] A. Ben-Tal and D. Den Hertog, Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program., 143 (2014), 1-29.  doi: 10.1007/s10107-013-0710-8.
    [5] D. Bienstock and A. Michalka, Polynomial solvability of variants of the trust-region subproblem, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics, New York, 2014,380–390. doi: 10.1137/1.9781611973402.28.
    [6] D. Bienstock, A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26 (2016), 488-498.  doi: 10.1137/15M1009871.
    [7] I. M. Bomze and M. L. Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Math. Program., 151 (2015), 459-476.  doi: 10.1007/s10107-014-0836-3.
    [8] I. M. BomzeV. Jeyakumar and G. Li, Extended trust-region problems with one or two balls: Exact copositive and Lagrangian relaxations, J. Global Optim., 71 (2018), 551-569.  doi: 10.1007/s10898-018-0607-4.
    [9] S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23 (2013), 432-451.  doi: 10.1137/110826862.
    [10] M. R. CelisJ. E. Dennis and R. A. Tapia, A trust region strategy for nonlinear equality constrained optimization, Numerical Optimization, 1984 (1985), 71-82. 
    [11] M. Grant and S. Boyed, CVX: Matlab Software for Disciplined Convex Programming, version 2.1, (2014). Available at: http://cvxr.com/cvx.
    [12] N. Ho-Nguyen and F. Kilinc-Karzan, A second-order cone based approach for solving the trust-region subproblem and its variants, SIAM J. Optim., 27 (2017), 1485-1512.  doi: 10.1137/16M1065197.
    [13] R. Jiang and D. Li, Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming, SIAM J. Optim., 26 (2016), 1649-1668.  doi: 10.1137/15M1023920.
    [14] V. Jeyakumar and G. Y. Li, Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization, Math. Program., 147 (2014), 171-206.  doi: 10.1007/s10107-013-0716-2.
    [15] S. Kim and M. Kojima, Second order cone programming relaxation of nonconvex quadratic optimization problems, Optim. Methods Softw., 15 (2001), 201-224.  doi: 10.1080/10556780108805819.
    [16] C. LuZ. Deng and Q. Jin, An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, J. Global Optim., 67 (2017), 475-493.  doi: 10.1007/s10898-016-0436-2.
    [17] C. LuZ. DengJ. Zhou and X. Guo, A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming, J. Global Optim., 73 (2019), 371-388.  doi: 10.1007/s10898-018-0726-y.
    [18] Z. Q. LuoW. K. MaA. M. C. SoY. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems, IEEE Signal Processing Magazine, 27 (2010), 20-34.  doi: 10.1109/MSP.2010.936019.
    [19] D. R. MorrisonS. H. JacobsonJ. J. Sauppe and E. C. Sewell, Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning, Discrete Optim., 19 (2016), 79-102.  doi: 10.1016/j.disopt.2016.01.005.
    [20] K. B. Petersen and M. S. Pedersen, The matrix cookbook, Technical University of Denmark, 7 (2008), 510pp.
    [21] N. Sagara and M. Fukushima, A trust region method for nonsmooth convex optimization, J. Ind. Manag. Optim., 1 (2005), 171-180.  doi: 10.3934/jimo.2005.1.171.
    [22] Z. ShengG. YuanZ. CuiX. Duan and X. Wang, An adaptive trust region algorithm for large-residual nonsmooth least squares problems, J. Ind. Manag. Optim., 14 (2018), 707-718.  doi: 10.3934/jimo.2017070.
    [23] J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11 (1999), 625-653.  doi: 10.1080/10556789908805766.
    [24] J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Math. Oper. Res., 28 (2003), 246-267.  doi: 10.1287/moor.28.2.246.14485.
    [25] Y. TianZ. DengJ. Luo and Y. Li, An intuitionistic fuzzy set based S3VM model for binary classification with mislabeled information, Fuzzy Optim. Decis. Mak., 17 (2018), 475-494.  doi: 10.1007/s10700-017-9282-z.
    [26] J. ZhouS.-C. Fang and W. Xing, Conic approximation to quadratic optimization with linear complementarity constraints, Comput. Optim. Appl., 66 (2017), 97-122.  doi: 10.1007/s10589-016-9855-8.
    [27] J. Zhou and Z. Xu, A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints, Optim. Letters, 13 (2019), 1615-1630.  doi: 10.1007/s11590-018-1337-8.
  • 加载中

Tables(3)

SHARE

Article Metrics

HTML views(1171) PDF downloads(504) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return