On Constrained Optimization of Polynomials on Permutation Set 1[0000-0003-1707-843X] Sergiy Yakovlev and Oksana Pichugina2[0000-0002-7099-8967] 1 National Aerospace University “Kharkiv Aviation Institute”, Kharkiv, Ukraine svsyak7@gmail.com 2 National Aerospace University “Kharkiv Aviation Institute”, Kharkiv, Ukraine oksanapichugina1@gmail.com Abstract. Constrained polynomial optimization problem on permutation set is explored. For the problem, an equivalent formulation with a convex objective function and functional constraints is formed based on forming convex exten- sions of all functions involved in the model. New approaches to the construc- tion of convex extensions of polynomials from the permutation set are pro- posed. Original optimization methods using a polyhedral-spherical structure of the set are offered. Decomposition schemes underlying some global optimiza- tion techniques on permutations are described. Results of numerical experi- ments are presented. Keywords: Combinatorial Optimization, Constraints, Permutation Set, Poly- nomial, Convex Extension. 1 Introduction Various real-world problems can be modeled as optimization problems over the per- mutation set [1-5]. Among them are scheduling, assignment, routing problems and many others. They form a class of permutation-based problems (PBP) [6, 7]. Some of them allow embedding into Euclidean space and considering them as Euclidean com- binatorial sets. Permutation set and it's Boolean invariant - permutation matrices set - are well studied [8-10]. For instance, it is known H-representations of their convex hulls, main combinatorial characteristics, solutions of linear optimization and projec- tion problems, etc. However, real problems require fulfilling many conditions on permutations. In mathematical models, they are represented by additional constraints, typically spoiled the original combinatorial structure of permutation set and requiring developing specific technics for solving the corresponding optimization and feasibil- ity problems. From a theoretical point of view, permutation, as well as some of its subsets, are of interest. Among such subsets are even, odd, alternating, distance, cy- clic, circular, complete permutations, etc. [11-14]. It is a separate problem to construct additional constraints to single out any of the specific subsets. When it is solved, we come to a constrained PBP again. The paper is dedicated to studying permutation set embedded into the Euclidean space from different points of view in order to offer new approaches to constrained permutation-based optimization. 2 Optimization Problem of Polynomials on Permutations Consider the optimization problem on permutation set in the following formulation. Let Π be permutation space on which functional  : Π  R1 is defined. We are looking for   Π such that   arg min (  ) , (1) Π where Π  Π is a feasible set. We perform a mapping  : Π  E between elements   Π and vectors x =  x1 ,x2 ,..., xn   E  R n , i.e., suppose x = ψ(π), π = ψ -1 (x)   Π, x  E . Combinatorial sets for which such mapping can be established are called Euclidean combinatorial sets. Permutation set is Euclidean combinatorial one, which is espe- cially important for further research in this paper. Denote J n = 1,...,n . Let G   gi , i  J n  be a set of real numbers such that 0  g1  g 2  ...  g n . To each    1 ,..., n   Π we correspond vector x =  x1 , x2 ,...,xn   R n , assuming xi = g πi , i  J n . The set of such vectors x =  x1 ,x2 ,..., xn  induces a finite point configuration    g ,g ,...,g  be a multiset of real numbers such that En (G)  R n . Let G 1 2 n 0 < g1  g 2  ...  g n .   R n be permutation set with repetitions. For both sets E (G) and Then En (G) n  , we will use the same notation E . En (G) Suppose function f : E  R1 is such that f(x) = ξ(ψ -1 (x)) for all x  E . Consider a discrete optimization problem: to find x  arg min f (x) , (2) xE  E where E   ( Π  . The problems (1) and (2) are equivalent in the sense that if a solution x  E  of the problem (2) is found, then    1 ( x ) is a solution of the problem (1). We reformulate (2) in the form f  x   min , x   , (3) where set  is given by the constraints: xE , (4) i  x   0, i  J k , (5) φi  x  = 0, i  J m \ J k . (6) and functions f  x  , φi  x  , i  J m , are defined on E . Thus, X= x  E : i (x)  0, i  J k , i (x)  0,i  J m \ J k  . . 3 Properties of Polynomials on Permutation Set Properties of the problem (3) - (6) are determined by properties of permutation set E and behavior of functions f  x  , φi  x  , i  J m on R n , as well as on E  R n . Let functions f  x  , φi  x  , i  J m be polynomials. Theorem 1. For any polynomial f  x  , there exists a constant С and a polyno- mial f  x  , that can be represented as a positive linear combination of monomials, such that f  x   f  x   С for any x  E . Proof of the theorem follows from the fact that any symmetric function takes a constant value on E . We choose a positive linear combination of monomials as the symmetric function. Then any monomial with a negative coefficient can be repre- sented on E by a positive linear combination of monomials and a constant. An important property of a polynomial function f : E  R1 is the possibility of constructing its convex extension to a convex set Х  conv E . Definition 1. A function f : X  R1 defined on a convex set X is called a con- vex extension of function f : E  R1 onto X if f  x  = f  x  for any x  E  Х . To indicate that equality of functions holds on E , we will use a notation f  x   f  x  . E The theory of convex extensions of functions defined on combinatorial sets mapped onto R n , is considered in [15] and is based on the following theorem. Theorem 2. Let E = vert conv E . Then for any function f : E  R1 there exists a convex function f : conv E  R1 , such that f  x   f  x  . E Definition 2. A finite set E satisfying a condition E = vert conv E is called vertex- located. A convex hull of any finite set E  R n is a polytope P  conv E whose vertices form a vertex located set. Permutation set E is vertex located and coincides with a set of vertices of the permutohedron P described by the following linear system n n  xi   gi (7) i 1 i 1   xi   gi , (8) i i 1 where the summation is over various indexes from subsets   J n of the cardinality . Note that for any  , equality n n  (xi   )2   ( gi   )2 (9) i 1 i 1 holds for points of E . Thus, set E belongs to a family (9) of hyperspheres centered at the point   ( , ,...,  )  R n with a radius 1/ 2  n  r =   (gi   )2  (10)    i=1  and a parameter   R1 . The minimum value of the radii is attained at 1 n =  gi . n i=1 (11) Theorem 3 [16]. A point x  E if and only if it satisfies the system (7)-(9). Definition 3. Finite set E  R n that belongs to both a hypersphere and a vertex set of a polytope is called polyhedral-spherical. Properties of polyhedral-spherical sets were studied in [17–19] and adapted to permutation set. 4 Convex Extensions of Polynomials on Permutation Set Let us present new approaches to constructing convex extensions of polynomials defined on permutation set E . The extensions will be formed by induction. By assumption E  Rn0  int Rn . Clearly, any monomial with a positive coefficient is positive on Rn0 . For convex extensions of monomials, we also require positivity on Rn0 Remark 1. A square of any positive convex function is also a convex function. We will use this fact for a recursive construction of convex extensions monomials from already constructed ones of lower degrees. A monomial of a degree k is represented in the form: n ( x )   xi i , k1  k2  ...  kn  k  1 . k Fk( k...k ) (12) 1 n i 1 If k  1 , then Fk( 1...k ) ( x )  xi , 1 n where ki  1, k j  0 , j  J n , j  i . A convex extension of this function will coincide with the original one and positive on Rn0 , i.e.,  ( 1) ( x )  F( 1 ) ( x ) . Fk ...k 1 k ...k n 1 n For a quadratic monomial Fk( 2...k ) ( x ) we offer the following convex extension 1 n n onto R  xi2 , if ki  2, k j  0 j  J n , j  i;     (2) F̂k ...k ( x )   1  n n    ( xi  x j )   xk   g k  , if ki  k j  1, i, j  J n , j  i. 1 n 2 2 2  2  k 1 k 1     k  i, j  Positive convex extension of Fk( 2...k ) ( x ) onto Rn0 has the form 1 n 1 n k ...k   ( 2 ) ( x )  max 0,Fˆ ( 2 ) ( x ) . Fk ...k 1 n  We construct a positive convex extension onto Rn0 for monomial (12) of a de- gree k under the assumption that for any monomials of degree less k such extensions have been constructed. It is true Fk( k...k ) ( x )  F (j j...) j ( x )Fl( k...l j ) ( x )  1 n 1 n 1 n  1 ( j)      2 2 2 ( k j ) ( j) ( k j )   F j1 ... jn ( x )  Fl1 ...ln ( x )  F j1 ... jn ( x )  Fl1 ...ln ( x )  , 2  where j  (k  1 ) 2  , li  ki  ji , i  J n . Based on the induction hypothesis for monomials of degree less k and taking into account Remark 1 and Theorem 1, we can construct a convex extension F̂k( k...k ) (x). 1 n Then a positive convex extension on Rn0 is 1 n k ...k   ( k ) ( x )  max 0,Fˆ ( k ) ( x ) . Fk ...k 1 n  The considered approach to constructing the convex extension is generally compli- cated and yields no smooth functions. Depending on a class of functions in the problem (3)-(6), simpler algorithms can be offered. In the article [17], such an ap- proach to the construction of smooth convex extensions of monomials defined on permutation set was proposed. Theorem 4. For any monomial Fk ...k ( x ) of the form (10) defined on a set E , 1 n there exists a smooth convex extension onto Rn0 given by a formula   n  n k  F kk ...k ( x )    i   i 1 n g  xi ,  i 1  i 1 where μ = max ki . iJ n Corollary. For any polynomial defined on a set E  Rn0 , there exists a smooth convex extension onto Rn0 . 5 Optimization of Polynomials on Permutations with Constraints Consider the optimization problem (3)-(6) and implement the following equivalent transformations to it. Represent equations (6) in the form i  x   0,  i  x   0, i  J m \ J k . Next, for polynomials f  x  , i  x  , i  J m , we construct the following convex ex- tensions onto a convex set P  E : f  x  = f  x  , E i  x  = i  x  , i  J m , E i  x  =  i-m+k  x  , i  J q \ J m , q  2m  k . E Let us form an optimization problem f  x   min , x   , (13) where the set  satisfies (3) and the system of inequalities i  x   0, i  J q , (14) Problems (3)-(6) and (13),(14) are equivalent in the sense that arg min f (x)  arg min f (x) . xX  xX  in the form Let us consider X  =E  W , X where  W  x   : gi (x)  0, i  J q .  As a result, we have constructed a polyhedral relaxation of the original problem as a convex optimization problem f  x   min , x  W , (15) One of the interesting properties of permutation set is its decompositions into per- mutation sets of lower dimension lying on parallel planes. For instance, if x =  x1 ,x2 ,...,xn   En ( G  holds  ) , then for any x  G i  )= E (G En ( G  i ) x , n-1 i where  \ x  , i  J .  i =G G i n Evidently, when solving the problem (13),(14), such a decomposition induces con- vex optimization problems again. In fact, the offered branching scheme, used recur- sively, allows organizing branch and bound schemes to solve the problem (15). In this case, lower bounds correspond to solutions of the induced convex programs, where the number of levels of a decision trees dos not exceed n . Also, note that a specifics of the permutohedron and permutation set allows strengthening the lower bounds [20]. Let us describe some approaches to optimization on permutations based on its polyhedral-spherical structure. One of them uses an idea of optimization of convex objective function on the hypersphere described by equation (9). In the general case, the exact methods to solve this problem are unknown. An exception is a linear or convex quadratic function f  x  . This feature underlies an approach to solve the quadratic optimization problem on E offered in [20]. Clearly, an intersection of a hypersphere with a hyperplane yields a lower-dimension sphere. This allows perform- ing a decomposition of the original problem into simpler ones in accordance to the decomposition of E into hyperplanes parallel to facets of permutohedron, followed by solving induced problems of quadratic function optimization on a sphere of lower dimension. It is of interest to apply the penalty method to the problem (15). We offer an ap- proximate method for solving this problem based on using of a polyhedral-spherical representation of the set E , i.e., its presentation as the intersection of polytope (7), (8) with hypersphere (9). Consider the following penalty function: q   . 2 F(  k , x )  f  x  +  k  max 0,i  x  i 1 It is clear that, given that penalty coefficients  k  0 , the following sequence of optimization problems F(  k ,x )  min, x   , k  consists of convex programs, whose solutions, under rather general conditions and  k   , converge to a solution of the problem (15). Let us introduce one more optimization approach based on the use of the following penalty function: 2  n  (  k ,k ,x )  F(  k ,x )  k   (xi   )2  r 2  ,    i 1  where  k  0 , k  0 are penalty coefficients, r and  are given by expressions (10), (11), respectively. Then for sufficiently large  k and k , a solution of the following problem (  k ,k ,x )  min, x   (16) can be considered as an approximate solution to the problem (3)-(6). When solving optimization problems on permutohedron P , auxiliary linear and quadratic optimization problems arise, which are solvable explicitly using the proper- ties of permutation set [16,21,22]. For instance, the minimization of a linear function on E is reduced to the ordering of its coefficients. Similarly, the problems of finding the nearest vertex and facet of the permutohedron are solvable. This allows offering modifications of the conditional gradient method and the gradient projection method for solving nonlinear optimization problems on the permutohedron. As a model constrained optimization problem on permutation set, the problem of balancing rotating discretely distributed masses was considered [23]. There are n blades with masses i , i  J n , that are placed on a balanced disk with a given angular step. It is required that masses of successively placed blades should differ by at least the value 1 an at most  2 . The goal is to minimize the total unbalance of the whole system. Mathematically, the problem can be represented as the optimization problem on the permutation set E of the following objective function 1/ 2  n 2   n   2 f ( x )    xi cos 2 i n     xi sin 2 i n      i 1        i 1   subject to constraints 1  xi 1  xi   2 , i  J n-1 , 1  xn  x1   2 .    , ,...,  . A test problem of balancing was The set E is induced by G 1 2 n formed and solved with the following parameters: n  100 , 1  0,2 ,  2  1,0 , i  i , i  J n . PC with characteristics i3/8G/SSD 256G was used. A solution was obtained by the penalty method in the formulation (16) with parameters  k  10 , k  5 . Namely, the total unbalance of 0.31 was obtained for the running time 17 sec. In addition, the test problem of balancing rotating 96 blades masses presented in [23] was solved resulted in the total unbalance 0.07 obtained over 9 sec. 6 Conclusions The paper presents new approaches to solving permutation-based problems allowing embedding into the Euclidean space. The main result consists in the reduction of an arbitrary problem of conditional optimization of a polynomial function defined on a set of permutations to optimization of a convex objective function with convex func- tional restrictions on a vertex located set. Thus, for any permutation-based optimiza- tion problem on permutations with arbitrary constraints, an equivalent problem is constructed, where convex extensions of its objective function and functional con- straints participate. Now, geometric properties of permutation set and permutohedron, as well as fea- tures of continuous and convex optimization methods, become applicable to the solu- tion of new classes of combinatorial optimization problems. The results of this paper can be extended to optimization problems on other vertex-located and polyhedral- spherical sets, in particular, on Boolean and binary ones, known by a variety of prac- tical and theoretical applications [2,5,8-11]. In addition, since the sets of even, odd, alternating, distance, cyclic, circular, complete permutations are subsets of the of permutation set , the above results also apply to them. References 1. Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. 6th ed. 2018 edition. Springer, New York (2018). 2. Pardalos, et al.: Handbook of combinatorial optimization. Springer, New York (2013). 3. Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Mineola : Dover Publications (2013). 4. Schrijver, A.: Combinatorial optimization: polyhedra and efficiency. Berlin Heidelberg: Springer-Verlag (2003). 5. Burkard, R.E.: Quadratic assignment problems. Handbook of combinatorial optimization, vol. 5(1), pp. 2741–2814 (2013). 6. Onwubolu, G.C., Davendra, D. (Eds.): Differential evolution: A Handbook for global per- mutation-based combinatorial optimization. Springer-Verlag, Berlin Heidelberg (2009). 7. Mehdi, M.: Parallel hybrid optimization methods for permutation based problems. PhD thesis. Université des Sciences et Technologie de Lille (2011). 8. Brualdi, R.A.: Combinatorial matrix classes. Cambridge: University Press (2006). 9. Kochenberg, G., et. al.: The unconstrained binary quadratic programming problem: a sur- vey. Journal of Combinatorial Optimization, vol 1, pp. 58-81 (2014). 10. Bohn, A., et. al.: Enumeration of 2-Level Polytopes. Algorithms - ESA 2015, Berlin, Hei- delberg: Springer, pp. 191–202 (2015). 11. Bona, M . : Combinatorics of Permutations. Boca Raton, FL: Chapman Hall-CRC (2012). 12. Korsh, J.F., LaFollette, P.S.: Loopless array generation of multiset permutations. Comput. Journal, vol. 47(5), pp. 612-621 (2004). 13. Skala, M.: Counting distance permutations. Journal of Discrete Algorithms, vol. 7, no. 1, pp. 49–61 (2009). 14. Weisstein, E.W.: CRC concise encyclopedia of mathematics. Second Edition. Chapman and Hall/CRC, Boca Raton (2002). 15. Yakovlev, S.: Convex extensions in combinatorial optimization and their applications. Springer Optimization and its Applications, vol. 130, pp. 567-584 (2017). 16. Pichugina, O.S., Yakovlev, S.V.: Functional and analytic representations of the general permutations. Eastern-European Journal of Enterprise Technologies, vol. 1(4), pp. 27-38 (2016). 17. Yakovlev, S.V., Pichugina, O.S.: Properties of combinatorial optimization problems over polyhedral-spherical sets. Cybernetics and Systems Analysis, vol. 54(1), pp. 99-109 (2018). 18. Pichugina, O., Yakovlev, S.: Optimization on Polyhedral-Spherical Sets: Theory and Ap- plications. In 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneer- ing (UKRCON), pp. 1167-1175 (2017). 19. Yakovlev, S.V., et al.: Polyhedral spherical configuration in discrete optimization. J. of Autom. and Information Sci., vol. 51(1), pp.38-50 (2019). 20. Yakovlev, S.V.: Bounds on the minimum of convex functions on Euclidean combinatorial sets. Cybernetics and Systems Analysis, vol. 23(3), pp. 385-391 (1989). 21. Stoyan, Y.G., et al.: Quadratic optimization on combinatorial sets in Rn. Cybernetics and Systems Analysis, vol. 27(4), pp. 561–567 (1991). 22. Yakovlev, S.V., Valuiskaya, O.A.: Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints. Ukrainian Mathematical Journal, vol. 53(9), pp. 1535-1545 (2001). 23. Stoyan, Y.G., et al.: Method of balancing rotating discretely distributed masses. Energomashinostroenie, vol. 2, pp. 4-5 (1982).