article

On Copositive Programming and Standard Quadratic Optimization Problems

Authors:

Immanuel M. Bomze,

Etienne De Klerk,

Tamás TerlakyAuthors Info & Claims

Journal of Global Optimization, Volume 18, Issue 4

Pages 301 - 320

https://doi.org/10.1023/A:1026583532263

Published: 01 December 2000 Publication History

Abstract

A standard quadratic problem consists of finding global maximizers of a quadratic form over the standard simplex. In this paper, the usual semidefinite programming relaxation is strengthened by replacing the cone of positive semidefinite matrices by the cone of completely positive matrices (the positive semidefinite matrices which allow a factorization FF^T where F is some non-negative matrix). The dual of this cone is the cone of copositive matrices (i.e., those matrices which yield a non-negative quadratic form on the positive orthant). This conic formulation allows us to employ primal-dual affine-scaling directions. Furthermore, these approaches are combined with an evolutionary dynamics algorithm which generates primal-feasible paths along which the objective is monotonically improved until a local solution is reached. In particular, the primal-dual affine scaling directions are used to escape from local maxima encountered during the evolutionary dynamics phase.

References

[1]

1. Baum, L. E. and Eagon, J. A. (1967), An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull. Amer. Math. Soc. 73: 360-363.

[2]

2. Baum, L. E. and Sell, G. R. (1968), Growth transformations for functions on manifolds. Pacif. J. Math. 27: 211-227.

[3]

3. Berman, A. (1988), Complete positivity. Linear Algebra Appl. 107: 57-63.

[4]

4. Berman, A. and Hershkowitz, D. (1987), Combinatorial results on completely positive matrices. Linear Algebra Appl. 95: 111-125.

[5]

5. Bomze, I. M. (1987), Remarks on the recursive structure of copositivity. J. Inf. Optimiz. Sci. 8: 243-260.

[6]

6. Bomze, I. M. (1996), Block pivoting and shortcut strategies for detecting copositivity. Linear Algebra Appl. 248: 161-184.

[7]

7. Bomze, I. M. (1997), Evolution towards the maximum clique. J. Global Optimiz. 10: 143-164.

Digital Library

[8]

8. Bomze, I. M. (1997), Global escape strategies for maximizing quadratic forms over a simplex. J. Global Optimiz. 11: 325-338.

Digital Library

[9]

9. Bomze, I. M. (1998), On standard quadratic optimization problems. J. Global Optimiz. 13: 369- 387.

Digital Library

[10]

10. Bomze, I. M. (2000), Linear-time detection of copositivity for tridiagonal matrices and extension to block-tridiagonality. SIAM J. Matrix Anal. Appl. 21: 840-848.

Digital Library

[11]

11. Bomze, I. M., Pelillo, M. and Giacomini, R. (1997), Evolutionary approach to the maximum clique problem: empirical evidence on a larger scale. In: Bomze, I. M., Csendes, T., Horst, R. and Pardalos, P. M. (eds.), Developments in Global Optimization, Kluwer, Dordrecht, pp. 95-108.

[12]

12. Bomze, I. M. and Stix, V. (1999), Genetical engineering via negative fitness: evolutionary dynamics for global optimization. Annals of O.R. 89: 279-318.

[13]

13. Crow, J. F., Kimura, M. (1970), An Introduction to Population Genetics Theory, Harper & Row, New York.

[14]

14. Danninger, G. (1990), A recursive algorithm to detect (strict) copositivity of a symmetric matrix. In: Rieder, U., Gessner, P., Peyerimhoff, A. and Radermacher, F. J., (eds.), Methods of Operations Research 62: 45-52. Hain, Meisenheim.

[15]

15. Drew, J. H., Johnson, C. R. and Loewy, R. (1994), Completely positive matrices associated with M-matrices. Linear and Multilinear Algebra 37: 303-310.

[16]

16. Fujisawa, K., Kojima, M. and Nakata, K. (1997), Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. Math. Prog. 79: 235-253.

Digital Library

[17]

17. Fukuda, M., Kojima, M., Murota, K. and Nakata, K. (1999), Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework, Research Report B-358, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo 152-8552, Japan.

[18]

18. Goemans, M. X. (1997), Semidefinite programming in combinatorial optimization. Math. Prog. 79: 143-161.

Digital Library

[19]

19. Hadeler, K. P. (1983), On copositive matrices. Linear Algebra Appl. 49: 79-89.

