2
$\begingroup$

Let $A, B$ be two convex and closed subsets of $\mathbb{R}^n$. We would like to the minimum distance between these two sets. i.e., we want to find a solution for the following problem. $$ \min \{||x-y||~ ~\hbox{for}~ x\in A, y\in B\}$$.

I would like to see if there is a method to find a solution for this problem in general in the theory of optimization.

Improve this question
$\endgroup$
5
  • $\begingroup$ This is a bit broad formulated... You mean a numerical method? $\endgroup$
    – András Bátkai
    Commented Apr 5, 2014 at 19:55
  • $\begingroup$ yes! numerical method should be ok for my case. $\endgroup$
    – Math123
    Commented Apr 5, 2014 at 19:56
  • $\begingroup$ How are the convex sets represented combinatorially? Aside from special cases (eg intersection of half-spaces or vertices of polyhedra) I'm not quite sure what the "input" to your desired numerical methods are allowed to be. $\endgroup$
    – Vidit Nanda
    Commented Apr 5, 2014 at 19:59
  • $\begingroup$ Let's say we have $A$ and $B$ as follows. Consider the functions $g(x,y)= xy$ and $f$ a differentiable function on $\mathbb{R}^2$. $A= \{X=\nabla f(u)~\hbox{for}~ u\in \mathbb{R}^2\}$ and $B= \{(x,y)~|~g(x,y)= c~\hbox{for some} c\in \mathbb{R}\}$. I don't know how I can input my constraints in numerical methods as I have infinite constrants... $\endgroup$
    – Math123
    Commented Apr 5, 2014 at 20:06
  • $\begingroup$ Your $B$ is not a convex set; in fact, for any two points $a, b\in B$ the line between $a$ and $b$ is not contained within $B$. If you instead define $B=\{(x, y) x\geq 0 \wedge y\geq 0\wedge xy\geq c\}$ then $B$ is convex, but that definition may not satisfy your needs. $\endgroup$
    – Steven Stadnicki
    Commented Apr 6, 2014 at 4:57

5 Answers 5

Reset to default
2
$\begingroup$

You are trying to solve what is known as a best approximation problem.

  1. von Neumann's alternating projections does not work here (as might have been perhaps suggested above)
  2. You can use Dykstra's projection algorithm, which will find the desired projection (some reformulation will be needed though before you can apply it)
  3. See the paper by Bauschke, Combettes, and Luke on reflection methods---the references in that paper also put this problem in wider context. The "averaged reflections" method (which is essentially the Douglas-Rachford splitting scheme) often works better / faster than Dykstra's projection method.
Improve this answer
$\endgroup$
5
  • $\begingroup$ PS: Both Dykstra and Reflection methods rely on having access to a projection oracle for each of the convex sets. $\endgroup$
    – Suvrit
    Commented Apr 6, 2014 at 16:58
  • $\begingroup$ Just out of curiosity: is there a standard reason/reference why the alternating projection method does not work? $\endgroup$
    – Igor Rivin
    Commented Apr 7, 2014 at 19:38
  • $\begingroup$ @Suvrit, If I want to use Dykstra's projection algorithm for my problem then what could be the best criterion to get the best approximation for my problem? I mean under which criterion I can stop running the algorithm and get a good approximation for my points? $\endgroup$
    – Math123
    Commented Apr 8, 2014 at 14:20
  • $\begingroup$ @Igor: to my mind the greediness of AP can make it get "stuck" (e.g., at a corner). But more basically, AP just generates sequences that converges to a feasible point (because feasibility is what it set out to solve in the first place), there is nothing in the AP which should make it converge to the "best" feasible point (unless the set of feasible points in a singleton) --- a nice example is Example 11.24 in the book: "Convex analysis and monotone operator theory..." by Bauschke and Combettes. $\endgroup$
    – Suvrit
    Commented Apr 8, 2014 at 16:05
  • $\begingroup$ @Math123: If your sets are polyhedral, then both Dykstra and alternating reflections may (in principle, but hard to quantify) converge at a linear rate, so you can "detect" when to stop. If your sets are "almost parallel" then both will slow down --- you have to experiment to see what convergence criterion works for you (in the worst case, to obtain an $\epsilon$-accurate solution, these methods may require $O(1/\epsilon)$ iterations, I think) $\endgroup$
    – Suvrit
    Commented Apr 8, 2014 at 16:08
2
$\begingroup$

In the closed convex case there are some fairly efficient algorithms, as long as you can efficiently project any point $x$ onto $A$ and $B$. This class of algorithms (named alternating projections, and tracing back to von Neumann) iterate projecting first on $A$, then on $B$, and repeating until the sequence stabilizes. If the intersection between $A$ and $B$ is nonempty, then this sequence converges to some point in the intersection. If they don't intersect, but the distance between $A$ and $B$ is positive, the odd and even iterates converge respectively to the minimizers $x$ and $y$.

See http://en.wikipedia.org/wiki/Projections_onto_convex_sets for more details.

Improve this answer
$\endgroup$
2
$\begingroup$

I'd like to give a little more general answer.

The problem of finding the minimum distance between two (convex) sets is a mainstay of the optimization theory. In fact, even finding the distance of a point to an hyper plane is such a problem.

So in your case, given that $A,B$ are compact closed sets, your formulation can be solved fairly efficiently as long as you can express both sets in closed form. Indeed, the problem is a convex optimization problem, which can be solvable efficiently in many cases.

For instance, if $A,B$ can be expressed in terms of the intersection of convex constraints, i.e. some functions $g^i_B(),g_A^i()$,

$min_{x,y} ||x-y||_2$

$ s.t.$

$\quad g_A^i(x)\leq 0\quad i=1,\ldots,n_A$

$\quad g_B^i(y)\leq 0\quad i=1,\ldots,n_B$

then any algorithm for general convex optimization can do. If also all the functions can be expressed in conic form (see Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications) then the problem can be solved in polynomial time.

I myself have experienced solving some of this problem to test the optimization software produced the company I work in. Our solver, MOSEK, deals with conic optimization, which includes a fairly large number of possible convex set you can think about.

Of course, if your set is particularly structured or performance is a major issue, you must look for specialized algorithms. But as an advise, if you can I would use a general purpose solver as a basic, and usually robust, benchmark to compare against.

Improve this answer
$\endgroup$
1
$\begingroup$

This may help, as it applies to "arbitrary compact convex sets" in $\mathbb{R}^n$, although primarily applied to polytopes:

Llanas, B., M. Fernández de Sevilla, and V. Feliú. "An iterative algorithm for finding a nearest pair of points in two convex subsets of $\mathbb{R}^n$." Computers & Mathematics with Applications, 40.8 (2000): 971-983. (Elsevier link)

Llanas, Bernardo. "Efficient computation of the Hausdorff distance between polytopes by exterior random covering." Computational Optimization and Applications 30.2 (2005): 161-194. (MathSciNet review)

Here is the MathSciNet review:
 MSN review

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Joseph, the first one using iterative method would be helpful I guess! $\endgroup$
    – Math123
    Commented Apr 6, 2014 at 0:24
0
$\begingroup$

There is a much earlier (and seemingly very efficient) algorithm by Gilbert, Johnson, Kerthi. (1988, IEEE Journal of Robotics and Automation).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .