article

A clique algorithm for standard quadratic programming

Authors:

Andrea Scozzari,

Fabio TardellaAuthors Info & Claims

Discrete Applied Mathematics, Volume 156, Issue 13

Pages 2439 - 2448

https://doi.org/10.1016/j.dam.2007.09.020

Published: 01 July 2008 Publication History

Abstract

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.

References

[1]

Biggs, N., Some heuristic in graph coloring. In: Nelson, R., Wilson, R.J. (Eds.), Graph Colourings, Longman, New York.

[2]

Bomze, I.M., Global escape strategies for maximizing quadratic forms over a simplex. Journal of Global Optimization. v11. 325-338.

Digital Library

[3]

Bomze, I.M., On standard quadratic optimization problems. Journal of Global Optimization. v13. 369-387.

Digital Library

[4]

Bomze, I.M., Dür, M., de Klerk, E., Quist, A., Roos, C. and Terlaky, T., On copositive programming and standard quadratic optimization problems. Journal of Global Optimization. v18. 301-320.

Digital Library

[5]

Bomze, I.M. and de Klerk, E., Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Journal of Global Optimization. v24. 163-185.

Digital Library

[6]

Bomze, I.M., Frommlet, F. and Rubey, M., Improved SDP bounds for minimizing quadratic functions over the l1-ball. Optimization Letters. v1. 49-59.

[7]

Bomze, I.M., Locatelli, M. and Tardella, F., New and old bounds for standard quadratic optimization: Dominance, equivalence and incomparability. Mathematical Programming.

Digital Library

[8]

Bomze, I.M. and Palagi, L., Quartic formulation of standard quadratic optimization problems. Journal of Global Optimization. v32. 181-205.

Digital Library

[9]

Coleman, T.F. and Li, Y., A reflective Newton method for minimizing a quadratic function subject to bounds on some of the variables. SIAM Journal on Optimization. v6. 1040-1058.

Digital Library

[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. and Wolfe, P., An algorithm for quadratic programming. Naval Research Logistics Quarterly. v3. 95-110.

[12]

Gibbons, L.E., Hearn, D.W., Pardalos, P.M. and Ramana, M.V., Continuous characterizations of the maximum clique problem. Mathematics of Operations Research. v22. 754-768.

[13]

Gill, P.E., Murray, W. and Wright, M.H., Practical Optimization. 1981. Academic Press, London, UK.

[14]

Motzkin, T.S. and Straus, E.G., Maxima for graphs and a new proof of a theorem of Turán. Canadian Journal of Mathematics. v17. 533-540.

[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. and Ye, Y., Nonconvex quadratic optimization. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (Eds.), Handbook of Semidefinite Programming, Kluwer Academic Publishers, Dordrecht.

[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. v14. 357-364.

Digital Library

[20]

Östergard, P.R.J., A new algorithm for the maximum-weigth clique problem. Nordic Journal of Computing. v8. 424-436.

Digital Library

[21]

Östergard, P.R.J., A fast algorithm for the maximum clique problem. Discrete Applied Mathematics. v120. 197-207.

Digital Library

[22]

Tardella, F., On the equivalence between some discrete and continuous optimization problems. Annals of Operation Research. v25. 291-300.

Digital Library

[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. v17. 257-262.

Cited By

Bomze IPeng BQiu YYıldırım E(2025)On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity ConstraintsJournal of Optimization Theory and Applications10.1007/s10957-024-02593-1204:3Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s10957-024-02593-1
Gondzio JYıldırım E(2021)Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulationsJournal of Global Optimization10.1007/s10898-021-01017-y81:2(293-321)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10898-021-01017-y
Chen XPittel B(2021)On sparsity of the solution to a random quadratic optimization problemMathematical Programming: Series A and B10.1007/s10107-019-01456-2186:1-2(309-336)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10107-019-01456-2
Show More Cited By

Index Terms

A clique algorithm for standard quadratic programming
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Quadratic programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Quadratic programming

Recommendations

An algorithm for non-linear multi-level integer programming problems

In this paper, an algorithm is proposed to solve a tri-level integer programming problem in which the objective function for the first level is an indefinite quadratic, the second one is linear and the third one is linear fractional. The feasible space ...
An algorithm for indefinite quadratic programming with convex constraints

We propose a branch-and-bound method for minimizing an indefinite quadratic function over a convex set. The bounding operation is based on a certain relaxation of the constraints. The branching is a simplex bisection.
Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming

The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 156, Issue 13

July, 2008

146 pages

ISSN:0166-218X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2007.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 July 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bomze IPeng BQiu YYıldırım E(2025)On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity ConstraintsJournal of Optimization Theory and Applications10.1007/s10957-024-02593-1204:3Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s10957-024-02593-1
Gondzio JYıldırım E(2021)Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulationsJournal of Global Optimization10.1007/s10898-021-01017-y81:2(293-321)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10898-021-01017-y
Chen XPittel B(2021)On sparsity of the solution to a random quadratic optimization problemMathematical Programming: Series A and B10.1007/s10107-019-01456-2186:1-2(309-336)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10107-019-01456-2
Xia WVera JZuluaga L(2020)Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming TechniquesINFORMS Journal on Computing10.1287/ijoc.2018.088332:1(40-56)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1287/ijoc.2018.0883
Chen XPeng J(2015)New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and ExtensionsMathematics of Operations Research10.1287/moor.2014.069240:3(725-738)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1287/moor.2014.0692
Misener RFloudas C(2014)ANTIGONEJournal of Global Optimization10.1007/s10898-014-0166-259:2-3(503-526)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1007/s10898-014-0166-2

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents