arrow
Volume 16, Issue 2
Finding Symmetry Groups of Some Quadratic Programming Problems

Anton V. Eremeev & Alexander S. Yurkov

Numer. Math. Theor. Meth. Appl., 16 (2023), pp. 370-392.

Published online: 2023-04

Export citation
  • Abstract

Solution and analysis of mathematical programming problems may be simplified when these problems are symmetric under appropriate linear transformations. In particular, a knowledge of the symmetries may help decrease the problem dimension, reduce the size of the search space by means of linear cuts. While the previous studies of symmetries in the mathematical programming usually dealt with permutations of coordinates of the solutions space, the present paper considers a larger group of invertible linear transformations. We study a special case of the quadratic programming problem, where the objective function and constraints are given by quadratic forms. We formulate conditions, which allow us to transform the original problem to a new system of coordinates, such that the symmetries may be sought only among orthogonal transformations. In particular, these conditions are satisfied if the sum of all matrices of quadratic forms, involved in the constraints, is a positive definite matrix. We describe the structure and some useful properties of the group of symmetries of the problem. Besides that, the methods of detection of such symmetries are outlined for different special cases as well as for the general case.

  • AMS Subject Headings

15A04, 22E70, 22F50, 90C20

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-16-370, author = {Eremeev , Anton V. and Yurkov , Alexander S.}, title = {Finding Symmetry Groups of Some Quadratic Programming Problems}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2023}, volume = {16}, number = {2}, pages = {370--392}, abstract = {

Solution and analysis of mathematical programming problems may be simplified when these problems are symmetric under appropriate linear transformations. In particular, a knowledge of the symmetries may help decrease the problem dimension, reduce the size of the search space by means of linear cuts. While the previous studies of symmetries in the mathematical programming usually dealt with permutations of coordinates of the solutions space, the present paper considers a larger group of invertible linear transformations. We study a special case of the quadratic programming problem, where the objective function and constraints are given by quadratic forms. We formulate conditions, which allow us to transform the original problem to a new system of coordinates, such that the symmetries may be sought only among orthogonal transformations. In particular, these conditions are satisfied if the sum of all matrices of quadratic forms, involved in the constraints, is a positive definite matrix. We describe the structure and some useful properties of the group of symmetries of the problem. Besides that, the methods of detection of such symmetries are outlined for different special cases as well as for the general case.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.OA-2022-0092}, url = {http://global-sci.org/intro/article_detail/nmtma/21581.html} }
TY - JOUR T1 - Finding Symmetry Groups of Some Quadratic Programming Problems AU - Eremeev , Anton V. AU - Yurkov , Alexander S. JO - Numerical Mathematics: Theory, Methods and Applications VL - 2 SP - 370 EP - 392 PY - 2023 DA - 2023/04 SN - 16 DO - http://doi.org/10.4208/nmtma.OA-2022-0092 UR - https://global-sci.org/intro/article_detail/nmtma/21581.html KW - Non-convex programming, orthogonal transformation, symmetry group, Lie group. AB -

Solution and analysis of mathematical programming problems may be simplified when these problems are symmetric under appropriate linear transformations. In particular, a knowledge of the symmetries may help decrease the problem dimension, reduce the size of the search space by means of linear cuts. While the previous studies of symmetries in the mathematical programming usually dealt with permutations of coordinates of the solutions space, the present paper considers a larger group of invertible linear transformations. We study a special case of the quadratic programming problem, where the objective function and constraints are given by quadratic forms. We formulate conditions, which allow us to transform the original problem to a new system of coordinates, such that the symmetries may be sought only among orthogonal transformations. In particular, these conditions are satisfied if the sum of all matrices of quadratic forms, involved in the constraints, is a positive definite matrix. We describe the structure and some useful properties of the group of symmetries of the problem. Besides that, the methods of detection of such symmetries are outlined for different special cases as well as for the general case.

Eremeev , Anton V. and Yurkov , Alexander S.. (2023). Finding Symmetry Groups of Some Quadratic Programming Problems. Numerical Mathematics: Theory, Methods and Applications. 16 (2). 370-392. doi:10.4208/nmtma.OA-2022-0092
Copy to clipboard
The citation has been copied to your clipboard