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 and 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.

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

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.

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

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 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: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy