Skip to main content
SpringerLink
Log in

On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint

  • Original paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Strong Lagrangian duality holds for the quadratic programming with a two-sided quadratic constraint. In this paper, we show that the two-sided quadratic constrained quadratic fractional programming, if well scaled, also has zero Lagrangian duality gap. However, this is not always true without scaling. For a special case, the identical regularized total least squares problem, we establish the necessary and sufficient condition under which the Lagrangian duality gap is positive.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Let f(x) be continuous on the closed interval [a, b] and differentiable on the open interval (a, b). Then there is a point \(c\in (a, b)\) such that \(f'(c)=\frac{f(b)-f(a)}{b-a}.\)

References

  1. Beck, A., Ben-Tal, A., Teboulle, M.: 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, 425–445 (2006)

    Article  MathSciNet  Google Scholar 

  2. Beck, A., Teboulle, M.: A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid. Math. Program. Ser. A. 118(1), 13–35 (2009)

    Article  MathSciNet  Google Scholar 

  3. Ben-Tal, A., Teboulle, M.: Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Program. 72, 51–63 (1996)

    MathSciNet  MATH  Google Scholar 

  4. Hazan, E., Koren, T.: A linear-time algorithm for trust region problems. Math. Program. 158(1), 363–381 (2016)

    Article  MathSciNet  Google Scholar 

  5. Nguyen, V.B., Sheu, R.L., Xia, Y.: An SDP approach for quadratic fractional problems with a two-sided quadratic constraint. Optim. Methods Softw. 31(4), 701–719 (2016)

    Article  MathSciNet  Google Scholar 

  6. Pólik, I., Terlaky, T.: A survey of the S-lemma. SIAM Rev. 49(3), 371–418 (2007)

    Article  MathSciNet  Google Scholar 

  7. Pong, T.K., Wolkowicz, H.: Generalizations of the trust region subproblem. Comput. Optim. Appl. 58(2), 273–322 (2014)

    Article  MathSciNet  Google Scholar 

  8. Rendl, F., Wolkowicz, H.: A semidefinite framework for thrust region subproblems with applications to large scale minimization. Math. Program. 77(2), 273–299 (1997)

    MATH  Google Scholar 

  9. Smola, A.J., Schölkopf, B.: A tutorial on support vector regression. Stat. Comput. 14(3), 199–222 (2004)

    Article  MathSciNet  Google Scholar 

  10. Stern, R., Wolkowicz, H.: Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. SIAM J. Optim. 5(2), 286–313 (1995)

    Article  MathSciNet  Google Scholar 

  11. Renaut, R.A., Guo, H.: Efficient algorithms for solution of regularized total least squares. SIAM J. Matrix Anal. Appl. 26, 457–476 (2005)

    Article  MathSciNet  Google Scholar 

  12. Wang, J., Xia, Y.: A linear-time algorithm for the trust region subproblem based on the hidden convexity. Optim. Lett. 11, 1639–1646 (2017)

    Article  MathSciNet  Google Scholar 

  13. Wang, S., Xia, Y.: Strong duality for generalized trust region subproblem: S-lemma with interval bounds. Optim. Lett. 9, 1063–1073 (2015)

    Article  MathSciNet  Google Scholar 

  14. Xia, Y.: On minimizing the ratio of quadratic functions over an ellipsoid. Optimization 64(5), 1097–1106 (2015)

    Article  MathSciNet  Google Scholar 

  15. Xia, Y., Wang, S., Sheu, R.L.: S-Lemma with Equality and Its Applications. Math. Program. 156(1), 513–547 (2016)

    Article  MathSciNet  Google Scholar 

  16. Yakubovich, V.A.: S-procedure in nonlinear control theory. Vestnik Leningrad. Univ. 1, 62-77 (in Russian) (1971)

Download references

Acknowledgements

This research was supported by NSFC under grants 11571029, 11471325 and 11771056, and by fundamental research funds for the Central Universities under Grant YWF-18-BJ-Y-16

Author information

Authors and Affiliations

  1. LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing, 100191, People’s Republic of China

    Meijia Yang & Yong Xia

Authors
  1. Meijia Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yong Xia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yong Xia.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yang, M., Xia, Y. On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint. Optim Lett 14, 569–578 (2020). https://doi.org/10.1007/s11590-018-1320-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-018-1320-4

Keywords

Search

Navigation