On box-constrained total least squares problem

Zhuoyi Xu; Yong Xia; Deren Han

doi:10.3934/naco.2020043

Article Contents

2020, Volume 10, Issue 4: 439-449. Doi: 10.3934/naco.2020043

This issue Previous Article A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems Next Article An improved algorithm for generalized least squares estimation

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
^* Corresponding author: Y. Xia

Received: April 30, 2020

Revised: August 31, 2020

Published: September 2020

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

Abstract

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:

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

Citation:

Full Text(HTML)

Table 1. Numerical comparison of lower bounds

$ (m,n) $	$ l=0,u=50 $		$ l=0,u=100 $		$ l=0,u=255 $
$ (m,n) $	$ 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 $
$ (m,n) $	$ 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

Related Papers

Cited by

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.
[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.
[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. Luo, W. Ma, A. So, Y. 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.