American Institute of Mathematical Sciences

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

On box-constrained total least squares problem

 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.

Citation: Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 439-449. doi: 10.3934/naco.2020043
References:

show all references

References:
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
 $(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
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
 $(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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629

Impact Factor: