×

zbMATH — the first resource for mathematics

A clique algorithm for standard quadratic programming. (English) Zbl 1163.90691
Summary: A standard Quadratic Programming problem (StQP) consists in minimizing a (nonconvex) quadratic form over the standard simplex. For solving a StQP we present an exact and a heuristic algorithm, that are based on new theoretical results for quadratic and convex optimization problems. With these results a StQP is reduced to a constrained nonlinear minimum weight clique problem in an associated graph. Such a clique problem, which does not seem to have been studied before, is then solved with an exact and a heuristic algorithm. Some computational experience shows that our algorithms are able to solve StQP problems of at least one order of magnitude larger than those reported in the literature.

MSC:
90C20 Quadratic programming
05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Biggs, N., Some heuristic in graph coloring, (), pp. 87-96
[2] Bomze, I.M., Global escape strategies for maximizing quadratic forms over a simplex, Journal of global optimization, 11, 325-338, (1997) · Zbl 0904.90125
[3] Bomze, I.M., On standard quadratic optimization problems, Journal of global optimization, 13, 369-387, (1998) · Zbl 0916.90214
[4] Bomze, I.M.; Dür, M.; de Klerk, E.; Quist, A.; Roos, C.; Terlaky, T., On copositive programming and standard quadratic optimization problems, Journal of global optimization, 18, 301-320, (2000) · Zbl 0970.90057
[5] Bomze, I.M.; de Klerk, E., Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, Journal of global optimization, 24, 163-185, (2002) · Zbl 1047.90038
[6] Bomze, I.M.; Frommlet, F.; Rubey, M., Improved SDP bounds for minimizing quadratic functions over the \(l^1\)-ball, Optimization letters, 1, 49-59, (2007) · Zbl 1135.90377
[7] Bomze, I.M.; Locatelli, M.; Tardella, F., New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability, Mathematical programming, (2007) · Zbl 1171.90007
[8] Bomze, I.M.; Palagi, L., Quartic formulation of standard quadratic optimization problems, Journal of global optimization, 32, 181-205, (2005) · Zbl 1080.90057
[9] Coleman, T.F.; Li, Y., A reflective Newton method for minimizing a quadratic function subject to bounds on some of the variables, SIAM journal on optimization, 6, 1040-1058, (1996) · Zbl 0861.65053
[10] E. de Klerk, D.V. Pasechnik, A Linear Programming Reformulation of the Standard Quadratic Optimization Problem, CentER Discussion Paper Series No. 2005-24, Tilburg University, The Netherlands, Available at SSRN: http://ssrn.com/abstract=683106, 2005
[11] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval research logistics quarterly, 3, 95-110, (1956)
[12] Gibbons, L.E.; Hearn, D.W.; Pardalos, P.M.; Ramana, M.V., Continuous characterizations of the maximum clique problem, Mathematics of operations research, 22, 754-768, (1997) · Zbl 0883.90098
[13] Gill, P.E.; Murray, W.; Wright, M.H., Practical optimization, (1981), Academic Press London, UK · Zbl 0503.90062
[14] Motzkin, T.S.; Straus, E.G., Maxima for graphs and a new proof of a theorem of Turán, Canadian journal of mathematics, 17, 533-540, (1965) · Zbl 0129.39902
[15] Y.E. Nesterov, Global quadratic optimization on the sets with simplex structure, Discussion paper 9915, CORE, Katholic University of Louvain, Belgium, 1999
[16] Nesterov, Y.E.; Wolkowicz, H.; Ye, Y., Nonconvex quadratic optimization, (), pp. 361-416
[17] I. Nowak, Some heuristics and test problems for nonconvex quadratic programming over a simplex, Preprint 98-17, Humboldt University, Berlin, 1998
[18] I. Nowak, A global optimality criterion for nonconvex quadratic programming over a simplex, Preprint 98-18, Humboldt University, Berlin, 1998
[19] Nowak, I., A new semidefinite programming bound for indefinite quadratic forms over a simplex, Journal of global optimization, 14, 357-364, (1999) · Zbl 0959.65077
[20] Östergard, P.R.J., A new algorithm for the maximum-weigth clique problem, Nordic journal of computing, 8, 424-436, (2001) · Zbl 1003.68117
[21] Östergard, P.R.J., A fast algorithm for the maximum clique problem, Discrete applied mathematics, 120, 197-207, (2002) · Zbl 1019.05054
[22] Tardella, F., On the equivalence between some discrete and continuous optimization problems, Annals of operation research, 25, 291-300, (1990) · Zbl 0719.90057
[23] Tardella, F., Connections between continuous and combinatorial optimization problems through an extension of the fundamental theorem of linear programming, Electronic notes in discrete mathematics, 17, 257-262, (2004) · Zbl 1125.90403
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.