On Constrained Optimization of Polynomials on Permutation Set

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 extensions of all functions involved in the model. New approaches to the construction of convex extensions of polynomials from the permutation set are proposed. Original optimization methods using a polyhedral-spherical structure of the set are offered. Decomposition schemes underlying some global optimization techniques on permutations are described. Results of numerical experiments are presented.

Keywords

• Combinatorial Optimization
• Constraints
• Permutation Set
• Polynomial
• Convex Extension

-

Various real-world problems can be modeled as optimization problems over the permutation 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 combinatorial 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 projection 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 feasibility 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, cyclic, 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.

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 (  ) ,

Π where Π  Π is a feasible set.

We perform a mapping  : Π  E

x =  x1 , x2 ,..., xn   E  Rn , i.e., suppose for all x  E .

Consider a discrete optimization problem: to find

f(x) = ξ(ψ-1(x)) x  arg

min f (x) , xEE x = ψ(π), π = ψ-1(x)   Π, x  E .

xi = gπi , i  Jn . 0 < g1  g2  ...  gn .

between elements   Π and vectors ( 1 ) ( 2 )

Combinatorial sets for which such mapping can be established are called Euclidean combinatorial sets. Permutation set is Euclidean combinatorial one, which is especially important for further research in this paper.

Denote Jn = 1,...,n . Let G  gi , i  Jn be a set of real numbers such that 0  g1  g2  ...  gn .

To

each x =  x1 , x2 ,..., xn   Rn , assuming    1 ,...,n   Π we correspond vector

The set of such vectors x =  x1 , x2 ,..., xn  induces a finite point configuration

En (G)  Rn . Let G  g1 , g2 ,..., gn be a multiset of real numbers such that

Then En (G)  Rn be permutation set with repetitions. For both sets En (G) and

En (G) , we will use the same notation E .

Suppose function f : E  R1 is such that

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 is a solution of the problem ( 1 ). We reformulate ( 2 ) in the form where set  is given by the constraints:

  1( x ) f  x  min , x   ,

x  E , i  x  0, i  Jk , φi  x = 0, i  Jm \ Jk . ( 3 ) ( 4 ) ( 5 ) ( 6 ) and functions f  x , φi  x , i  Jm , are defined on E .

Thus,

X=x  E : i (x)  0, i  Jk , i (x)  0,i  Jm \ Jk  . functions f  x , φi  x , i  Jm be polynomials.

Theorem 1. For any polynomial f  x , there exists a constant С and a polynomial 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 represented 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 convex extension of function f : E  R1 onto X if for any x  E  Х .

To indicate that equality of functions holds on E , we will use a notation

The theory of convex extensions of functions defined on combinatorial sets mapped onto Rn , 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 vertexlocated.

A convex hull of any finite set E  Rn 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 f  x  = f  x  f  x   f  x .

E n n  xi   gi i1 i1

  xi   gi , i i1  .

Note that for any  , equality

n n (xi   )2  ( gi   )2 i1 i1 where the summation is over various indexes from subsets   Jn of the cardinality holds for points of E .

Thus, set E belongs to a family ( 9 ) of hyperspheres centered at the point   ( ,,..., )  Rn with a radius ( 7 ) ( 8 ) ( 9 ) and a parameter   R1 . The minimum value of the radii is attained at  n 1/ 2 r =  (gi   )2    i=1   = 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  Rn 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 n extensions of monomials, we also require positivity on R0

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 Fk(1k..).kn ( x )   xiki , k1  k2  ... kn  k  1 .

i1 ( 12 ) A convex extension of this function will coincide with the original one and positive If k  1 , then where ki  1, k j  0 , j  Jn , j  i . on Rn0 , i.e.,

Fk(11..).kn ( x )  xi , F( 1 ) k1...kn ( x ) .

k1...kn ( x )  F( 1 )

