-
Previous Article
An improved algorithm for generalized least squares estimation
- NACO Home
- This Issue
-
Next Article
A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems
On box-constrained total least squares problem
LMIB of the Ministry of Education, School of Mathematical Sciences, Beihang University, Beijing, 100191, P. R. China |
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.
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. |
(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 |
(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 |
(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 |
(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
Other articles
by authors
[Back to Top]