Semidefinite symplex-method for solving the quadratic optimization problems

Authors

  • Анатолий Иванович Косолап Ukrainian State University of Chemical Technology Gagarina 8, Dnipropetrovsk, Ukraine, 49001, Ukraine

DOI:

https://doi.org/10.15587/1729-4061.2013.19107

Keywords:

quadratic functions, semidefinite relaxation, semidefinite optimization, semidefinite simplex method, interior-point method

Abstract

We propose a new semidefinite simplex-method for solving the semidefinite optimization problems. In this paper, a general quadratic problem is transformed to a linear semidefinite one using a semidefinite relaxation. We look for a semidefinite matrix in the semidefinite optimization problem. Such matrix can be represented as a sum of the rank-one matrices. The proposed semidefinite simplex-method uses the semidefinite matrix in the form of a linear combination of matrices of the rank-one matrices. We find each such matrix solving the problem of minimizing the quadratic form. If the minimum of the quadratic form is non-negative, the semi-definite optimization problem is solved. Otherwise, we continue to search the rank-one matrix, which will reduce the value of the objective function of the semidefinite optimization problem. In general, solution of the semidefinite optimization problem defines only the lower bound of the solution of the initial quadratic problem. We use this solution as a starting point for the quadratic optimization problem. We solve this problem by a primal-dual interior-point method. The numerical experiments showed that the found solution often coincides with the point of global minimum of the quadratic optimization problem.

Author Biography

Анатолий Иванович Косолап, Ukrainian State University of Chemical Technology Gagarina 8, Dnipropetrovsk, Ukraine, 49001

Professor

Department of Specialized Computer Systems

References

  1. Vandenberghe, L. Semidefinite programming [Текст] /L. Vandenberghe, S. Boyd // SIAM Review. – 1996. – vol. 38. – P. 49–95.
  2. Косолап, А. И. Методы глобальной оптимизации [Текст] / А. И. Косолап. – Днепропетровск: Наука и образование, 2013. – 318 с.
  3. Todd, M. J. Semidefinite optimization [Текст] / M. J. Todd //Acta Numerica. – 2001. – № 10. – Р. 515–560.
  4. Horst, R. Global Optimization: Deterministic Approaches, 3rd ed. [Текст] / R. Horst, H. Tuy.  Springer-Verlag, Berlin, 1996. – 726 p.
  6. . Шор, Н. З. Квадратичные экстремальные задачи и недифференцируемая оптимизация [Текст] / Н. З. Шор, С. И. Стеценко. – К.: Наукова думка, 1989.– 205с.
  7. Floudas, C. A. Quadratic optimization [Текст] / C. A. Floudas, V. Visweswaran.  Princeton University, Princeton, 1995.  53 p.
  8. Ding, Y. On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic Programming [Текст] / Y. Ding. – Waterloo, Ontario, Canada. – 2007. – 68 p.
  9. Данциг, Дж. Линейное программирование его обобщение и применение [Текст] / Дж. Данциг; пер. с англ. Г. Н. Андрианова, Л. И. Горькова, А. А. Корбута, А. Н. Ляпунова; под ред. Н. Н. Воробьева. – М.: Прогресс, 1966. – 600 с.
  10. Nocedal, J. Numerical optimization [Текст] / J. Nocedal, S. J. Wright. – Springer, 2006. – 685 p.
  11. Nesterov, Y. Interior point polynomial algorithms in convex programming [Текст] /Y. Nesterov, A. S. Nemirovskii // SIAM Studies in Applied Mathematics. – 1994. – Vol. 13. – SIAM, Philadelphia,USA. – 405 p.
  12. Epperly, T. G. W. Global optimization test problem with solution [Электронный ресурс] /T. G. W.Epperly, R. E.Swaney. – 1995. – 34 p. Available at http://citeseer.nj.nec.com /147308.html.
  13. Aguirre, A. H. COPSO: Constrained Optimization via PSO algorithm. Appendix A: Benchmark functions [Электронный ресурс]/ A. H. Aguirre, A. E. M. Zavala, E. V. Diharce, S. B. Rionda. – 2007. – P. 21–28. Available at
  14. http://www.cimaf.mx/reports/enlinea/I-07-04.pdf.
  15. Martello, S. Knapsack problems: algorithms and computer implementation [Текст] / S. Martello, P. Toth. – Chichester: John Wiley & SONS, 1990. – 296 p.
  16. Vandenberghe, L., Boyd S. (1996). Semidefinite programming, SIAM Review, 38, 49–95.
  17. Kosolap, A. (2013). Methods of global optimization, Dn-sk, Science and Education, 318.
  18. Todd, M. J. (2001). Semidefinite optimization, Acta Numerica, 10, 515–560.
  19. Horst, R., Tuy, H. (1996). Global Optimization: Deterministic Approaches, 3rd ed., Springer-Verlag, Berlin, 726.
  20. Schor, N. Z., Stesenko, S. I. (1989). Quadratic extreme of problems and nondifferential optimization, 205.
  21. Floudas, C. A., Visweswaran, V. (1995) Quadratic optimization, Princeton University, Princeton, 53.
  22. Ding, Y. (2007). On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic Programming, Waterloo, Ontario, Canada, 68.
  23. Dantzig, G. B. (1963). Linear programming and extensions, Princeton University Press, Princeton.
  24. Nocedal, J., Wright, S.J. (2006). Numerical optimization, Springer, 685.
  25. Nesterov, Y., Nemirovskii, A. S. (1994). Interior point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, SIAM, Philadelphia,USA, 13, 405.
  26. Epperly, T. G. W., Swaney, R. E. (1995). Global optimization test problem with solution, 34. http://citeseer.nj.nec.com /147308.html.
  27. Aguirre, A. H., Zavala, A. E. M., Diharce, E. V., Rionda, S. B. (2007). COPSO: Constrained Optimization via PSO algorithm. Appendix A: Benchmark functions. http://www.cimaf.mx/reports/enlinea/I-07-04.pdf.
  28. Martello, S., Toth, P. (1990). Knapsack problems: algorithms and computer implementation, Chichester: John Wiley & SONS, 296.

Downloads

Published

2013-12-16

How to Cite

Косолап, А. И. (2013). Semidefinite symplex-method for solving the quadratic optimization problems. Eastern-European Journal of Enterprise Technologies, 6(4(66), 21–24. https://doi.org/10.15587/1729-4061.2013.19107

Issue

Vol. 6 No. 4(66) (2013): Mathematics and cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2014 Анатолий Иванович Косолап

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.