For a quadratic monomial Fk(12..).kn ( x ) we offer the following convex extension onto Rn xi2 , if ki  2, k j  0 j  Jn , j  i;    Fˆk(12..).kn ( x )   1  n n   ( xi  x j )2   xk2   gk2  , if ki  k j  1, i, j  Jn , j  i.

 2  kk 1i, j k 1  Positive convex extension of Fk(12..).kn ( x ) onto Rn0 has the form Fk(12..).kn ( x )  max0, Fˆk(12..).kn ( x ) .

n

We construct a positive convex extension onto R0 for monomial ( 12 ) of a degree k under the assumption that for any monomials of degree less k such extensions have been constructed. It is true

Fk(1k...)kn ( x )  F( j ) ( x )Fl(1k...lnj )( x ) 

j1... jn  12   Fj(1j..).jn ( x )  Fl(1.k..lnj )( x )   Fj(1j..).jn ( x )   Fl(1k...lnj )( x )2  ,

2 2 where

j  (k  1 ) 2 , li  ki  ji , i  Jn .

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(1k..).kn ( x ) .

Then a positive convex extension on Rn0 is

Fk(1k..).kn ( x )  max0, Fˆk(1k..).kn ( x ) .

The considered approach to constructing the convex extension is generally complicated 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 approach to the construction of smooth convex extensions of monomials defined on permutation set was proposed.

Theorem 4. For any monomial Fk1...kn ( x ) of the form ( 10 ) defined on a set E , there exists a smooth convex extension onto Rn0 given by a formula

 n  n F kk1...kn ( x )    gi   i1  i1

 xiki  , μ = max ki .

iJn where convex extension onto Rn0 .

Corollary. For any polynomial defined on a set E  Rn0 , there exists a smooth 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  Jm \ Jk .

Next, for polynomials f  x , i  x , i  Jm , we construct the following convex extensions onto a convex set P  E : f  x = f  x ,

E i  x=E i  x ,i  Jm , i  x=  i-m+k  x , i  Jq \ Jm , q  2m  k .

E

Let us form an optimization problem

where the set  satisfies ( 3 ) and the system of inequalities f  x  min , x  , i  x  0, i  Jq ,

Problems (3)-(6) and (13),(14) are equivalent in the sense that (13) (14)

arg min f (x)  arg minf (x) . xX xX

Let us consider X in the form

where where

X =E  W , W  x   :gi (x)  0, i  Jq  .

En( G ) = En-1( Gi ) xi , Gi = G \xi  , i  Jn .

As a result, we have constructed a polyhedral relaxation of the original problem as a convex optimization problem

One of the interesting properties of permutation set is its decompositions into permutation sets of lower dimension lying on parallel planes. For instance, if x =  x1 , x2 ,..., xn   En ( G ) , then for any xi G holds f  x  min , x W , ( 15 )

Evidently, when solving the problem ( 13 ),( 14 ), such a decomposition induces convex optimization problems again. In fact, the offered branching scheme, used recursively, 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 performing 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 approximate 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:

It is clear that, given that penalty coefficients k  0 , the following sequence of optimization problems q 2 F( k , x ) f  x + k  max0,i  x  .

i1 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: 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 properties 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  Jn , 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

The set E is induced by G  1 ,2 ,...,n . A test problem of balancing was formed and solved with the following parameters:

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 functional restrictions on a vertex located set. Thus, for any permutation-based optimization problem on permutations with arbitrary constraints, an equivalent problem is constructed, where convex extensions of its objective function and functional constraints participate.

Now, geometric properties of permutation set and permutohedron, as well as features of continuous and convex optimization methods, become applicable to the solution of new classes of combinatorial optimization problems. The results of this paper can be extended to optimization problems on other vertex-located and polyhedralspherical sets, in particular, on Boolean and binary ones, known by a variety of practical 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 permutation-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 survey . Journal of Combinatorial Optimization , vol 1 , pp. 58 - 81 ( 2014 ).

10. Bohn , A. , et. al.: Enumeration of 2-Level Polytopes. Algorithms - ESA 2015 , Berlin, Heidelberg: 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 Applications . In 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (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 ).