Problem with a simple benchmark function

[avaneev]

Hi! Congratulations on your CMA-ES method! I myself am developing an optimization method, and I'm using your method for comparison purposes. Your method is very competitive, I can't reach its convergence speed yet in dimensions above 10.

My benchmarking suite uses random offsetting and rotation in the same manner as BBOB benchmark suite.

I'm having problems with CMA-ES optimizing such function in 14 dimensions, x[] is in the range -25 to 25. CMA-ES simply crashes the program without providing any output. I have a diverse set of functions, and basically only this function causes issues. Note that a random offsetting and rotation should be applied to this function.

static double calcZeroSum( const double* const x, const int N )
{
    double s = 0.0;
    int i;
    for( i = 0; i < N; i++ )
    {
        s += x[i];
    }
    return( s == 0.0 ? 0.0 : 1.0+pow(10000.0*fabs(s),0.5) );
}

[nikohansen]

Thanks for the feedback. Could you provide the calling code and the parameters (file) used? There should also be some output in the beginning when the CMA object is initialized, am I wrong? This may be quite helpful to proceed in finding the reasons.

[avaneev]

I'm using a custom CMA_ES initialization, derived from BBOB code. There's no output. I've found out that in some dimensions (e.g. 10 or 20), this function does optimize correctly, so the "bug" is generally hard to detect.

for( i = 0; i < Dims; i++ )
{
    initial_solution[ i ] = lower[ i ] + ( upper[ i ] - lower[ i ]) * getRndUniform();
    initial_sigma[ i ] = ( upper[ i ] - lower[ i ]) / 6.0;
}
cmaes_t cma;
const int lambda = 100;
cmaes_init_para( &cma, Dims, initial_solution, initial_sigma, 0, lambda, "no" );
cma.sp.filename = strdup( "no" );
y = cmaes_init_final( &cma );

The inner loop is:

i = 0;
bool IsFinished = false;
while( !IsFinished )
{
    X = cmaes_SamplePopulation( &cma );
    int k;
    for( k = 0; k < cmaes_Get( &cma, "lambda" ); k++ )
    {
        y[ k ] = calcZeroSum( X[ k ], Dims );
        i++;

        if( i > MaxIters )
        {
            IsFinished = true;
            break;
        }
    }
    cmaes_UpdateDistribution( &cma, y );
}

Sometimes function optimizes without problems in dimensions 14, but that does not happen every day and every run, maybe something related to random seed.

[nikohansen]

Below what I get in Python. The condition number is increasing quickly, because the solution of the problem is an n-1-dimensional subspace and only one principal axis length is quickly converging towards zero.

[avaneev]

Yes, convergence plot is understandable as there is an infinite number of minimizers. The original function formulation however is a bit different. Note that the function equals zero at 0.0 sum, >1 elsewhere. Maybe that's what causes issues and function can be considered "ill-formed".

return( s == 0.0 ? 0.0 : 1.0+pow(10000.0*fabs(s),0.5) );

This function was taken here: http://infinity77.net/global_optimization/test_functions_nd_Z.html#go_benchmark.ZeroSum

[nikohansen]

Note that the function equals zero at 0.0 sum, >1 elsewhere.

Yes, I saw that.

Maybe that's what causes issues and function can be considered "ill-formed".

No. The algorithm is invariant to monotonous f-transformations (that is, both functions lead to identical algorithm behavior apart from termination) and such a solution is anyway only with negligible probability ever actually attained and evaluated (as we can see the minimal attained value in the above shown run was above 1.00001).

[avaneev]

I would happily try to find randseed at which the function fails, but even when I constantly specify inseed=0 in the cmaes_init_para() function, every run returns different results, so there must be some other source of reseeding.

[nikohansen]

inseed=0 may be code for no input seed, hence it is chosen at random.

c-cmaes/cmaes_initials.par

Line 43 in eda8268

seed 0 # 0 == by time, also regard maxTimeFractionForEigendecomposition

[avaneev]

Ah, thanks, missed that part. I'll try to locate a problematic inseed along with exact offset and rotation matrix.

Edit: Well, when I specify inseed>0, some randomness still presents.

[nikohansen]

Well, when I specify inseed>0, some randomness still presents.

maybe check that the setting is not overwritten somewhere in the code

[avaneev]

I've finally discovered a very strange behavior on Intel i7-7700K processor's side. The random seed is initialized correctly, I've debugged this inside CMAES code. The problem is, at some iteration objective function values start to diverge on a purely random basis. When I run program twice, there is always a point where function values diverge: e.g. in run 1 I get 128.4656403030385 and in run 2 I get 121.18351111048705 at the same iteration index. I tried compiling with and without optimizations, for IA32 and SSE2 instructions, outcome is the same.

This makes it impossible to pinpoint the exact random seed where the optimization of the subject function fails. I think you may close this issue.

[avaneev]

There may be a bug in CMA-ES code present, but I'm not sure.

[avaneev]

There's one more benchmark function I've found to cause occasional crash with CMA-ES, in 14 dimensions and population size 48:

double calcBrown( const double* const x, const int N ) {
    double s = 0.0;
    for( int i = 0; i < N - 1; i++ ) {
        s += pow(sqr(x[i]),sqr(x[i+1])+1.0) +
            pow(sqr(x[i+1]),sqr(x[i]+1.0));
    }
    return( s );
}
lb=-4
ub=4
minf=0