[20]

20. Hall, M., Jr. and M. Newman, (1963), Copositive and completely positive quadratic forms. Proc. Cambridge Philos. Soc. 59: 329-339.

[21]

21. Hannah, J. and Laffey, T. J. (1983), Nonnegative factorization of completely positive matrices. Linear Algebra Appl. 55: 1-9.

[22]

22. Helmberg, C., Rendl, F., Vanderbei, R. J. and Wolkowicz, H. (1996), An interior-point method for semidefinite programming. SIAM J. Optimiz. 6: 342-361.

[23]

23. Hofbauer, J. and Sigmund, K. (1988), The Theory of Evolution and Dynamical Systems. Cambridge University Press, Cambridge, UK.

[24]

24. Horst, R., Pardalos, P. M. and Thoai, N. V. (1995), Introduction to Global Optimization, Kluwer, Dordrecht.

Digital Library

[25]

25. Hummel, R. A. and Zucker, S. W. (1983), On the foundations of relaxation labeling processes. IEEE Trans. Pattern Anal. Machine Intell. 5: 267-287.

Digital Library

[26]

26. Jansen, B., Roos, C. and Terlaky, T. (1995), Interior point methods: a decade after Karmarkar. A survey, with application to the smallest eigenvalue problem. Statistica Neerlandica 50: 146- 170.

[27]

27. Kaykobad, M. (1987), On nonnegative factorization matrices. Linear Algebra Appl. 96: 27-33.

[28]

28. Klerk, E. de, Roos, C. and Terlaky, T. (1998), Polynomial primal-dual affine scaling algorithms in semidefinite programming. J. Combin. Optimiz. 2: 51-69.

[29]

29. Kojima, M., Shindoh, S. and Hara, S. (1997), Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optimiz. 7: 86-125.

Digital Library

[30]

30. Kojima, M. and Tunçel, L. (1998), Monotonicity of primal-dual interior-point algorithms for semidefinite programming problems. Optimiz. Methods Softw. 10: 275-296.

[31]

31. Lau, C. M. and Markham, T. L., (1978), Square triangular factorizations of completely positive matrices. J. Ind. Math. Soc. 28: 15-24.

[32]

32. Levinson, S. E., Rabiner, L. R. and Sondhi, M. M. (1983), An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition. Bell Syst. Tech. J. 62: 1035-1074.

[33]

33. Lyubich, Y., Maistrowskii, G. D. and Ol'khovskii, Yu.G. (1980), Selection-induced convergence to equilibrium in a single-locus autosomal population. Problems of Information Transmission 16: 66-75.

[34]

34. Markham, T. L. (1971), Factorizations of completely positive matrices. Proc. Cambridge Philos. Soc. 69: 53-58.

[35]

35. Martin, D. H. and Jacobson, D. H. (1981), Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraints, Linear Algebra Appl. 35: 227-258.

[36]

36. Monteiro, R. D. C. (1997), Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optimiz. 7: 663-678.

Digital Library

[37]

37. Muramatsu, M. and Vanderbei, R. J. (1997), Primal-dual affine-scaling algorithm fails for semidefinite programming. Technical Report SOR 97-04, Princeton University, NJ 08544.

[38]

38. Murty, K. G. and Kabadi, S. N. (1987), Some NP-complete problems in quadratic and linear programming. Math. Prog. 39: 117-129.

Digital Library

[39]

39. Nesterov, Y. E. and Nemirovskii, A. S. (1994), Interior point methods in convex programming: theory and applications. SIAM, Philadelphia, PA.

[40]

40. Nowak, I. (1999), A new semidefinite programming bound for indefinite quadratic forms over a simplex. J. Global Optimiz. 14: 357-364.

Digital Library

[41]

41. Pelillo, M. (1994), On the dynamics of relaxation labeling processes. Proc. IEEE Int. Conf. Neural Networks, Orlando, FL, pp. 1006-1011.

[42]

42. Pelillo, M. (1995), Relaxation labeling networks for the maximum clique problem. J. Artif. Neural Networks 2: 313-327.

Digital Library

[43]

43. Raber, U. (1999), Nonconvex all-quadratic global optimization problems: solution methods, application and related topics. Ph.D. dissertation, University of Trier.

[44]

44. Rosenfeld, A., Hummel, R. A. and Zucker, S. W. (1976), Scene labeling by relaxation operations. IEEE Trans. Syst. Man Cybern. 6: 420-433.

