Публікація: Напіввизначена оптимізація для розв'язування загальних квадратичних задач
Завантаження...
Дата
2015
Автори
Назва журналу
ISSN журналу
Назва тома
Видавництво
Анотація
У дисертаційній роботі удосконалюються теорія та чисельні методи напіввизначеної оптимізації, розширюється її використання для розв’язування загальних квадратичних задач, які виникають при математичному моделюванні складних систем. Як альтернативу прямо-двоїстим методам внутрішньої точки для розв’язування задач напіввизначеної оптимізації удосконалено та обґрунтовано напіввизначений симплекс-метод, визначені його теоретичні та чисельні переваги. Для методів напів-визначеної оптимізації розроблена ефективна процедура визначення додатної напів-визначеності матриці з використанням методу спряжених напрямів. У роботі розглянута напіввизначена релаксація, яка дозволяє перетворювати загальні квадратичні задачі до задач напіввизначеної оптимізації. Знайдені перетворення початкової квадратичної задачі, які уточнюють напіввизначену релаксацію. Зокрема, для таких перетворень використана точна квадратична регуляризація, яка дозволяє отримувати точну напіввизначену релаксацію для визначених класів задач квадратичної оптимізації. Запропоновано та перевірено на практиці нову процедуру знаходження верхніх і нижніх оцінок цільової функції у загальних задачах квадратичної оптимізації. Виконані значні порівняльні експерименти свідчать про перевагу розроблених методів при розв’язуванні складних багатоекстремальних квадратичних задач.
The thesis is devoted to theory and numerical methods for semidefinite optimization and to its use for solving general quadratic problems arising in mathematical modeling of complex systems. As alternative to primal-dual interior point methods semidefinite simplex-method was improved and proved, its theoretical and numerical advantages were defined. For se-midefinite optimization methods an effective procedure for determination of positive semi-definiteness of matrices using the method of conjugate directions was developed. Much attention is given to semidefinite relaxation which allows to transform general quadratic problems to semidefinite optimization problems. The transformations of initial quadratic problem, that refine the semidefinite relaxation, were found. In particular, for such transformations the exact quadratic regularization was used, which enables to get exact semidefinite relaxation for certain classes of quadratic optimization problems. The new procedure of finding the upper and lower bounds of the objective function in the ge-neral quadratic optimization problems was proposed and tested. Significant comparative experiments show the superiority of the developed methods for solving complex quadratic multi-extremal problems.
Опис
Ключові слова
напіввизначена оптимізація, загальна квадратична задача, напіввизначений симплекс-метод, напіввизначена релаксація, semidefinite optimization, general quadratic problem, semidefinite sim-plex-method, emidefinite relaxation
Бібліографічний опис
Перетятько А. С. Напіввизначена оптимізація для розв'язування загальних квадратичних задач : автореф. дис. ... канд. фіз.-мат. наук : 01.05.02 "Математичне моделювання та обчислювальні методи" / А. С. Перетятько ; М-во освіти і науки України, ДВНЗ "Укр. держ. хім.-технол. ун-т". – Дніпропетровськ, 2015. – 181 с.