On the solution of systems of quadratic equations

A. S. Strekalovskii ; M. V. Barkova

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 30 (2024) no. 2, pp. 173-187

Résumé

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.

Détail

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

Bibliographie

[25] Lemarechal C., “Cauchy and the gradient method”, Optimization Stories, 21st Int. Symp. Math. Program., Extra Vol. (Berlin, August 19–24), Documenta Math., 2012, 251–254 | MR | Zbl

[26] Deuflhard P., “A short history of newton's method”, Optimization Stories, 21st Int. Symp. Math. Program., Extra Vol. (Berlin, August 19–24), Documenta Math., 2012, 25–30 | MR | Zbl

[27] Pang J.-S., “Three modeling paradigms in mathematical programming”, Math. Program., 124:2 (2010), 297–323 | DOI | MR

[28] Vasilev F.P., Metody optimizatsii, MTsNMO, M., 2011, 620 pp.

[29] Bakhvalov N.S., N.P.Zhidkov, G.M.Kobelkov, Chislennye metody, Binom, M., 2013, 640 pp. | MR

[30] Tyrtyshnikov E.E., Metody chislennogo analiza, Akademiya, M., 2007, 320 pp.

[31] Samarskii A.A., Gulin A.V., Chislennye metody, Nauka, M., 1989, 432 pp.

[32] Ortega Dzh., Reinbold V., Iteratsionnye metody resheniya nelineinykh sistem uravnenii, Mir, M., 1975, 559 pp.

[33] Floudas C., Klepeis J., Pardalos P., “Global optimization approaches in protein folding and peptide docking”, DIMACS Ser. in Discrete Math. and Theoret. Comp. Sci, 47, 1999, 141–171 | DOI | MR | Zbl

[34] 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., 31:2 (2019), 235–250 | DOI | MR

[35] Kantorovich L.V., Akilov G.P., Funktsionalnyi analiz, Izdanie 2-e, pererab., Nauka, M., 1977, 744 pp. | MR

[36] Nocedal J., Wright St.J., Numerical optimization, Springer, NY, 2006, 664 pp. | MR | Zbl

[37] Byrd R.H., Marazzi M., Nocedal J., “On the convergence of Newton iterations to non-stationary points”, Math. Program., Ser. A, 99:1 (2004), 127–148 | DOI | MR | Zbl

[38] Mascarenhas W. F., “The BFGS method with exact line searches fails for non-convex objective functions”, Math. Program., Ser. A, 99:1 (2004), 49–61 | DOI | MR | Zbl

[39] Wachter A., Biegler L.T., “Failure of global convergence for a class of interior point methods for nonlinear programming”, Math. Program., Ser. B, 88:3 (2000), 565–574 | DOI | MR | Zbl

[40] Floudas C.A., Pardalos P.M. et al., Handbook of test problems in local and global optimization, Springer Science and Business Media Dordrecht, NY, 1999, 442 pp. | DOI

[41] Horst R., Tuy H., Global optimization: Deterministic approaches, Springer-Verlag, Berlin, 1996, 730 pp. | DOI | MR | Zbl

[42] Strekalovskii A.S., Elementy nevypukloi optimizatsii, Nauka, Novosibirsk, 2003, 356 pp.

[43] Strekalovskii A.S., “Novye usloviya globalnoi optimalnostiv zadache s d.c. ogranicheniyami”, Tr. In-ta matematiki i mekhaniki UrO RAN, 25:1 (2019), 245–261 | DOI | MR

[44] 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., Springer Internat. Publ., Cham, 2020, 229–261 | DOI | MR

[45] 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, Springer, NY, 2014, 465–502 | DOI | MR | Zbl

[46] Strekalovskii A.S., “Minimiziruyuschie posledovatelnosti v zadache DC optimizatsii s ogranicheniyami”, Tr. In-ta matematiki i mekhaniki UrO RAN, 29:3 (2023), 185–209 | DOI

[47] Strekalovsky A.S., Minarchenko I.M., “A local search method for optimization problem with d.c. inequality constraints”, Appl. Math. Modelling, 58 (2018), 229–244 | DOI | MR | Zbl

[48] Bellavia S., Macconi M., Morini B., “STRSCNE: A scaled trust region solver for constrained nonlinear equations”, Comput. Optim. Appl., 28:1 (2004), 31–50 | DOI | MR | Zbl

[49] Hiriart-Urruty J.-B., Lemarechal C., Convex analysis and minimization algorithms, Springer-Verlag, Berlin, 1993, 418 pp. | DOI | MR

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

[51] Dopolnitelnye materialy k state: Strekalovskii A.S., Barkova M.V. “O reshenii sistem kvadratichnykh uravnenii”, Onlain-versiya soderzhit dopolnitelnye materialy (PDF), razmeschennye na URL: http://journal.imm.uran.ru/sites/default/files/content/30_2/Suppl_inf_2024-v.30-2_experiment.pdf