2020, випуск 1, c. 15-22
Одержано 03.03.2020; Виправлено 07.03.2020; Прийнято 10.03.2020
Надруковано 31.03.2020; Вперше Online 26.04.2020
https://doi.org/10.34229/2707-451X.20.1.2
Попередня | Повний текст | Наступна
Покращення лагранжевих двоїстих оцінок для квадратичних екстремальних задач
О.А.
Березовський 1 * 
1 Інститут кібернетики імені В.М. Глушкова, Київ, Україна
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. У зв’язку з тим, що квадратичні екстремальні задачі в загальному випадку є NP-складними, використовують різні опуклі релаксації для знаходження оцінок їх глобальних екстремумів: лагранжеві релаксації, SDP-релаксації, SOCP-релаксації, LP-релаксації та інші. В цій роботі досліджується двоїста оцінка, яка є результатом лагранжевої релаксації квадратичної екстремальної задачі за всіма обмеженнями. Головне питання при використанні такого підходу для розв’язування квадратичних екстремальних задач – це якість отриманих оцінок (величина розриву двоїстості) та можливості їх покращення. Якщо для квадратичних задач опуклої оптимізації такі оцінки є точними, то в інших випадках це питання досить складне. У неопуклих випадках для покращення двоїстих оцінок (зменшення розриву двоїстості) можна використовувати прийоми, які базуються на неоднозначності постановок задач. Найбільш загальний з цих прийомів – розширення початкової квадратичної постановки задачі шляхом введення в неї так званих функціонально надлишкових обмежень (додаткові обмеження, які є наслідками вже існуючих обмежень задачі). Способи побудови таких обмежень можуть носити як загальний характер, так і використовувати специфіку конкретної задачі.
Мета статті. Показати шляхи покращення лагранжевих двоїстих оцінок для квадратичних екстремальних задач за рахунок використання функціонально надлишкових обмежень; навести приклади побудови таких обмежень.
Результати. Розглянуто загальну концепцію використання функціонально надлишкових обмежень для покращення лагранжевих двоїстих оцінок для квадратичних екстремальних задач. Наведено ряд способів побудови таких обмежень. Зокрема, в узагальненому і схематизованому вигляді представлено підхід до побудови функціонально надлишкових обмежень для квадратичних задач загального вигляду, що був запропонований Н.З. Шором. Також відзначається можливість використання й інших специфічних прийомів побудови функціонально надлишкових обмежень, які використовують особливості конкретних задач.
Висновки. Для покращення двоїстих оцінок для квадратичних екстремальних задач можна використовувати різні сімейства функціонально надлишкових обмежень, як загального так і специфічного типу. Їх застосування в ряді випадків може привести до уточнення оцінок або, навіть, надати можливість отримати точні значення глобальних екстремумів.
Ключові слова: квадратична екстремальна задача, лагранжева релаксація, двоїста оцінка, функціонально надлишкові обмеження.
Цитувати так: Березовський О.А. Покращення лагранжевих двоїстих оцінок для квадратичних екстремальних задач. Cybernetics and Computer Technologies. 2020. 1. С. 15–22. https://doi.org/10.34229/2707-451X.20.1.2
Список літератури
1. Шор Н. З., Стеценко С. И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. Киев: Наукова думка, 1989. 208 с.
2. Lemaréchal C. Lagrangian relaxation. Computational combinatorial optimization. 2001. P. 112–156.
3. Nesterov Y., Wolkowicz H., Ye Y. Semidefinite programming relaxations of nonconvex quadratic optimization. Handbook of semidefinite programming. New York: Springer US, 2000. P. 361–419.
4. Kim S., Kojima M. Second order cone programming relaxation of nonconvex quadratic optimization problems. Optimization methods and software. 2001. 15(3). P. 201–224.
5. Qualizza A., Belotti P., Margot F. Linear programming relaxations of quadratically constrained quadratic programs. Mixed Integer Nonlinear Programming. NY: Springer, 2012. P. 407–426.
6. Березовский О.А. О точности двойственных оценок для квадратичных экстремальных задач. Кибернетика и системный анализ. 2012. № 1. С. 33–39.
7. Березовский О.А. О решении одной специальной оптимизационной задачи, связанной с определением инвариантных множеств динамических систем. Проблемы управления и информатики. 2015. № 3. С. 33–40.
8. Стецюк П.И. О функционально избыточных ограничениях для булевых оптимизационных задач квадратичного типа. Кибернетика и системный анализ. 2005. № 6. C. 168–172.
9. Sherali H.D., Adams W.P. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Dordrecht: Kluwer, 1998. 516 p.
10. Yajima Y., Fujie T. A polyhedral approach for nonconvex quadratic programming problems with box constraints. Journal of Global Optimization. 1998. 13. P. 151–170.
11. Стецюк П.И. Новые модели квадратичного типа для задачи о максимальном взвешенном разрезе графа. Кибернетика и системный анализ. 2006. № 1. C. 63–75.
12. Березовский О.А. О нижней оценке для одной квадратичной задачи на многообразии Штифеля. Кибернетика и системный анализ. 2008. № 5. С. 95–103.
13. Fujit T., Kojima M. Semidefinite programming relaxation for nonconvex quadratic problems. Journal of Global Optimization. 1997. 10. P. 367–380.
14. Березовский О.А. Критерии точности SDP-релаксаций квадратичных экстремальных задач. Кибернетика и системный анализ. 2016. № 6. С. 95–101.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | Повний текст | Наступна