Abstract

We consider the nonconvex problem minimizing the ratio of two quadratic functions over finitely many nonconvex quadratic inequalities. Relying on the homogenization technique we establish a sufficient condition that warrants the attainment of an optimal solution. Our result allows to extend and recover known conditions for some interesting special instances of the problem and to derive further results on its algorithmic and modeling aspects

Author information

Contact details are reproduced from the original publication and may be historical.

Amir Beck

Dept. of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa 32000, Israel

becka@ie.technion.ac.il

References

  1. A. Auslender: How to deal with the unbounded in optimization: theory and algorithms. Math. Program., Ser. A 79 (1997) 3–18.https://doi.org/10.1007/BF02614308Google Scholar
  2. A. Auslender, M. Teboulle: Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer, New York, 2003.Google Scholar
  3. A. Beck: Quadratic matrix programming, SIAM J. Optim. 17(4) (2006) 1224–1238.https://doi.org/10.1137/05064816XGoogle Scholar
  4. A. Beck, A. Ben-Tal: On the solution of the Tikhonov regularization of the total least squares problem, SIAM J. Optim. 17(1) (2006) 98–118.https://doi.org/10.1137/050624418Google Scholar
  5. A. Beck, A. Ben-Tal, 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(2) (2006) 425–445.https://doi.org/10.1137/040616851Google Scholar
  6. A. Beck, M. Teboulle: A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program., Ser. A 118(1) (2009) 13–35.https://doi.org/10.1007/s10107-007-0181-xGoogle Scholar
  7. A. Ben-Tal, A. Nemirovski: Lectures on Modern Convex Optimization, MPS/SIAM Series on Optimization, SIAM, Philadelphia (2001).https://doi.org/10.1137/1.9780898718829Google Scholar
  8. A. Ben-Tal, M. Teboulle: Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., Ser. A 72(1) (1996) 51–63.https://doi.org/10.1007/BF02592331Google Scholar
  9. W. Dinkelbach: On nonlinear fractional programming, Manage. Sci., Ser. A 13 (1967) 492–498.https://doi.org/10.1287/mnsc.13.7.492Google Scholar
  10. R. D. Fierro, G. H. Golub, P. C. Hansen, D. P. O’Leary: Regularization by truncated total least squares, SIAM J. Sci. Comput. 18(1) (1997) 1223–1241.https://doi.org/10.1137/S1064827594263837Google Scholar
  11. G. H. Golub, P. C. Hansen, D. P. O’Leary: Tikhonov regularization and total least squares, SIAM J. Matrix Anal. Appl. 21(2) (1999) 185–194.https://doi.org/10.1137/S0895479897326432Google Scholar
  12. G. H. Golub, C. F. Van Loan: An analysis of the total least-squares problem, SIAM J. Numer. Anal. 17(6) (1980) 883–893.https://doi.org/10.1137/0717073Google Scholar
  13. G. H. Golub, C. F. Van Loan: Matrix Computations. 3rd Ed., Johns Hopkins Univ. Press, Baltimore (1996).Google Scholar
  14. H. Guo, R. Renaut: A regularized total least squares algorithm, in: Total Least Squares and Errors-in-Variables Modeling. Analysis, Algorithms and Applications, S. Van Huffel, P. Lemmerling (eds.), Kluwer, Dordrecht (2002) 57–66.https://doi.org/10.1007/978-94-017-3552-0_6Google Scholar
  15. P. C. Hansen: The use of the L-curve in the regularization of discrete ill-posed problems, SIAM J. Sci. Comput. 14 (1993) 1487–1503.https://doi.org/10.1137/0914086Google Scholar
  16. P. C. Hansen: Regularization tools, a matlab package for analysis of discrete regularization problems, Numer. Algorithms 6 (1994) 1–35.https://doi.org/10.1007/BF02149761Google Scholar
  17. P. C. Hansen: Rank-Deficient and Discrete Ill-Posed Problems. Numerical Aspects of Linear Inversion, SIAM, Philadelphia (1998).https://doi.org/10.1137/1.9780898719697Google Scholar
  18. R. A. Horn, C. R. Johnson: Matrix Analysis, Cambridge Univ. Press, Cambridge (1985).https://doi.org/10.1017/CBO9780511810817Google Scholar
  19. R. Horst, P. M. Pardalos (eds.): Handbook of Global Optimization, Kluwer, Dordrecht (1995).https://doi.org/10.1007/978-1-4615-2025-2Google Scholar
  20. S. Van Huffel, J. Vandewalle: The Total Least-Squares Problem: Computational Aspects and Analysis, Frontier in Applied Mathematics 9, SIAM, Philadelphia (1991).https://doi.org/10.1137/1.9781611971002Google Scholar
  21. Y. Nesterov, A. Nemirovski: Interior-Point Polynomial Algorithms in Convex Programming, SIAM, Philadelphia (1994).https://doi.org/10.1137/1.9781611970791Google Scholar
  22. G. Pataki: The geometry of semidefinite programming, in: Handbook of Semidefinite Programming. Theory, Algorithms, and Applications, H. Wolkowicz et al. (ed.), Int. Ser. Oper. Res. Manag. Sci. 27, Kluwer, Boston (2000) 29–65.https://doi.org/10.1007/978-1-4615-4381-7_3Google Scholar
  23. D. Sima, S. Van Huffel, G. H. Golub: Regularized total least squares based on quadratic eigenvalue problem solvers, BIT 44(4) (2004) 793–812.https://doi.org/10.1007/s10543-004-6024-8Google Scholar
  24. J. F. Sturm: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw. (11–12) (1999) 625–653.https://doi.org/10.1080/10556789908805766Google Scholar
  25. L. Vandenberghe, S. Boyd: Semidefinite programming, SIAM Rev. 38(1) (1996) 40–95.https://doi.org/10.1137/1038003Google Scholar
  26. F. Zhang: Matrix Theory: Basic Results and Techniques, Universitext, Springer, New York (1999).https://doi.org/10.1007/978-1-4757-5797-2Google Scholar

Suggested citation

A. Beck, M. Teboulle. “On Minimizing Quadratically Constrained Ratio of Two Quadratic Functions.” Journal of Convex Analysis 17 (2010), No. 3&4, 789–804. https://doi.org/10.68381/jca17052

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2010. Rights now held by Banach Press LLC.