×

zbMATH — the first resource for mathematics

New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. (English) Zbl 1171.90007
For the problem of minimizing a quadratic indefinite form over a simplex known and new bounds for the optimal objective function value are derived. Main tools for this are semidefinite programming and the decomposition of the objective function into the difference of two convex functions. The different bounds are completely compared and a new bound is developed which dominates all the other bounds, especially also Shrijver’s improvement of Lovasz’s \(\theta\) function. Interesting results are also obtained with respect to the Lagrangean duality, where tight dual formulations are found. Special topics in this interesting and comprehensive paper are convex underestimation bounds, Nowak’s bound and copositive as well as decomposition bounds.

MSC:
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstreicher K. and Burer S. (2005). D.C. Versus copositive bounds for standard QP. J. Glob. Optim. 33: 299–312 · Zbl 1093.90033
[2] Bomze I.M. (1998). On standard quadratic optimization problems. J. Glob. Optim. 13: 369–387 · Zbl 0916.90214
[3] Bomze I.M. (2000). Copositivity aspects of standard quadratic optimization problems. In: Dockner, E., Hartl, R., Luptacik, M. and Sorger, G. (eds) Dynamics, Optimization and Economic Analysis., pp 1–11. Physica, Heidelberg · Zbl 0990.90090
[4] Bomze I.M. (2002). Branch-and-bound approaches to standard quadratic optimization problems. J. Glob. Optim. 22: 17–37 · Zbl 1045.90042
[5] Bomze I.M., Dür M., de Klerk E., Quist A., Roos C. and Terlaky T. (2000). On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18: 301–320 · Zbl 0970.90057
[6] Bomze I.M. and de Klerk E. (2002). Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24: 163–185 · Zbl 1047.90038
[7] Bomze I.M. and Locatelli M. (2004). Undominated d.c. decompositions of quadratic functions and applications to branch-and-bound approaches. Comput. Optim. Appl. 28(2): 227–245 · Zbl 1056.90112
[8] Bomze, I.M., Locatelli, M., Tardella, F.: Efficient and cheap bounds for (Standard) Quadratic Optimization, Technical Report dis tr 2005/2010, Dipartimento di Informatica e Sistemistica ”Antonio Ruberti”, Universitá degli Studi di Roma ”La Sapienza”, available at http://www.optimization-online.org/DB_HTML/2005/07/1176.html (2005) · Zbl 1171.90007
[9] Boyd S. and Vandenberghe L. (2004). Convex Optimization. Cambridge University Press, Cambridge · Zbl 1058.90049
[10] Laurent M., Parrillo P.A. and Klerk E. (2006). A PTAS for the minimization of polynomials of fixed degree over the simplex. Theor. Comp. Sci. 361: 210–225 · Zbl 1115.90042
[11] de Klerk E. and Pasechnik D.V. (2002). Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12: 875–892 · Zbl 1035.90058
[12] Diananda P.H. (1967). On non-negative forms in real variables some or all of which are non-negative. Proc. Camb. Philos. Soc. 58: 17–25 · Zbl 0108.04803
[13] Dür M. (2002). A class of problems where dual bounds beat underestimation bounds. J. Glob. Optim. 22: 49–57 · Zbl 1045.90078
[14] Falk J. (1969). Lagrange multipliers and nonconvex programs. SIAM J. Control 7: 312–321 · Zbl 0184.44404
[15] Frank M. and Wolfe P. (1956). An algorithm for quadratic programming. Naval Res. Logist. Q. 3: 95–110
[16] Gibbons L.E., Hearn D.W., Pardalos P.M. and Ramana M.V. (1997). Continuous characterizations of the maximum clique problem. Math. Oper. Res. 22: 754–768 · Zbl 0883.90098
[17] Gower J.C. (1985). Properties of Euclidean and non-Euclidean distance matrices. Linear Algebra Appl. 67: 81–97 · Zbl 0569.15016
[18] Horst R. and Tuy H. (1990). Global Optimization: Deterministic Approaches. Springer, Berlin · Zbl 0704.90057
[19] Ibaraki T. and Katoh N. (1988). Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge · Zbl 0786.90067
[20] Lasserre J.B. (2001). Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11: 796–817 · Zbl 1010.90061
[21] Lemaréchal, C., Oustry, F.: Semidefinite relaxations and Lagranian duality with application to combinatorial optimization, INRIA research report, vol. 3710 (1999)
[22] Markowitz H.M. (1952). Portfolio selection. J. Finance 7: 77–91
[23] Markowitz H.M. (1995). The general mean-variance portfolio selection problem. In: Howison, S.D., Kelly, F.P. and Wilmott, P. (eds) Mathematical Models in Finance, vol. 93–99., pp. Chapman & Hall, London · Zbl 0854.90014
[24] Motzkin T.S. and Straus E.G. (1965). Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17: 533–540 · Zbl 0129.39902
[25] Nesterov, Y.E.: Global Quadratic Optimization on the Sets with Simplex Structure, Discussion paper 9915, CORE. Catholic University of Louvain, Belgium (1999)
[26] Nowak I. (1999). A new semidefinite programming bound for indefinite quadratic forms over a simplex. J. Glob. Optim. 14: 357–364 · Zbl 0959.65077
[27] Pena J., Vera J. and Zuluaga L. (2007). Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18: 87–105 · Zbl 1176.90611
[28] Rockafellar R.T. (1970). Convex analysis. Princeton University Press, Princeton · Zbl 0193.18401
[29] Schrijver A. (1979). A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Theory 25: 425–429 · Zbl 0444.94009
[30] Sahinidis N.V. and Tawarmalani M. (2002). Convex extensions and envelopes of lower semi-continuous functions. Math. Prog. 93: 247–263 · Zbl 1065.90062
[31] Tardella F. (1990). On the equivalence between some discrete and continuous optimization problems. Ann. Oper. Res. 25: 291–300 · Zbl 0719.90057
[32] Tardella F. (2004). Connections between continuous and combinatorial optimization problems through an extension of the fundamental theorem of linear programming. Electron. Notes Discret. Math. 17: 257–262 · Zbl 1125.90403
[33] Tuy, H.: A general deterministic approach to global optimization via d.c. programming. In: Fermat days 85: Mathematics for optimization, vol. 129. North-Holland Math. Stud., Toulouse/France, pp. 273–303 (1985)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.