А.С. Стрекаловский, М.В. Баркова. О решении систем квадратичных уравнений ... С. 173-187

УДК 519.853.4

MSC: 90C26, 90C30

DOI: 10.21538/0134-4889-2024-30-2-173-187

Онлайн-версия статьи содержит дополнительные материалы

Работа выполнена в рамках базового проекта фундаментальных исследований Минобрнауки РФ (№ 121041300065-9, код FWEW-2021-0003).

В работе рассматривается классическая проблема решения системы квадратичных алгебраических уравнений. Для поиска решения применяется вариационный подход сведения к задаче оптимизации с функциями, представимыми разностью выпуклых функций (DC функций). Задача оптимизации при этом оказывается невыпуклой и негладкой. Используя известные свойства DC функций, удается свести основную задачу оптимизации к гладкой задаче DC минимизации с ограничениями-неравенствами. Для решения последней вначале применяется специальный метод локального поиска (СМЛП), для которого исследована сходимость и обоснованы критерии останова. Тестирование СМЛП на системах с квадратичными данными продемонстрировало достаточную эффективность СМЛП, в том числе по сравнению с известными специальными пакетами прикладных программ (ППП). Процедуры глобального поиска строятся на основе условий глобальной оптимальности (УГО), позволяющих “выскакивать” из локальных решений, стационарных и критических точек. Далее произведено успешное тестирование метода глобального поиска (МГП). При этом сравнительная эффективность разработанного подхода доказана успешным решением всех тестовых систем квадратичных уравнений для задач большой размерности (с количеством уравнений и переменных до 1000). В то же время стандартные ППП на задачах большой размерности продемонстрировали свою неспособность отыскать решение в большинстве тестовых примеров.

Ключевые слова: системы квадратичных уравнений, DC функции, условия глобальной оптимальности, локальный поиск, глобальный поиск, квадратичные задачи

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

1.   Lemarechal C. Cauchy and the gradient method // Documenta Math. 21st Int. Symp. Math. Program. Berlin, August 19–24. 2012. Extra Vol. Optimization Stories. P. 251–254.

2.   Deuflhard P. A short history of newton’s method // Documenta Math. 21st Int. Symp. Math. Program. Berlin, August 19–24. 2012. Extra Vol. Optimization Stories. P. 25–30.

3.   Pang J.-S. Three modeling paradigms in mathematical programming // Math. Program. 2010. Vol. 124, no. 2. P. 297–323.

4.   Васильев Ф.П. Методы оптимизации. М.: МЦНМО, 2011. 620 c.

5.   Бахвалов Н.С., Н.П.Жидков, Г.М.Кобельков Численные методы. М.:Бином, 2013. 640 c.

6.   Тыртышников Е.Е. Методы численного анализа. М.: Академия, 2007. 320 c.

7.   Самарский А.А., Гулин А.В. Численные методы. М.: Наука, 1989. 432 c.

8.   Ортега Дж., Рейнбольд В. Итерационные методы решения нелинейных систем уравнений. М.: Мир, 1975. 559 c.

9.   Floudas C., Klepeis J., Pardalos P. Global optimization approaches in protein folding and peptide docking // DIMACS Ser. in Discrete Math. and Theoret. Comp. Sci. 1999. Vol. 47. P. 141–171.

10.   Pei J., Drazic Z., Drazic M., Mladenovic N., Pardalos P. Continuous variable neighborhood search (C-VNS) for solving systems of nonlinear equations // INFORMS J. Comp. 2019. Vol. 31, no. 2. P. 235–250.

11.   Канторович Л.В., Акилов Г.П. Функциональный анализ. М.: Наука; Издание 2-е, перераб., 1977. 744 c.

12.   Nocedal J., Wright St.J. Numerical optimization. NY: Springer, 2006. 664 p.

13.   Byrd R.H., Marazzi M., Nocedal J. On the convergence of Newton iterations to non-stationary points // Math. Program., Ser. A. 2004. Vol. 99, no. 1. P. 127–148. doi: 10.1007/s10107-003-0376-8

14.   Mascarenhas W. F. The BFGS method with exact line searches fails for non-convex objective functions// Math. Program., Ser. A. 2004. Vol. 99, no. 1. P. 49–61. doi: 10.1007/s10107-003-0421-7

15.   Wachter A., Biegler L.T. Failure of global convergence for a class of interior point methods for nonlinear programming // Math. Program., Ser. B. 2000. Vol. 88, no. 3. P. 565–574. doi: 10.1007/PL00011386

16.   Floudas C.A., Pardalos P.M. et al. Handbook of test problems in local and global optimization. NY: Springer Science and Business Media Dordrecht, 1999. 442 p. doi: 10.1007/978-1-4757-3040-1

17.   Horst R., Tuy H. Global optimization: Deterministic approaches. Berlin: Springer-Verlag, 1996. 730 p. doi: 10.1007/978-3-662-03199-5

18.   Стрекаловский А.С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003. 356 c.

19.   Стрекаловский А.С. Новые условия глобальной оптимальностив задаче с d.c. ограничениями // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 1. C. 245–261. doi: 10.21538/0134-4889-2019-25-1-245-261

20.   Strekalovsky A.S. Local search for nonsmooth DC optimization with DC equality and inequality constraints // Constraints Numerical Nonsmooth Optimization: State of the Art Algorithms / eds. A. M. Bagirov, M. Gaudioso, N. Karmitsa et al. Cham: Springer Internat. Publ., 2020. P. 229–261. doi: 10.1007/978-3-030-34910-3_7

21.   Strekalovsky A.S. On solving optimization problems with hidden nonconvex structures // Optimization in Science and Engineering / eds. T.M. Rassias, C.A. Floudas, S. Butenko. NY: Springer, 2014. P. 465–502. doi: 10.1007/978-1-4939-0808-0_23

22.   Стрекаловский А.С. Минимизирующие последовательности в задаче DC оптимизации с ограничениями // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. C. 185–209. doi: 10.21538/0134-4889-2023-29-3-185-209

23.   Strekalovsky A.S., Minarchenko I.M. A local search method for optimization problem with d.c. inequality constraints // Appl. Math. Modelling. 2018. Vol. 58. P. 229–244. doi: 10.1016/j.apm.2017.07.031

24.   Bellavia S., Macconi M., Morini B. STRSCNE: A scaled trust region solver for constrained nonlinear equations // Comput. Optim. Appl. 2004. Vol. 28, no. 1. P. 31–50.

25.   Hiriart-Urruty J.-B., Lemarechal C. Convex analysis and minimization algorithms. Berlin: Springer-Verlag, 1993. 418 p. doi: 10.1007/978-3-662-02796-7

26.   Roose A., Kulla V., Lomp M., Meressoo T. Test examples of systems of non-linear equations. Tallin: Estonian Software and Computer Service Company, 1990.

27.   Дополнительные материалы к статье: Стрекаловский А.С., Баркова М.В. “О решении систем квадратичных уравнений”. Онлайн-версия содержит дополнительные материалы, размещенные на http://journal.imm.uran.ru/Suppl_inf_2024-v.30-2 (PDF) .

Поступила 2.10.2023

После доработки 13.03.2024

Принята к публикации 18.03.2024

Стрекаловский Александр Сергеевич
д-р физ.-мат. наук, профессор
зав. отделом
Институт динамики систем и теории управления имени В.М. Матросова СО РАН
г. Иркутск
e-mail: strek@icc.ru

Баркова Мария Владимировна
младший науч. сотрудник
Институт динамики систем и теории управления имени В.М. Матросова СО РАН
г. Иркутск
e-mail: mbarkova@icc.ru

Ссылка на статью: А.С. Стрекаловский, М.В. Баркова. О решении систем квадратичных уравнений // Тр. Ин-та математики и механики УрО РАН. 2024. Т. 30, № 2. С. 173-187

English

A.S. Strekalovsky, M.V. Barkova. On the solution of systems of quadratic equations

The paper addresses the classical problem of solving a system of quadratic algebraic equations. To find a solution, we apply a variational approach of reducing the original problem to an optimization problem with cost functions represented by the difference of convex functions (DC functions). In this case, the optimization problem turns out to be nonconvex and nonsmooth. Using the known properties of DC functions, we reduce the main optimization problem to a smooth DC minimization problem with inequality constraints. To solve the latter problem, first, a special local search method (SLSM) is applied. The convergence of the method is proved and stopping criteria are established. The testing of the SLSM on systems of equations with quadratic data shows its sufficient efficiency, even when compared with known special applied software packages. Global search procedures are built on the basis of global optimality conditions, which allow us to “jump out” of local solutions and stationary and critical points. The global search method is tested. The comparative efficiency of the developed approach is proved by the successful solution of all test systems of quadratic equations for problems of large dimension (with the number of equations and variables up to 1000). At the same time, the standard applied software packages fail to solve large-dimensional problems for the most part of test examples.

Keywords: system of quadratic equations, DC functions, global optimality conditions, local search, global search, quadratic problems

Received October 2, 2023

Revised March 13, 2024

Accepted March 18, 2024

Funding Agency: The research was carried out within a basic project for fundamental research of the Ministry of Science and Higher Education of the Russian Federation (no. 121041300065-9, code FWEW-2021-0003).

Alexander Sergeevich Strekalovsky, Dr. Phys.-Math. Sci., Prof., Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: strek@icc.ru

Maria Vladimirovna Barkova, Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: mbarkova@icc.ru

Cite this article as: A.S. Strekalovsky, M.V. Barkova. On the solution of systems of quadratic equations. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2024, vol. 30, no. 2, pp. 173–187.

[References -> on the "English" button bottom right]