Finding symmetry groups of some quadratic programming problems. (English) Zbl 07814760
Summary: 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.
MSC:
| 15A04 | Linear transformations, semilinear transformations |
| 22E70 | Applications of Lie groups to the sciences; explicit representations |
| 22F50 | Groups as automorphisms of other structures |
| 90C20 | Quadratic programming |
References:
| [1] | R. BÖDI, K. HERR, AND M. JOSWIG, Algorithms for highly symmetric linear and integer programs, Math. Program. 137 (2013), 65-90. · Zbl 1262.90101 |
| [2] | N. BOURBAKI, Groupes et Algèbres de Lie, Masson, 1982. · Zbl 0505.22006 |
| [3] | P. BURGISSER, C. FRANKS, A. GARG, R. OLIVEIRA, M. WALTER, AND A. WIGDERSON, Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes, In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), (2019), 845-861. |
| [4] | O. CHERVYAKOV, Affine symmetries of the polyhedron of independence system with uhit shift, Discretnyi Analiz i Issledovanie Operacii 2(2) (1999), 82-96. (in Russian) · Zbl 0938.94018 |
| [5] | A. COSTA, P. HANSEN, AND L. LIBERTI, On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square, Discret. Appl. Math. 161(1) (2013), 96-106. · Zbl 1262.90143 |
| [6] | B. DOERR, Runtime analysis of evolutionary algorithms via symmetry arguments, Inf. Pro-cess. Lett. 166 (2021), 106064. · Zbl 1506.68189 |
| [7] | A. V. EREMEEV, N. N. TYUNIN, AND A. S. YURKOV, Non-Convex Quadratic Programming Problems in Short Wave Antenna Array Optimization, In: Mathematical Optimization The-ory and Operations Research, M. Khachay, Y. Kochetov, P. Pardalos (Eds.), Springer Inter-national Publishing, Cham. (2019), 34-45. · Zbl 1443.90266 |
| [8] | A. V. EREMEEV AND A. S. YURKOV, On Symmetry Groups of Some Quadratic Programming Problems, In: Mathematical Optimization Theory and Operations Research -19th Interna-tional Conference, MOTOR 2020, A.V. Kononov, M.Y. Khachay, V.A. Kalyagin, P.M. Parda-los (Eds.), Novosibirsk, Russia, July 6-10. Proceedings, Lecture Notes in Computer Sci-ence, Springer, 12095 (2020), 35-48. · Zbl 1464.90065 |
| [9] | J. GARNIER AND L. KALLEL, How to detect all maxima of a function, In: Theoretical Aspects of Evolutionary Computing. Natural Computing Series, L. Kallel, B. Naudts, A. Rogers (Eds), Springer, (2001), 343-370. · Zbl 1001.68194 |
| [10] | K. GATERMANN AND P. A. PARRILO, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra. 192(1) (2004), 95-128. · Zbl 1108.13021 |
| [11] | R. A. HORN AND C. R. JOHNSON, Matrix Analysis, Cambridge University Press, (1990). · Zbl 0704.15002 |
| [12] | A. KHAJAVIRAD AND N. V. SAHINIDIS, A hybrid LP/NLP paradigm for global optimization relaxations, Math. Program. Comput. 10 (2018), 383-421. · Zbl 1400.90227 |
| [13] | A. A. KOLOKOLOV, T. G. ORLOVSKAYA, AND M. F. RYBALKA, Analysis of integer program-ming algorithms with L-partition and unimodular transformations, Autom. Remote Con-trol. 73(2) (2012), 369-380. · Zbl 1307.90110 |
| [14] | G. KOUYIALIS, X. WANG, AND R. MISENER, Symmetry detection for quadratic optimization using binary layered graphs, Processes 7(11) (2019). |
| [15] | P. LANCASTER AND M. TISMENETSKY, The Theory of Matrices, Academic Press, (1985). · Zbl 0558.15001 |
| [16] | J. LEAKE AND N. K. VISHNOI, Optimization and sampling under continuous symmetry: Examples and Lie theory, arxiv abs/2109.01080, (2021). |
| [17] | L. LIBERTI, Reformulations in mathematical programming: Automatic symmetry detection and exploitation, Math. Program. 131 (2012). · Zbl 1235.90103 |
| [18] | F. MARGOT, Symmetry in Integer Linear Programming, In: 50 Years of Integer Program-ming 1958-2008, Springer, (2010), 647-686. · Zbl 1187.90200 |
| [19] | M. PFETSCH AND T. REHN, A computational comparison of symmetry handling methods for mixed integer programs, Math. Progr. Comput. 11 (2019), 37-93. · Zbl 1411.90233 |
| [20] | A. PRUGEL-BENNETT, Symmetry breaking in population-based optimization, Trans. Evol. Comp. 8(1) (2004), 63-79. |
| [21] | C. R. REEVES AND A. V. EREMEEV, Statistical analysis of local search landscapes, J. Oper. Res. Soc. 55(7) (2004), 687-693. · Zbl 1095.90098 |
| [22] | N. Z. SHOR, Semidefinite programming bounds for extremal graph problems, In: Nondif-ferentiable Optimization and Polynomial Problems, Springer, 24 (1998), 265-298. · Zbl 0901.49015 |
| [23] | R. SIMANCHEV, Linear symmetries of matchings polyhedron and graph automorphisms, Vestnik Omskogo Universiteta, 1 (1996), 18-20. (in Russian) · Zbl 0935.05074 |
| [24] | N. N. TYUNIN, On mutual influence of emitters in directivity optimization of shortwave phased antenna arrays, J. Phys. Conf. Ser. 1901(012053) (2021), 1-8. |
| [25] | N. N. TYUNIN, Problems of nonconvex quadratic programming related to the optimization of phased antenna arrays, J. Appl. Ind. Math. 15 (2021), 543-557. |
| [26] | D. P. ZHELOBENKO, Compact Lie Groups and Their Representations, Translations of math-ematical monographs, AMS, 40 (1973). · Zbl 0272.22006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
