Comment by msteffen
3 days ago
I'm trying to work through the math here, and I don't understand why these two propositions are equivalent:
1) min_{x,y} |x-y|^2
x ∈ A
y ∈ B
2) = min_{x,y} d
d ≥ |x-y|^2
x ∈ A
y ∈ B
What is 'd'? If d is much greater than |x-y|^2 at the actual (x, y) with minimal distance, and equal to |x-y|^2 at some other (x', y'), couldn't (2) yield a different, wrong solution? Is it implied that 'd' is a measure or something, such that it's somehow constrained or bounded to prevent this?
This is the epigraph form of the problem. You try to find the point with the lowest height in the epigraph.
https://en.wikipedia.org/wiki/Epigraph_(mathematics)
Ah, got it, thanks!!
But why would d be much greater. The problem asks to minimise d, and so it cannot be greater than the smallest |x-y|^2.
I think you are missing that d, x, and y are variables that get optimized over. Any choice of d lower than the the solution to 1) is infeasible. Any d higher than the solution to 1) is suboptimal.
edit: I see now that the problem 2) is missing d in the subscript of optimization variables. I think this is a typo.
I can't read substack on my phone, so I can't see the article, but the correct statement that is closest to what you have written is just that d is any real number satisfying this inequality. We define a subset U of AxBxR by
U={(a,b,x):x>|a-b|^2}
and then were looking for the infimum of (the image of) U under the third coordinate function
d(a,b,x)=x