Some Results by George Bilchev

Suitable bounds which can be optionally imposed are

x_i in [-n,n] for i=1,...,n.

The global minimum is at x_i=i with f(x)=0.

Suggested specific cases: (n,beta) = (4,50), (4,0.5), (10,10^9), (10,10^7); the first and third are easy, the other two somewhat harder. Since these are nowadays also easy, increase n or decrease beta (but see below for tiny beta).

**PERM0(n,beta):**

`f(x) = sum_{k=1}^n (sum_{i=1}^n [i+beta][(x_i)^k-(1/i)^k])^2`

Suitable bounds which can be optionally imposed are

x_i in [-1,1] for i=1,...,n.

The global minimum is at x_i=1/i with f(x)=0.

Suggested specific cases: (n,beta) = (4,10) (10,100) but since these have become easy, increase n or decrease beta.

beta is a nonnegative parameter. The smaller beta, the more
difficult both problems become since the global minimum
is difficult to distinguish from local minima near permuted
solutions. For beta=0, every permuted solution is a global minimum,
too.

For tiny beta, the problem becomes (apparently) simpler
for algorithms trying to find only one global minimum point since
one of the many near-global local optima is found instead.

These problems therefore appear useful to test the ability of a global minimization algorithm to reach the global minimum sucessfully and to discriminate it from other local minima.

Because of the special permutation structure of the problems, genetic algorithms which can exchange components of different candidates might have a slight advantage.

The global minimum has the value 0 if the b_k are chosen
as b_k = sum_{i=1}^n z_i^k for a target solution z.

No other solutions exist. (Proof: Use the theory of symmetric functions to rewrite the problem as one of finding the zeros of a polynomial with coefficients determined by b.)

Of interest is how the work scales for

**POWERSUM1(n):** b from z_i = 1/i, bounds x_i in [0,2],

**POWERSUM2(n):** b from x_i = i-1, bounds x_i in [-n,n],

when n=5,10,20,30,40,50,100

Suitable bound constraints for the general problems are x_i in [u,v] (i=1,...,n), where u=min(z_i), v=max(z_i).

All permutations of a solution are solutions, too. In branch and bound codes, one may add the constraint x_1 le x_2 le ... le x_n to avoid the exponential increase of work due to permuted solutions.

The problem becomes harder when a solution with multiple x_i exists, since then the rank of the Hessian at the solution decreases, and the objective function becomes there extremely flat in some directions. Thus the problem can assess the ability of algorithms to find highly accurate solutions near singular minimal points.

A simple instance is the singular problem POWERSUM(8,18,44,114) with bounds [0,4]^4 and solution (1,2,2,3). The goal here is to find the solution with high accuracy, not just the optimal function value (which is much easier to find to high absolute accuracy).

Suitable bounds for a bound constrained version would be
[-n^2,n^2] for each component.

The solution is x_i=i(n+1-i) with f(x)=-n(n+4)(n-1)/6.

This is a simple discretized variational problem, convex, quadratic, with a unique local minimizer and a tridiagonal Hessian. The scaling behaviour for increasing n gives an idea on the efficiency of localizing minima once the region of attraction (which here is everything) is found; most local methods only need O(n^2) function evaluations, or only O(n) (function+gradient) evaluations. A global optimization code that has difficulties with solving this problem for n=100, say, is of limited worth only.

The strong coupling between the variables causes difficulties for genetic algorithms.

The problem is typical for many problems from control theory, though the latter are usually nonquadratic and often nonconvex.

Equations (2.2) - (2.6) in

Results of fairly exhaustive multiple random start searches for these problems are available from F.H. Stillinger (fhs@allwise.att.com) and from G. Bilchev. See also Studies of an off-lattice model for protein folding (375K, by A. Irbäck. and F. Potthast)

Optimization Test Problem Collection

Suggestions for a global optimization contest

Global Optimization

my home page (http://www.mat.univie.ac.at/~neum)

Arnold Neumaier (Arnold.Neumaier@univie.ac.at)