Shortest Distance between 2 convex sets

[TPks]

Hi, I hope someone can help me out with this problem:

Let set S be defined by (x in En :f(x) <=c}
f: En -> E1 is convex and differentiable and gradient of f(xo) is not 0 when f(x) = c. Let xo be a point such that f(xo) = c and let d = gradient at xo. Let lamda be any positive number and define x1 = xo+ lamda(d)
we know:
||x1-xo|| <= ||x1-x||
suppse we have 2 islands:
f(x,y) <= c1 and g(x,y) <= c2
where f and g are contibuously differentiable and strictly convex functions whose gradient vectors are non zero when f(x,y) = c1 and g(x,y)=c2

We need to build a bridge between the two islands of shortest possible length. Using the result of the theorem of separating hyperplane, devise a search technique to find the optimal bridge location.

Test your routine on:
f(x,y)= x^2 +2y^2, c1=1
g(x,y)= (x-4)^2 + (y-3)^2, c2 = 1

 

[Stephen Tashi]

Did you get an answer for this? It sounds like you are to base you algorithm on hunting for a line segment (a "bridge") joining the surfaces of the two sets such that the separating hyperplane normal to that line segment is parallel to the tangent planes to the surface where the same line segment hits them. But what's the best way to search for such a line segment?

You could start with an arbitrary line segment. Look at the tangent planes at the ends of the line segment and determine which way to move the ends in order make the line segment more perpendicular to the tangent plane and then move the end of the current line a little way in that direction to get a new line segment.