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.