What is that optimization algorithm called?

  • A+
Category:Languages

I've got a piece of undocumented code, which I have to understand to fix an error. The following method is called optimization and it is supposed to find the maximum of a very complex function f. Unfortunately, it fails under some circumstances (i.e. it reaches the "Max iteration reached" line).

I already tried to write some unit tests, but this didn't help much.

So I want to understand how this method really works and if it implements a specific, and well known optimization algorithm. Maybe I can then understand, if it is suitable to solve the required equations.

public static double optimization(double x1, double x2, double x3, Function<Double, Double> f, double epsilon) {     double y1 = f.apply(x1);     double y2 = f.apply(x2);     double y3 = f.apply(x3);      double a = (   x1*(y2-y3)+   x2*(y3-y1)+   x3*(y1-y2)) / ((x1-x2)*(x1-x3)*(x3-x2));     double b = (x1*x1*(y2-y3)+x2*x2*(y3-y1)+x3*x3*(y1-y2)) / ((x1-x2)*(x1-x3)*(x2-x3));     int i=0;     do {         i=i+1;          x3=x2;         x2=x1;         x1=-1.*b/(2*a);          y1=f.apply(x1);         y2=f.apply(x2);         y3=f.apply(x3);          a = (   x1*(y2-y3)+   x2*(y3-y1)+   x3*(y1-y2))/((x1-x2)*(x1-x3)*(x3-x2));         b = (x1*x1*(y2-y3)+x2*x2*(y3-y1)+x3*x3*(y1-y2))/((x1-x2)*(x1-x3)*(x2-x3));     } while((Math.abs(x1 - x2) > epsilon) && (i<1000));     if (i==1000){         Log.debug("Max iteration reached");     }     return x1; } 

 


This seems to be a Successive parabolic interpolation.

One of the clues is the replacement of the oldest of three estimates by the position of the extremum,

    x3= x2;     x2= x1;     x1= -1. * b / (2 * a); 

The method may fail if the estimates do not achieve an extremum configuration (in particular at an inflection point).

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: