Abstract

The classical Frank and Wolfe theorem states that a quadratic function which is bounded below on a convex polyhedron P attains its infimum on P. We investigate whether more general classes of convex sets F can be identified which have this Frank-and-Wolfe property. We show that the intrinsic characterizations of Frank-and-Wolfe sets hinge on asymptotic properties of these sets.

Author information

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

Juan-Enrique Martínez-Legaz

Dep. d'Economia i d'Història Econòmica, Universitat Autònoma de Barcelona, 08193 Bellaterra, Spain
and: Barcelona Graduate School of Mathematics, Spain

JuanEnrique.Martinez.Legaz@uab.es

Wilfredo Sosa

Programa de Pôs-Graduação em Economia, Universidade Católica de Brasilia, Brazil

sosa@ucb.br

Keywords

  • Quadratic optimization problem
  • asymptotes
  • conic asymptotes
  • Motzkin decomposition
  • Frank and Wolfe theorem
  • complementarity problem

Mathematics Subject Classification

90C20, 90C26

References

  1. B. Banks, J. Guddat, D. Klatte, B. Kummer, K. Tammer: Non-Linear Parametric Optimization, Springer-Verlag, Berlin (1983).https://doi.org/10.1007/978-3-0348-6328-5Google Scholar
  2. E. G. Belousov, D. Klatte: A Frank-and-Wolfe theorem for convex polynomial programs, Comp. Optim. Appl. 22 (2002) 37–48.https://doi.org/10.1023/A:1014813701864Google Scholar
  3. M. J. Best, B. Ding: On the continuity of the minimum in parametric quadratic programs, J. Optim. Theory Appl. 86(1) (1995) 245–250.https://doi.org/10.1007/BF02193469Google Scholar
  4. E. Blum, W. Oettli: Direct proof of the existence theorem in quadratic programming, Operations Research 20 (1972) 165–167.https://doi.org/10.1287/opre.20.1.165Google Scholar
  5. M. Frank, P. Wolfe: An algorithm for quadratic programming, Naval Res. Logistics Quarterly 3 (1956) 95–110.https://doi.org/10.1002/nav.3800030109Google Scholar
  6. M. S. Gowda: Minimising quadratic functionals over closed convex cones, Bull. Austr. Math. Soc. 39 (1989) 15–20.https://doi.org/10.1017/S0004972700027933Google Scholar
  7. W. M. Hirsch, A. J. Hoffman: Fixed charge problems, Communications Pure Appl. Math. 14 (1961) 355–369.https://doi.org/10.1002/cpa.3160140313Google Scholar
  8. A. N. Iusem, J. E. Martínez-Legaz, M. I. Todorov: Motzkin predecomposable sets, J. Global Optim. 60(4) (2014) 635–647.https://doi.org/10.1007/s10898-013-0097-3Google Scholar
  9. V. Klee: Asymptotes and projections of convex sets, Math. Scand. 8 (1960) 356–362.https://doi.org/10.7146/math.scand.a-10617Google Scholar
  10. Z.-Q. Luo, S. Zhang: On extensions of the Frank-Wolfe theorem, Comput. Optim. Appl. 13 (1999) 87–110.https://doi.org/10.1023/A:1008652705980Google Scholar
  11. A. F. Perold: A generalization of the Frank and Wolfe theorem, Math. Programming 18 (1980) 215–227.https://doi.org/10.1007/BF01588315Google Scholar
  12. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  13. A. Schrijver: Theory of Linear and Integer Programming, J. Wiley, Chichester (1986).Google Scholar
  14. N. N. Tam: Continuity of the optimal value function in indefinite quadratic programming, J. Global Optim. 23(1) (2002) 43–61.https://doi.org/10.1023/A:1014011906646Google Scholar
  15. D. S. Tiep, K. Kurdyka, O. Le Gal: Łojasiewicz inequality on non-compact domains and singularities at infinity, Int. J. Math. 24(10) (2013) 8 pages.https://doi.org/10.1142/S0129167X13500791Google Scholar

Suggested citation

J.-E. Martínez-Legaz, D. Noll, W. Sosa. “Minimization of Quadratic Functions on Convex Sets without Asymptotes.” Journal of Convex Analysis 25 (2018), No. 2, 623–641. https://doi.org/10.68381/jca25038

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2018. Rights now held by Banach Press.