[45]

45. Quist, A. J., de Klerk, E., Roos, C. and Terlaky, T. (1998), Copositive relaxation for general quadratic programming. Optimiz. Methods Softw. 9: 185-209.

[46]

46. Sigmund, K. (1987), Game dynamics, mixed strategies, and gradient systems. Theor. Pop. Biol. 32: 114-126.

[47]

47. Tunçel, L. (1999), Generalization of primal-dual interior-point methods to convex optimization problems in conic form. Technical Report CORR 99-35, University of Waterloo.

[48]

48. Väliaho, H. (1986), Criteria for copositive matrices. Linear Algebra Appl. 81: 19-34.

[49]

49. Väliaho, H. (1988), Testing the definiteness of matrices on polyhedral cones. Linear Algebra Appl. 101: 135-165.

[50]

50. Väliaho, H. (1989), Quadratic-programming criteria for copositive matrices. Linear Algebra Appl. 119: 163-182.

[51]

51. Xiang, S. H. and Xiang, S. W. (1998), Notes on completely positive matrices. Linear Algebra Appl. 271: 273-282.

Cited By

Qiu YYıldırım E(2025)Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxationsMathematical Programming: Series A and B10.1007/s10107-024-02070-7209:1(397-433)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s10107-024-02070-7
Fearnley JGoldberg PHollender ASavani RMohar BShinkar IO'Donnell R(2024)The Complexity of Computing KKT Solutions of Quadratic ProgramsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649647(892-903)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649647
Nishijima MNakata K(2024)Approximation hierarchies for copositive cone over symmetric cone and their comparisonJournal of Global Optimization10.1007/s10898-023-01319-388:4(831-870)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10898-023-01319-3
Show More Cited By

On Copositive Programming and Standard Quadratic Optimization Problems

Recommendations

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 ...
A clique algorithm for standard quadratic programming

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 ...
Tightening a copositive relaxation for standard quadratic optimization problems

We focus in this paper the problem of improving the semidefinite programming (SDP) relaxations for the standard quadratic optimization problem (standard QP in short) that concerns with minimizing a quadratic form over a simplex. We first analyze the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Global Optimization

Journal of Global Optimization Volume 18, Issue 4

December 2000

114 pages

ISSN:0925-5001

Issue’s Table of Contents

Copyright © Copyright © 2000 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2000

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Qiu YYıldırım E(2025)Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxationsMathematical Programming: Series A and B10.1007/s10107-024-02070-7209:1(397-433)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s10107-024-02070-7
Fearnley JGoldberg PHollender ASavani RMohar BShinkar IO'Donnell R(2024)The Complexity of Computing KKT Solutions of Quadratic ProgramsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649647(892-903)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649647
Nishijima MNakata K(2024)Approximation hierarchies for copositive cone over symmetric cone and their comparisonJournal of Global Optimization10.1007/s10898-023-01319-388:4(831-870)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10898-023-01319-3
Cui YLiang LSun DToh K(2022)On Degenerate Doubly Nonnegative Projection ProblemsMathematics of Operations Research10.1287/moor.2021.120547:3(2219-2239)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1287/moor.2021.1205
Nguyen D(2022)Strong Duality for General Quadratic Programs with Quadratic Equality ConstraintsJournal of Optimization Theory and Applications10.1007/s10957-022-02082-3195:1(297-313)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10957-022-02082-3
Zhang BGao YLiu XHuang X(2022)Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problemsJournal of Global Optimization10.1007/s10898-022-01255-886:1(61-92)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1007/s10898-022-01255-8
Kostyukova OTchemisova T(2022)On strong duality in linear copositive programmingJournal of Global Optimization10.1007/s10898-021-00995-383:3(457-480)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10898-021-00995-3
Bomze IPeng B(2022)Conic formulation of QPCCs applied to truly sparse QPsComputational Optimization and Applications10.1007/s10589-022-00440-584:3(703-735)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1007/s10589-022-00440-5
Lai ZYoshise A(2022)Completely positive factorization by a Riemannian smoothing methodComputational Optimization and Applications10.1007/s10589-022-00417-483:3(933-966)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s10589-022-00417-4
Gökmen YYıldırım E(2022)On standard quadratic programs with exact and inexact doubly nonnegative relaxationsMathematical Programming: Series A and B10.1007/s10107-020-01611-0193:1(365-403)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s10107-020-01611-0
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents