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

On box-constrained total least squares problem

  • * Corresponding author: Y. Xia

    * Corresponding author: Y. Xia 

This research was supported by NSFC grants 11822103, 11571029, 11771056 and Beijing Natural Science Foundation Z180005

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • We study box-constrained total least squares problem (BTLS), which minimizes the ratio of two quadratic functions with lower and upper bounded constraints. We first prove that (BTLS) is NP-hard. Then we show that for fixed number of dimension, it is polynomially solvable. When the constraint box is centered at zero, a relative $ 4/7 $-approximate solution can be obtained in polynomial time based on SDP relaxation. For zero-centered and unit-box case, we show that the direct nontrivial least square relaxation could provide an absolute $ (n+1)/2 $-approximate solution. In the general case, we propose an enhanced SDP relaxation for (BTLS). Numerical results demonstrate significant improvements of the new relaxation.

    Mathematics Subject Classification: Primary: 90C20, 90C32; Secondary: 65F20.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Numerical comparison of lower bounds

    $ (m,n) $ $ l=0,u=50 $ $ l=0,u=100 $ $ l=0,u=255 $
    $ v $(SDP) $ v $(ISDP) $ v $(SDP) $ v $(ISDP) $ v $(SDP) $ v $(ISDP)
    (15, 10) 0.1847 0.1884 0.1742 0.1760 0.1675 0.1683
    (50, 25) 0.4530 0.5043 0.4137 0.4425 0.3893 0.4011
    (75, 50) 0.4732 0.5302 0.4214 0.4546 0.3893 0.4033
    (100, 75) 0.3218 0.3825 0.2501 0.2875 0.2057 0.2229
    (125,100) 0.4034 0.4805 0.3010 0.3541 0.2372 0.2646
    (150,125) 0.3664 0.4496 0.2403 0.3028 0.1622 0.2163
     | Show Table
    DownLoad: CSV

    Table 2.  Numerical comparison of CPU time

    $ (m,n) $ $ l=0,u=50 $ $ l=0,u=100 $ $ l=0,u=255 $
    $ t $(SDP) $ t $(ISDP) $ t $(SDP) $ t $(ISDP) $ t $(SDP) $ t $(ISDP)
    (15, 10) 0.69 2.70 0.34 1.35 0.41 1.41
    (50, 25) 0.94 8.34 0.40 4.36 0.42 4.67
    (75, 50) 1.44 36.81 0.70 19.16 0.68 20.76
    (100, 75) 2.33 109.05 1.27 66.26 1.26 70.89
    (125,100) 4.92 259.68 2.91 176.77 2.87 239.28
    (150,125) 9.99 686.35 6.65 564.68 6.11 647.24
     | Show Table
    DownLoad: CSV
  • [1] K. Anstreicher, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, J. Global Optim., 43 (2009), 471-484.  doi: 10.1007/s10898-008-9372-0.
    [2] A. BeckA. Ben-Tal and M. Teboulle, Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares, SIAM J. Matrix Anal. Appl., 28 (2006), 425-445.  doi: 10.1137/040616851.
    [3] A. Beck and M. Teboulle, A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program., 118 (2009), 13-35.  doi: 10.1007/s10107-007-0181-x.
    [4] A. Beck and M. Teboulle, On minimizing quadratically constrained ratio of two quadratic functions, J. Convex Anal., 17 (2010), 789-804. 
    [5] 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.
    [6] A. Ben-Tal and M. Teboulle, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., 72 (1996), 51-63.  doi: 10.1016/0025-5610(95)00020-8.
    [7] D. Bienstock and A. Michalka, Polynomial solvability of variants of the trust-region subproblem, in Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms(eds. C. Chekuri), SODA, (2014), 380–390. doi: 10.1137/1.9781611973402.28.
    [8] S. Burer and K. Anstreicher, Second-order-cone constraints for extended trust-region problems, SIAM J. Optim., 23 (2013), 432-451.  doi: 10.1137/110826862.
    [9] A. Charnes and W. Cooper, Programming with linear fractional functionals, Nav. Res. Logist. Q., 9 (1962), 181-186.  doi: 10.1002/nav.3800090303.
    [10] CVX Research, Inc., CVX: Matlab software for disciplined convex programming, version 2.0., http://cvxr.com/cvx, April 2011.
    [11] W. Dinkelbach, On nonlinear fractional programming, Manag. Sci., 13 (1967), 492-498.  doi: 10.1287/mnsc.13.7.492.
    [12] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. Freeman, San Francisco, 1979.
    [13] G. Golub and C. Loan, An analysis of the total least-squares problem, SIAM J. Numer. Anal., 17 (1980), 883-893.  doi: 10.1137/0717073.
    [14] M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), 1115-1145.  doi: 10.1145/227683.227684.
    [15] Y. Hsia and R. L. Sheu, Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity, arXiv: 1312.1398, 2013
    [16] Z. LuoW. MaA. SoY. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems, IEEE Signal Proc. Mag., 27 (2010), 20-34. 
    [17] J. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4 (1994), 159-176.  doi: 10.1137/0804009.
    [18] Y. Nesterov and A. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SIAM Publications, SIAM, Philadelphia, 1993. doi: 10.1137/1.9781611970791.
    [19] Y. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optim. Method Softw., 9 (1998), 141-160.  doi: 10.1080/10556789808805690.
    [20] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, 2003. doi: 10.1007/978-1-4419-8853-9.
    [21] P. Pardalos and A. Phillips, Global optimization of fractional programs, J. Global Optim., 1 (1991), 173-182.  doi: 10.1007/BF00119990.
    [22] J. 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.
    [23] Y. Xia, On minimizing the ratio of quadratic functions over an ellipsoid, Optimization, 64 (2015), 1097-1106.  doi: 10.1080/02331934.2013.840623.
    [24] Y. Xia, A survey of hidden convex optimization, J. Oper. Res. Soc. China., 8 (2020), 1-28.  doi: 10.1007/s40305-019-00286-5.
    [25] M. Yang and Y. Xia, On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint, Optim. Lett., 14 (2020), 569–578., doi: 10.1007/s11590-018-1320-4.
    [26] Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program., 84 (1999), 219-226.  doi: 10.1007/s10107980012a.
    [27] Y. Ye and S. Zhang, New results on quadratic minimization, SIAM J. Optim., 14 (2003), 245-267.  doi: 10.1137/S105262340139001X.
  • 加载中

Tables(2)

SHARE

Article Metrics

HTML views(653) PDF downloads(540) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return