Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A geometric characterization of strong duality in nonconvex quadratic programming with linear and nonconvex quadratic constraints

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We first establish a relaxed version of Dines theorem associated to quadratic minimization problems with finitely many linear equality and a single (nonconvex) quadratic inequality constraints. The case of unbounded optimal valued is also discussed. Then, we characterize geometrically the strong duality, and some relationships with the conditions employed in Finsler theorem are established. Furthermore, necessary and sufficient optimality conditions with or without the Slater assumption are derived. Our results can be used to situations where none of the results appearing elsewhere are applicable. In addition, a revisited theorem due to Frank and Wolfe along with that due to Eaves is established for asymptotically linear sets.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Auslender, A.: Existence of optimal solutions and duality results under weak conditions. Math. Program. Ser. A 88, 45–59 (2000)

    Google Scholar 

  2. Auslender, A., Teboulle, M.: Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer Monograph. Math. Springer, New York (2003)

  3. Belousov, E.G., Klatte, D.: A Frank-Wolfe type theorem for convex polynomial programs. Comput. Optim. Appl. 22, 37–48 (2002)

    MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  5. Blum, E., Oettli, W.: Direct proof of the existence theorem for quadratic programming. Oper. Res. 20, 165–167 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bot, R.I., Wanka, G.: An alternative formulation for a new closed cone constraint qualification. Nonlinear Anal. 64, 1367–1381 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  7. Bot, R.I., Csetnek, E.R., Moldovan, A.: Revisiting some duality theorems via the quasirelative interior in convex optimization. J. Optim. Theory Appl. 139, 67–84 (2008)

    MATH  MathSciNet  Google Scholar 

  8. Bot, R.I., Csetnek, E.R., Wanka, G.: Regularity conditions via quasi-relative interior in convex programming. SIAM J. Optim. 19, 217–233 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  9. Cao, J.-M.: Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs. Math. Program. Ser. A. 69, 403–411 (1995)

    Google Scholar 

  10. Derinkuyu, K., Pinar, M.C.: On the S-procedure and some variants. Math. Meth. Oper. Res. 64, 55–77 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  11. Dines, L.L.: On the mapping of quadratic forms. Bull. Am. Math. Soc. 47, 494–498 (1941)

    Article  MathSciNet  Google Scholar 

  12. Eaves, B.C.: On quadratic programming. Manag. Sci. Theory Ser. 17, 698–711 (1971)

    Article  MATH  Google Scholar 

  13. Finsler, P.: Über das Vorkommen definiter und semi-definiter Formen in scharen quadratische Formen. Commentarii Matematici Helvetici 9, 188–192 (1937)

    Article  MathSciNet  Google Scholar 

  14. Flores-Bazán, F., Flores-Bazán, F., Vera, C.: A complete characterization of strong duality in nonconvex optimization with a single constraint. J. Glob. Optim. 53, 185–201 (2102)

    Google Scholar 

  15. Flores-Bazán, F., Hadjisavvas, N., Vera, C.: An optimal alternative theorem and applications to mathematical programming. J. Glob. Optim. 37, 229–243 (2007)

    Article  MATH  Google Scholar 

  16. Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3, 95–110 (1956)

    Article  MathSciNet  Google Scholar 

  17. Frenk, J.B.G., Kassay, G.: On classes of generalized convex functions. Gordan-Farkas type theorems, and Lagrangian duality J. Optim. Theory Appl. 102, 315–343 (1999)

    Google Scholar 

  18. Gay, D.M.: Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2, 186–197 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  19. Hamburger, C.: Two extensions to Finsler’s recurring theorem. Appl. Math. Optim. 40, 183–190 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  20. Horn, R.E., Johnson, C.R.: Matrix Analysis. Cambridge University Press, New york (1985)

    Book  MATH  Google Scholar 

  21. Jeyakumar, V.: Constraint qualifications characterizing Lagrangian duality in convex optimization. J. Optim. Theory Appl. 136, 31–41 (2008)

    MATH  MathSciNet  Google Scholar 

  22. Jeyakumar, V., Huy, N.Q., Li, Y.: Necessary and sufficient conditions for S-lemma and nonconvex quadratic optimization. Optim. Eng. 10, 491–503 (2009)

    Google Scholar 

  23. Jeyakumar, V., Lee, G.M.: Complete characterizations of stable Farkas’lemma and cone-convex programming duality. Math. Program. A 114, 335–347 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  24. Jeyakumar, V., Lee, G.M., Li, G.Y.: Alternative theorems for quadratic inequality systems and global quadratic optimization. SIAM J. Optim. 20, 983–1001 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  25. Jeyakumar, V., Li, G.Y.: Stable zero duality gaps in convex programming: complete dual characterizations with applications to semidefinite programs. J. Math. Anal. Appl. 360, 156–167 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  26. Jeyakumar, V., Li, G.Y.: Regularized Lagrangian duality for linearly constrained quadratic optimization and the trust-region problems. J. Glob. Optim. 49, 1–14 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  27. Luo, Z.-Q., Zhang, S.: On extensions of the Frank-Wolfe theorems. Comput. Optim. Appl. 13, 87–110 (1999)

    MATH  MathSciNet  Google Scholar 

  28. Mangasarian, O.L.: Locally unique solutions of quadratic programs, linear and nonlinear complementarity problems. Math. Program. A 19, 200–212 (1980)

    Google Scholar 

  29. Matskani, E., Sidiropoulos, N.D., Luo, Z.-Q., Tassiulas, L.: Convex approximations techniques for joint multiuser downlink beamforming and admission control. IEEE Trans. Wirel. Commun. 7, 2682–2693 (2008)

    Article  Google Scholar 

  30. Moré, J.J.: Generalizations of the trust region problem. Optim. Methods Softw. 2, 189–209 (1993)

    Article  Google Scholar 

  31. Ozdaglar, A., Tseng, P.: Existence of global minima for constrained optimization. J. Optim. Theory Appl. 128, 523–546 (2006)

    MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  33. Polyak, B.T.: Convexity of quadratic transformations and its use in control and optimization. J. Optim. Theory Appl. 99, 553–583 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  34. Sidiropoulos, N.D., Davidson, T.N., Luo, Z.-Q.: Transmit beamforming for physical layer multicasting. IEEE Trans. Signal Process. 54, 2239–2251 (2006)

    Article  Google Scholar 

  35. Sorensen, D.C.: Newton’s method with a model trust region modification. SIAM Numer. Anal. 19, 409–426 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  36. Tseng, P.: Some convex programs without a duality gap. Math. Program. B 116, 553–578 (2009)

    Google Scholar 

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

    Google Scholar 

  38. Yakubovich, V.A.: S-procedure in nonlinear control theory. Vestnik Leningrad. Univ. 4, 73–93 (1977) (English translation)

  39. Yan, Z.-Z., Guo, J.H.: Some equivalent results with Yakuvobich $S$-lemma. SIAM J. Control Optim. 48, 4474–4480 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  40. Zalinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002)

    Book  MATH  Google Scholar 

Download references

Acknowledgments

The authors want to express their gratitude to both referees for their constructive criticism and helpful remarks, which have improved an earlier version of the present paper.

Author information

Authors and Affiliations

  1. Departamento de Ingeniería Matemática, CI2MA, Universidad de Concepción, Casilla 160-C, Concepción, Chile

    Fabián Flores-Bazán

  2. Departamento de Ingeniería Matemática, Universidad de Concepción, Casilla 160-C, Concepción, Chile

    Gabriel Cárcamo

Authors
  1. Fabián Flores-Bazán
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gabriel Cárcamo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fabián Flores-Bazán.

Additional information

This research, for the first author, was supported in part by CONICYT-Chile through FONDECYT 110-0667; 112-0980 and BASAL Projects, CMM, Universidad de Chile.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Flores-Bazán, F., Cárcamo, G. A geometric characterization of strong duality in nonconvex quadratic programming with linear and nonconvex quadratic constraints. Math. Program. 145, 263–290 (2014). https://doi.org/10.1007/s10107-013-0647-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-013-0647-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation