# Unconstrained Optimization - Minimum Distance Between Point and Curve

Background:

I am writing some software can fit a mathematical curve to data using different regression techniques. I currently have Ordinary Least Squares and Least Absolute Deviations mostly implemented, and am now working on Total Least Squares. In TLS, both x and y distances from the curve are minimized, rather than just y.

Problem:

In order to get my software to work, I need a closed-form solution to finding the minimum distance between a point $(x_{n}, y_{n})$ and a function $f(x)$ on an unbounded domain. It also needs to be reasonably fast to compute (so preferably non-iterative) because this operation could possibly be carried out thousands of times during the curve fitting process.

What I Know So Far:

• I know that a global minimum value must exist. The distance between $(x_{n}, y_{n})$ and $(x, f(x))$ can be modeled by $\sqrt{(x_n-x)^2 + (y_n-f(x))^2}$, which I believe (from what I've read) is coercive, which implies the existence of a global minimum.
• The minimum value must be less than or equal to $|y_n - f(x_n)|$, assuming $f(x_n)$ is defined.

My Plea:

Can someone at least point me in a direction?

• A closed-form exact solution for an arbitrary function $f$? No such thing! – Robert Israel Aug 19 '15 at 4:54
• Not even if the minimum is guaranteed to exist? – Mr. Nielsen Aug 19 '15 at 5:00

Suppose $f(x)$ is a polynomial of degree $d$ with rational coefficients, and for convenience take $(x_n, y_n) = (0,0)$. You want to minimize $g(x) = x^2 + f(x)^2$ (the square of your distance): the minimum occurs at a root of $g'(x) = 2 x + 2 f(x) f'(x)$, a polynomial of degree $2d-1$ which will usually be irreducible over the rationals, so the root would be an algebraic number of degree $2d-1$. You then evaluate $g(x)$ at such a root: the result will again be likely to be algebraic of degree $2d-1$. So unless you can solve polynomials of high degree in "closed form", you're not going to be able to do this exactly.

For example, try $f(x) = x^3 + x + 1$. The minimum occurs at a root of $6\,{x}^{5}+8\,{x}^{3}+6\,{x}^{2}+4\,x+2$, and the minimum value is a root of ${z}^{5}-2\,{z}^{4}+\frac {31}{27}{z}^{3}+{\frac {2}{27}} z -\frac{1}{27}$. That polynomial has Galois group $S_5$, so no solution in radicals.

• Would it change anything if $f(x)$ was approximated by many small line segments? – Mr. Nielsen Aug 19 '15 at 19:48
• Then in general you'd have to look at each segment. Each individually is easy, but a lot of them would take a lot of time. – Robert Israel Aug 19 '15 at 20:50