forum.alglib.net
http://forum.alglib.net/

Using minlbfgsoptimize for determining smallest distance
http://forum.alglib.net/viewtopic.php?f=2&t=592
Page 1 of 1

Author:  alexN [ Sun Jun 24, 2012 7:20 pm ]
Post subject:  Using minlbfgsoptimize for determining smallest distance

Hi all,

I try to find the smallest distance between two circles given in R3 using minlbfgsoptimize but it obviously fails (see attached image).

Each circle is given by its center C, a radius R and a normal vector N. Pairwise perpendicular vectors U and V are calculated with respect to N. All vectors are unit-vectors.
A point on the circle can be evaluated for a given angle alpha in the UV-plane:
Quote:
Circle K = C + R * cos(alpha) * U + R * sin(alpha) * V

For finding the smallest distance between two given circles the squared distance between two points on the circles is calculated and has to be minimized. The points on the circles are given by the angle theta for the first circle and the angle phi for the second circle:
Code:
public static void functionCircleCircle(double[] x, ref double func, object obj)
{
    Circle[] circles = (Circle[])obj;
    double theta = x[0];
    double phi = x[1];
    Vector w1 = Math.Cos(theta) * circles[0].U + Math.Sin(theta) * circles[0].V;
    Vector w2 = Math.Cos(phi) * circles[1].U + Math.Sin(phi) * circles[1].V;
    double d = (circles[1].Center - circles[0].Center + circles[1].Radius * w2 - circles[0].Radius * w1).Norm;
    func = d * d;
}

The optimization is done like this:
Code:
// define the circles
// first case
Circle c1 = new Circle(new Point(0, 0, 0), 10, new Vector(0, 0, 1));   // black circle
Circle c2 = new Circle(new Point(0, 0, 30), 10, new Vector(1, 0, 0));   // green circle

// second case
//Circle c1 = new Circle(new Point(0, 0, 0), 10, new Vector(0, 0, 1));   // black circle
//Circle c2 = new Circle(new Point(0, 0, 30), 10, new Vector(0, 1, 0));   // red circle

double[] x = new double[] { 0, 0 };   // initial guess
double epsg = 1.0e-6;
double epsf = 0;
double epsx = 0;
double diffstep = 1.0e-6;
int maxits = 0;
alglib.minlbfgsstate state;
alglib.minlbfgsreport rep;
alglib.minlbfgscreatef(1, x, diffstep, out state);
alglib.minlbfgssetcond(state, epsg, epsf, epsx, maxits);
alglib.minlbfgsoptimize(state, functionCircleCircle, null, circles);
alglib.minlbfgsresults(state, out x, out rep);

Point p1 = circles[0].Eval(x[0]);   // eval optimized angle on first circle
Point p2 = circles[1].Eval(x[1]);   // eval optimized angle on second circle
LineSegment segment = new LineSegment(p1, p2);   // this *should* be the shortest line between the two circles

// Output
Console.WriteLine("Theta = {0}\tPhi = {1}", x[0], x[1]);
Console.WriteLine("Length = {0}", segment.Length);

DrawCircle(circles[0]);
DrawCircle(circles[1]);
DrawLineSegment(segment);

It is clear that the distance in both cases equal each other. But it turns out, that the first case gives the correct result of 21.623 mm, while the second case gives 22.361 mm. In the attached image you can see that the position of the point on the black circle c1 is not optimized.

Can anyone give me a hint for a solution of this problem? Is there another suitable algo in alglib for solving this task while keeping in mind that later on not only the distance between circles but discs must be calculated!?

Thanks in advance,
Alex

Attachments:
DistanceCircleCircle.png
DistanceCircleCircle.png [ 101.97 KiB | Viewed 4970 times ]

Author:  Sergey.Bochkanov [ Mon Jun 25, 2012 6:00 am ]
Post subject:  Re: Using minlbfgsoptimize for determining smallest distance

Hello! It is not error, neither in ALGLIB, nor in your code. Algorithm stops in the second case because you start from the point where gradient is zero.

If you look at your picture, you will see that in both cases initial position is bottom point of the red/green circle (marked by red square) and rightmost point of the black circle (marked by red square). Your problem is symmetric, i.e. there always exist two identical solutions - "main" one and its mirror reflection. In the first case initial conditions are asymmetric, you start from the point which is closer to one of solutions. However, in the second case you start from the point which is halfway between both - thus gradient is zero, and algorithm stops.

If you start from the randomly chosen point, you will break down this symmetry, and (with almost 100%) probability your algorithm will converge to one of these two solutions.

Author:  alexN [ Mon Jun 25, 2012 12:35 pm ]
Post subject:  Re: Using minlbfgsoptimize for determining smallest distance

Hello Sergey, thanks for your answer.

That's the same solution, I came up with ;-) But I wanted to make sure, that there is no better way to solve my task... It works fine, as long as I randomize both start values, so that the algo does not start with a zero gradient. But I can not be sure that this is not the case, so it might be necessary to run the algo twice and return the smaller value.

Best regards,
Alex

Author:  Sergey.Bochkanov [ Mon Jun 25, 2012 1:42 pm ]
Post subject:  Re: Using minlbfgsoptimize for determining smallest distance

In fact, you can not be sure even with two restarts :) you can get 99.999% probability of success, but if you want to have 100% probability, you need infinitely many restarts.

It is not a problem for calculations which are executed just several times, but if you have to run optimization from thousands to millions of times, you may routinely encounter such "improbable" situations. In particular, we encounter them every week when we repeatedly test ALGLIB.

Author:  alexN [ Mon Jun 25, 2012 3:37 pm ]
Post subject:  Re: Using minlbfgsoptimize for determining smallest distance

Yes, I know :-) For practical reasons in approx. 50000 randomly created circle pairs it did work out. On the I other hand I could those start values that would create a zero gradient...
Thanks again for your help and your great lib!

Best regards,
Alex

Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/