American Institute of Mathematical Sciences

Advanced
December  2020, 10(4): 439-449. doi: 10.3934/naco.2020043

On box-constrained total least squares problem

Zhuoyi Xu , Yong Xia , and  Deren Han

LMIB of the Ministry of Education, School of Mathematical Sciences, Beihang University, Beijing, 100191, P. R. China

* Corresponding author: Y. Xia

Received  May 2020 Revised  September 2020 Published  September 2020

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

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.

Keywords: Total least squares, fractional programming, quadratic optimization, semidefinite programming, approximation.
Mathematics Subject Classification: Primary: 90C20, 90C32; Secondary: 65F20.
Citation: Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 439-449. doi: 10.3934/naco.2020043
References:
[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.  Google Scholar

[2]

A. Beck, A. 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.  Google Scholar

[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.  Google Scholar

[4]

A. Beck and M. Teboulle, On minimizing quadratically constrained ratio of two quadratic functions, J. Convex Anal., 17 (2010), 789-804.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

A. Charnes and W. Cooper, Programming with linear fractional functionals, Nav. Res. Logist. Q., 9 (1962), 181-186.  doi: 10.1002/nav.3800090303.  Google Scholar

[10]

CVX Research, Inc., CVX: Matlab software for disciplined convex programming, version 2.0., http://cvxr.com/cvx, April 2011. Google Scholar

[11]

W. Dinkelbach, On nonlinear fractional programming, Manag. Sci., 13 (1967), 492-498.  doi: 10.1287/mnsc.13.7.492.  Google Scholar

[12]

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. Freeman, San Francisco, 1979.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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 Google Scholar

[16]

Z. Luo, W. Ma, A. So, Y. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems, IEEE Signal Proc. Mag., 27 (2010), 20-34.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

Y. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optim. Method Softw., 9 (1998), 141-160.  doi: 10.1080/10556789808805690.  Google Scholar

[20]

Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, 2003. doi: 10.1007/978-1-4419-8853-9.  Google Scholar

[21]

P. Pardalos and A. Phillips, Global optimization of fractional programs, J. Global Optim., 1 (1991), 173-182.  doi: 10.1007/BF00119990.  Google Scholar

[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.  Google Scholar

[23]

Y. Xia, On minimizing the ratio of quadratic functions over an ellipsoid, Optimization, 64 (2015), 1097-1106.  doi: 10.1080/02331934.2013.840623.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[26]

Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program., 84 (1999), 219-226.  doi: 10.1007/s10107980012a.  Google Scholar

[27]

Y. Ye and S. Zhang, New results on quadratic minimization, SIAM J. Optim., 14 (2003), 245-267.  doi: 10.1137/S105262340139001X.  Google Scholar

show all references

References:
[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.  Google Scholar

[2]

A. Beck, A. 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.  Google Scholar

[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.  Google Scholar

[4]

A. Beck and M. Teboulle, On minimizing quadratically constrained ratio of two quadratic functions, J. Convex Anal., 17 (2010), 789-804.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

A. Charnes and W. Cooper, Programming with linear fractional functionals, Nav. Res. Logist. Q., 9 (1962), 181-186.  doi: 10.1002/nav.3800090303.  Google Scholar

[10]

CVX Research, Inc., CVX: Matlab software for disciplined convex programming, version 2.0., http://cvxr.com/cvx, April 2011. Google Scholar

[11]

W. Dinkelbach, On nonlinear fractional programming, Manag. Sci., 13 (1967), 492-498.  doi: 10.1287/mnsc.13.7.492.  Google Scholar

[12]

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. Freeman, San Francisco, 1979.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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 Google Scholar

[16]

Z. Luo, W. Ma, A. So, Y. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems, IEEE Signal Proc. Mag., 27 (2010), 20-34.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

Y. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optim. Method Softw., 9 (1998), 141-160.  doi: 10.1080/10556789808805690.  Google Scholar

[20]

Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, 2003. doi: 10.1007/978-1-4419-8853-9.  Google Scholar

[21]

P. Pardalos and A. Phillips, Global optimization of fractional programs, J. Global Optim., 1 (1991), 173-182.  doi: 10.1007/BF00119990.  Google Scholar

[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.  Google Scholar

[23]

Y. Xia, On minimizing the ratio of quadratic functions over an ellipsoid, Optimization, 64 (2015), 1097-1106.  doi: 10.1080/02331934.2013.840623.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[26]

Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program., 84 (1999), 219-226.  doi: 10.1007/s10107980012a.  Google Scholar

[27]

Y. Ye and S. Zhang, New results on quadratic minimization, SIAM J. Optim., 14 (2003), 245-267.  doi: 10.1137/S105262340139001X.  Google Scholar

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

Download as excel

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

Download as excel

$ (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
[1]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[2]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[3]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[4]

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

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[6]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[7]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[8]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[9]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[10]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127
[11]

Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83
[12]

Chengjin Li. Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 511-520. doi: 10.3934/naco.2020048
[13]

Cristian Dobre. Mathematical properties of the regular *-representation of matrix $*$-algebras with applications to semidefinite programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
[14]

James Anderson, Antonis Papachristodoulou. Advances in computational Lyapunov analysis using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2361-2381. doi: 10.3934/dcdsb.2015.20.2361
[15]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185
[16]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[17]

Lucian Coroianu, Danilo Costarelli, Sorin G. Gal, Gianluca Vinti. Approximation by multivariate max-product Kantorovich-type operators and learning rates of least-squares regularized regression. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4213-4225. doi: 10.3934/cpaa.2020189
[18]

Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350
[19]

Mansoureh Alavi Hejazi, Soghra Nobakhtian. Optimality conditions for multiobjective fractional programming, via convexificators. Journal of Industrial & Management Optimization, 2020, 16 (2) : 623-631. doi: 10.3934/jimo.2018170
[20]

Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial & Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629

 Impact Factor: 

Tools

Metrics

  • PDF downloads (381)
  • HTML views (237)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy