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
REFERENCES
1. Lemarechal C. Cauchy and the gradient method. Documenta Math., 21st Int. Symp. Math. Program., Berlin, 2012, Extra Vol. Optimization Stories, pp. 251–254.
2. Deuflhard P. A short history of Newton’s method. Documenta Math. 21st Int. Symp. Math. Program., Berlin, 2012, Extra Vol. Optimization Stories, pp. 25–30.
3. Pang J.-S. Three modeling paradigms in mathematical programming. Math. Program., Ser. B, 2010, vol. 125, no. 2, pp. 297–323. doi: 10.1007/s10107-010-0395-1
4. Vasil’ev F.P. Metody optimizatsii [Optimization methods]. Moscow, MCNMO, 2011, 620 p. ISBN 978-5-94057-706-5 .
5. Bahvalov N.S., Zhidkov N.P., Kobelkov G.M. Chislennyye metody [Numerical Methods]. Moscow, Binom Publ., 2013, 640 p.
6. Tyrtyshnikov E.E. Metody chislennogo analiza [Methods of numerical analysis]. Moscow, Academia Publ., 2007, 317 p. ISBN: 978-5-7695-3925-1 .
7. Samarskii A.A., Gulin A.V. Chislennyye metody [Numerical Methods]. Moscow, Nauka Publ., 1989, 429 p. ISBN: 5-02-013996-3 .
8. Ortega J.M., Rheinboldt W.C. Iterative solution of nonlinear equations in several variables. NY, Acad. Press, 1970, 572 p. Translated to Russian under the title Iteratsionnyye metody resheniya nelineynykh sistem uravneniy, Moscow, Mir Publ., 1975, 559 p.
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, pp. 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. Comput., 2019, vol. 31, no. 2, pp. 235–250.
11. Kantorovich L.V., Akilov G.P. Functional Analysis. NY, Pergamon Press, 1982, 604 p. doi: 10.1016/C2013-0-03044-7 . Original Russian text published in Kantorovich L.V., Akilov G.P. Funktsional’nyi analiz, Moscow, Nauka Publ., 1977, 744 p.
12. Nocedal J., Wright St.J. Numerical optimization. NY, Springer, 2006, 664 p. doi: 10.1007/978-0-387-40065-5
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, pp. 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, pp. 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, pp. 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. Strekalovskii A.S. Elementy nevypukloi optimizatsii [Elements of nonconvex optimization]. Novosibirsk, Nauka Publ., 2003, 356 p. ISBN: 5-02-032064-1 .
19. Strekalovsky A.S. New global optimality conditions in a problem with d.c. constraints. Tr. Instituta Matematiki i Mekhaniki UrO RAN, 2019, vol. 25, no. 1, pp. 245–261 (in Russian). doi: 10.21538/0134-4889-2019-25-1-245-261
20. Strekalovsky A.S., Bagirov A.M. et al. Local search for nonsmooth DC optimization with DC equality and inequality constraints. In: 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., Rassias T.M. et al. On solving optimization problems with Hidden nonconvex structures. In: Optimization in Science and Engineering. NY, Springer, 2014, pp. 465–502. doi: 10.1007/978-1-4939-0808-0_23
22. Strekalovsky A.S. Minimizing sequences in a constrained DC optimization problem. Proc. Steklov Inst. Math. (Suppl.), 2023, vol. 323, suppl. 1, pp. S255–S278. doi: 10.1134/S0081543823060214
23. Strekalovsky A.S., Minarchenko I.M. A local search method for optimization problem with d.c. inequality constraints. Appl. Math. Model., 2018, vol. 58, pp. 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. Optimiz. Appl., 2004, vol. 28, no. 1, pp. 31–50.
25. Hiriart-Urruty J.-B., Lemaréchal C. Convex analysis and minimization algorithms. I, 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. ISBN: 9789916031643 .
27. Supplementary Materials for the article Strekalovsky A.S., Barkova M.V. “On the solution of systems of quadratic equations”. The online version contains supplementary material available at http://journal.imm.uran.ru/Suppl_inf_2024-_v.30-_2 (PDF) .
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.
