Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Том 57 >>> № 1 СІЧЕНЬ — ЛЮТИЙ 2021
-->

УДК 519.8
О.А. Березовський

ТОЧНІ ДВОЇСТІ ОЦІНКИ ДЛЯ ДЕЯКИХ
НЕОПУКЛИХ МІНІМАКСНИХ КВАДРАТИЧНИХ
ОПТИМІЗАЦІЙНИХ ЗАДАЧ

Анотація. Досліджено неопуклу сепарабельну мінімаксну квадратичну оптимізаційну задачу. Наведено два підходи до її розв’язання: за допомогою SOCP-релаксації і лагранжевої релаксації квадратичної екстремальної за-дачі-аналога. Отримано умову, виконання якої гарантує знаходження значення і точки глобального екстремуму задачі розглянутого класу обчисленням двої-стої оцінки еквівалентної квадратичної екстремальної задачі.

Ключові слова: мінімаксна квадратична оптимізаційна задача, SOCP-релак-сація, лагранжева релаксація, точна двоїста оцінка, додатно-визначена матриця.



ПОВНИЙ ТЕКСТ

Березовский Олег Анатольевич,
кандидат физ.-мат. наук, старший научный сотрудник Института кибернетики имени В.М. Глушкова НАН Украины, Киев,  o.a.berezovskyi@gmail.com


