Abstract
A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP-hard problem has several immediate real-world applications like the Maximum Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. We propose unconstrained reformulations of StQPs, by using different approaches. We test our method on clique problems from the DIMACS challenge.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bomze IM (1992) Copositivity conditions for global optimality in indefinite quadratic programming problems. Czechoslov. J. Oper. Res. 1:7–19
Bomze IM (1997) Evolution towards the maximum clique. J Glob Optim 10:143–164
Bomze IM (1998) On standard quadratic optimization problems. J Glob Optim 13:369–387
Bomze IM (2009) Quadratic optimization: standard problems: I—theory; II—algorithms; III—applications. In: Floudas CA, Pardalos PM (eds) Encyclopedia of optimization, 2nd edn. Springer, New York
Bomze IM, Budinich M, Pardalos P, Pelillo M (1999) The maximum clique problem. In: Du D-Z, Pardalos PM (eds) Handbook of combinatorial optimization, vol A. Kluwer Academic, New York, pp 1–74. supp
Bomze I, Palagi L (2005) Quartic formulation of standard quadratic optimization. J Glob Optim 32:181–205
Burer S, Monteiro RDC (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math Program 95:329–357
Fletcher R (1981) Practical methods of optimization. Constrained optimization, vol 2. Wiley, New York
Grippo L, Sciandrone M (2002) Nonmonotone globalization techniques for the Barzilai–Borwein gradient method. Comput Optim Appl 23:143–169
Homer S, Peinado M (1997) Design and performance of parallel and distributed approximation algorithms for maxcut. J Parallel Distrib Comput 46:48–61
Johnson D, Trick MA (eds) (1996) Cliques coloring and satisfiability: second DIMACS implementation challenge. DIMACS series, vol 26. Am Math Soc, Providence
Júdice J, Sherali H, Ribeiro I (2007) The eigenvalue complementarity problem. Comput Optim Appl 37:139–156
Motzkin TS, Straus EG (1965) Maxima for graphs and a new proof of a theorem of Turán. Can J Math 17:533–540
Queiroz M, Júdice J, Humes C, Jr (2003) The symmetric eigenvalue complementarity problem. Math Comput 73:1849–1863
Author information
Authors and Affiliations
Corresponding author
Additional information
L. Grippo and L. Palagi acknowledge the support by MIUR PRIN National Research Program 20079PLLN7 “Nonlinear Optimization, Variational Inequalities and Equilibrium Problems”.
Rights and permissions
About this article
Cite this article
Bomze, I.M., Grippo, L. & Palagi, L. Unconstrained formulation of standard quadratic optimization problems. TOP 20, 35–51 (2012). https://doi.org/10.1007/s11750-010-0166-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-010-0166-4