Finding Symmetry Groups of Some Quadratic Programming Problems

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.