СПИСОК ЛІТЕРАТУРИ

  1. Shor N.Z. Nondifferentiable optimization and polynomial problems. Boston; London; Dordrecht: Kluwer Academic Publishers, 1998. 394 p.

  2. Pardalos P.M., Rosen J.B. Constrained global optimization: Algorithms and applications. In: Lecture Notes in Computer Science. Vol. 268. Berlin; Heidelberg: Springer-Verlag, 1987. 122 p.

  3. Momoh J.A. Electric power system applications of optimization. New York: CRC Press, 2017. 595 p.

  4. Arora J.S. Optimization of structural and mechanical systems. Singapore: World Scientific, 2007. 595 p.

  5. Шор Н.З., Сергієнко І.В., Шило В.П., Стецюк П.І., Парасюк І.М., Лебєдєва Т.Т., Лаптін Ю.П., Журбенко М.Г., Бардадим Т.О., Шаріфов Ф.А., Лиховид О.П., Березовський О.А., Мірошниченко В.М. Задачі оптимального проектування надійних мереж. К.: Наук. думка, 2005. 230 с.

  6. Стецюк П.И., Бортис Г., Эмменеггер Ж.-Ф., Кошлай Л.Б., Березовский О.А., Бардадым Т.А., Первухина Е.Л., Голикова В.В., Осипов К.Н., Карпец Э.П., Пилиповский А.В. Институциональные и технологические изменения в странах с рыночной и переходной экономикой. К.: Видавничий дім «Києво-Могилянська академія», 2015. 336 c.

  7. Guisewite G.M. Network problems. Handbook of Global Optimization. Nonconvex Optimization and Its Applications. Horst R., Pardalos P.M. (Eds.). Vol 2. Boston, MA: Springer, 1995. P. 609–648.

  8. Zhuravlev Yu.I., Laptin Yu.P., Vinogradov A.P., Zhurbenko N.G., Lykhovyd O.P., Berezovskyi O.A. Linear classifiers and selection of informative features. Pattern Recognition and Image Analysis. 2017. Vol. 27, Iss. 3. P. 426–432.

  9. Мунтіян В.І., Прокопенко О.В., Петрушенко М.М., Авескулова Л.І., Адасовський Б.І. Економічна безпека держави: стратегія, енергетика, інформаційні технології. За ред. Лук’яненко С.О., Караєвої Н.В. К.: Вид-во ООО «Юрка Любченка», 2014. 468 с.

  10. Pankov A.R., Platonov E.N., Semenikhin K.V. Minimax quadratic optimization and its application to investment planning. Automation and Remote Control. 2001. Vol. 62, Iss. 12. P. 1978–1995.

  11. Shor N.Z., Berezovskii O.A. Using the method of dual quadratic solutions to solve systems of polynomial equations in the complex domain. Cybernetics and Systems Analysis. 1994. Vol. 30, N 5. P. 686–692.

  12. 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.

  13. Kim S., Kojima M. Second order cone programming relaxation of nonconvex quadratic optimization problems. Optimization Methods and Software. 2001. Vol. 15, Iss. 3. P. 201–224.

  14. LemarБchal C. Lagrangian relaxation. Computational Combinatorial Optimization. Lecture Notes in Computer Science. Jnger M., Naddef D. (Eds.). Vol. 2241. Berlin; Heidelberg: Springer, 2001. P. 112–156. https://doi.org/10.1007/3-540-45586-8_4.

  15. Anstreicher K., Wolkowicz H. On Lagrangian relaxation of quadratic matrix constraints. SIAM Journal on Matrix Analysis and Applications. 2000. Vol. 2, Iss. 1. P. 41–55.

  16. Qualizza A., Belotti P., Margot F. Linear programming relaxations of quadratically constrained quadratic programs. Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications. Lee J., Leyffer S. (Eds.). Vol 154. New York: Springer, 2012. P. 407–426. https://doi.org/10.1007/978-1-4614-1927-3_14.

  17. Jeyakumar V., Li G. Exact second-order cone programming relaxations for some nonconvex minimax quadratic optimization problems. SIAM Journal on Optimization. 2018. Vol. 28, Iss. 1. P. 760–787.

  18. Wolkowicz H., Saigal R., Vandenberghe L. (Eds.). Handbook of semidefinite programming: theory, algorithms, and applications. New York: Springer Science & Business Media, 2012. 654 p.

  19. Lasserre J.B. An explicit exact SDP relaxation for nonlinear 0-1 programs. Intern. Conf. on Integer Programming and Combinatorial Optimization. Berlin: Springer, 2001. P. 293–303.

  20. Burer S., Anstreicher K.M. Second-order-cone constraints for extended trust-region subproblems. SIAM Journal on Optimization. 2013. Vol. 23, Iss. 1. P. 432–451.

  21. Beck A., Eldar Y.C. Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM Journal on Optimization. 2006. Vol. 17, Iss. 3. P. 844–860.

  22. Березовский О.А. О точности двойственных оценок для квадратичных экстремальных задач. Кибернетика и системный анализ. 2012. № 1. С. 33–39.

  23. Jeyakumar V., Li G. Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization. Mathematical Programming. 2014. Vol. 147, Iss. 1. P. 171–206.

  24. Jeyakumar V., Li G. Y. Strong duality in robust convex programming: complete characterizations. SIAM Journal on Optimization. 2010. Vol. 20, Iss. 6. P. 3384–3407.

  25. Berezovskyi O.A. On solving of a special optimization problem connected with determination of invariant sets of dynamical systems. Journal of Automation and Information Sciences. 2015. Vol. 47, Iss. 5. P. 69–77.

  26. Haines S., Loeppky J., Tseng P., Wang X. Convex relaxations of the weighted maxmin dispersion problem. SIAM Journal on Optimization. 2013. Vol. 23, Iss. 4. P. 2264–2294.

  27. Ben-Tal A., Ghaoui L.E., Nemirovski A. Robust optimization. Princeton Ser. Appl. Math. Princeton: Princeton Univ. Press, 2009. 544 р.

  28. Alizadeh F. Optimization over the positive-definite cone: Interior point methods and combinatorial applications. In: Advances in Optimization and Parallel Computing. Pardalos P.M. (Ed.). Amsterdam: Elsevier Science, 1992. P. 1–25.

  29. Fujit T., Kojima M. Semidefinite programming relaxation for nonconvex quadratic problems. Journal of Global Optimization. 1997. Vol. 10, Iss. 4. P. 367–380.

  30. Березовский О.А. Критерии точности SDP-релаксаций квадратичных экстремальных задач. Кибернетика и системный анализ. 2016. Т. 52, № 6. С. 95–101.




Інформація редакції Аннотації статей Автори Архів
Журнал Тематичні Розділи Редакція Редакційна колегія Приклади документів Передплата Контакти
© 2021 Kibernetika.org. All rights reserved.