Algorithmization and Software Implementation of the Method of Eliminating Variables in Polynomial Optimization Problems

96

Abstract

The method of sequential exclusion of variables in polynomial optimization problems is considered. A number of problems are solved using this method. The practical steps of an algorithm are described, which reduces the initial polynomial optimization problem to a multi-stage branching process of obtaining a finite number of alternative problems, the output of which gives a finite set of polynomials in one variable. As a result, solving a number of polynomial problems reduces to sorting out a finite number of vectors whose components are the real roots of polynomials.

General Information

Keywords: polynomials, exclusion of variables, optimization problems, systems of algebraic equations

Journal rubric: Optimization Methods

Article type: scientific article

DOI: https://doi.org/10.17759/mda.2020100107

For citation: Nefedov V.N., Zharkikh A.V. Algorithmization and Software Implementation of the Method of Eliminating Variables in Polynomial Optimization Problems. Modelirovanie i analiz dannikh = Modelling and Data Analysis, 2020. Vol. 10, no. 1, pp. 110–128. DOI: 10.17759/mda.2020100107. (In Russ., аbstr. in Engl.)

References

  1. Nefedov V.N. Metod isklyucheniya peremennykh v polinomial’nykh zadachakh optimizatsii – Dep. v VINITI, 1984, № 7590–84.
  2. Nefedov V.N. Polinomial’nyye zadachi optimizatsii. ZH. vychisl. matem. i matem. fi z. 1987. T. 27. № 5. pp. 661–675.
  3. Gubar’ YU.V. Vvedeniye v matematicheskoye programmirovaniye. – INTUIT (natsional’nyy otkrytyy universitet), 2016. – 227 p.
  4. Verzhbitskiy V.M. Osnovy chislennykh metodov. – Moscow: Vysshaya shkola, 2002. – 840 p.
  5. Kanovey G.V., Logofet D.O. D-Ustoychivost’ matrits 4×4. ZH. vychisl. matem. i matem. fi z. 1998. T. 38. № 9. p. 1429–1435.
  6. Logofet D.O. Stronger-than-Lyapunov notions of matrix stability, or how “fl owers” help solve problems in mathematical ecology. Linear Algebra Appl, 398 (2005), pp. 75–100.
  7. Nefedov V.N. Ob odnom dostatochnom uslovii ekstremuma dlya polinomov i stepennykh ryadov – Dep. v VINITI, 1990, № 2666-V90.
  8. Bukhberger B. Algoritmicheskiy metod v teorii polinomial’nykh idealov. Komp’yuternaya algebra. Simvol’nyye i algebraicheskiye vychisleniya. – Moscow: Mir, 1986.
  9. Arzhantsev I.V. Bazisy Grebnera i sistemy algebraicheskikh uravneniy. – Moscow: MTSNMO, 2003. – 68 p.

Information About the Authors

Viktor N. Nefedov, PhD in Physics and Matematics, Associate Professor, Department of Mathematical Cybernetics, Moscow Aviation Institute (MAI), Moscow, Russia, e-mail: nefedovvn54@yandex.ru

Aleksey V. Zharkikh, Master’s Degree Student at the Faculty of Information Technology and Applied Mathematics, Moscow Aviation Institute (MAI), Moscow, Russia, e-mail: alexvzhar@gmail.com

Metrics

Views

Total: 285
Previous month: 8
Current month: 1

Downloads

Total: 96
Previous month: 5
Current month: 2