Напіввизначений симплекс-метод для розв’язання задач квадратичної оптимізації

Автор(и)

  • Анатолий Иванович Косолап Український державний хіміко-технологічний університет пр. Гагаріна, 8, г. Дніпропетровськ, Україна, 49001, Україна

DOI:

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

Ключові слова:

квадратичні функції, напіввизначена релаксація, напіввизначенний симплекс-метод, метод внутрішньої точки

Анотація

Розглядається загальна задача квадратичної мінімізації з квадратичними обмеженнями. За допомогою напіввизначеної релаксації вона перетворюється до задачі лінійної напіввизначеної оптимізації, розв’язок якої дозволяє знайти нижню оцінку розв’язку квадратичної задачі. Знайдений розв’язок використовується в якості початкової точки в прямо-двоїстому методі внутрішньої точки для розв’язання квадратичної задачі. Чисельні експерименти показали ефективність запропонованого методу.

Біографія автора

Анатолий Иванович Косолап, Український державний хіміко-технологічний університет пр. Гагаріна, 8, г. Дніпропетровськ, Україна, 49001

Доктор фізико-математических наук, професор

Кафедра специалізованих комп’ютерных систем

Посилання

  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.

##submission.downloads##

Опубліковано

2013-12-16

Як цитувати

Косолап, А. И. (2013). Напіввизначений симплекс-метод для розв’язання задач квадратичної оптимізації. Eastern-European Journal of Enterprise Technologies, 6(4(66), 21–24. https://doi.org/10.15587/1729-4061.2013.19107

Номер

Том 6 № 4(66) (2013): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2014 Анатолий Иванович Косолап

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.