Minimal distance between a point and a manifold M (M is the intersection of a ball and an ellipsoid) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T23:22:11Z http://mathoverflow.net/feeds/question/54798 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54798/minimal-distance-between-a-point-and-a-manifold-m-m-is-the-intersection-of-a-bal Minimal distance between a point and a manifold M (M is the intersection of a ball and an ellipsoid) Bernhard Boehmler 2011-02-08T17:59:51Z 2011-02-09T12:51:03Z <p>Hi,</p> <p>I have an elementary question concerning an extremal problem:</p> <p>Given a manifold $M$:={$(x_1, x_2, x_3)$ | $x_1^2 + x_2^2 + x_3^2 = c$ and $\frac{x_1^2}{a_1^2} + \frac{x_2^2}{a_2^2} + \frac{x_3^2}{a_3^2}= d$ and max($a_1, a_2, a_3$) $> \sqrt{c} >$ min($a_1, a_2, a_3$) } consider an arbitrary point P($\tilde{x}_1, \tilde{x}_2, \tilde{x}_3$) with $M \cap P = \emptyset$.</p> <p>Now I'm interested in the minimal distance between P and M. My idea was to use Lagrange:</p> <p>Minimize f:= $||(\tilde{x}_1, \tilde{x}_2, \tilde{x}_3)-(x_1, x_2, x_3)||^2$ with the following boundary conditions: </p> <p>1) $\varphi_1 := x_1^2 + x_2^2 + x_3^2 - c =0$</p> <p>2) $\varphi_2 := \frac{x_1^2}{a_1^2} + \frac{x_2^2}{a_2^2} + \frac{x_3^2}{a_3^2} - d = 0$</p> <p>=> $\Lambda (x_1, x_2, x_3, \lambda_1, \lambda_2)$ = f + $\lambda_1 \varphi_1 + \lambda_2 \varphi_2$.</p> <p>Differentiating yields:</p> <p>i) $2x_1 - 2\tilde{x_1} + 2\lambda_1 x_1 + 2 \lambda_2 \frac{x_1^2}{a_1^2} = 0$</p> <p>ii) $2x_2 - 2\tilde{x_2} + 2\lambda_1 x_2 + 2 \lambda_2 \frac{x_2^2}{a_2^2} = 0$</p> <p>iii) $2x_3 - 2\tilde{x_3} +2\lambda_1 x_3 + 2 \lambda_2 \frac{x_3^2}{a_3^2} = 0$</p> <p>iv) $x_1^2 + x_2^2 + x_3^2 = c$ </p> <p>v) $\frac{x_1^2}{a_1^2} + \frac{x_2^2}{a_2^2} + \frac{x_3^2}{a_3^2}= d$</p> <p>vi) max($a_1, a_2, a_3$) $> \sqrt{c} >$ min($a_1, a_2, a_3$)</p> <p>vii) $P \cap M$ = $\emptyset$</p> <p>Rearranging i)-iii) yields</p> <p>$x_i\cdot (1+\lambda_1 + \frac{\lambda_2}{a_i^2})=\tilde{x_i}$ , thus $x_i = \frac{\tilde{x_i}}{1+\lambda_1 + \frac{\lambda_2}{a_i^2}}$</p> <p>Putting this into iv) and v) you get $\sum\limits_{i=1}^3 (\frac{\tilde{x_i}}{1+\lambda_1 + \frac{\lambda_2}{a_i^2}})^2 = c$ and $\sum\limits_{i=1}^{3} ({\frac{\frac{\tilde{x_i}}{a_i^2}}{1+\lambda_1 + \frac{\lambda_2}{a_i^2} } })^2 = d$</p> <p>Now I wish to solve this for the variables $\lambda_1, \lambda_2, x_1, x_2, x_3$, whereat these variables depend on $a_1, a_2, a_3, c, d, \tilde{x}_1, \tilde{x}_2$ and $\tilde{x}_3$.</p> <p>I had no idea how to calculate an exact solution, so I wanted to use Newton's Method in order to calculate $\lambda_1$ and $\lambda_2$, but I unfortunately did not succeed in achieving the minimum of f, because there are many different solutions for the $\lambda_i$ and I don't know how I can be sure that Newton's Method found the minimal distance between P and M.</p> http://mathoverflow.net/questions/54798/minimal-distance-between-a-point-and-a-manifold-m-m-is-the-intersection-of-a-bal/54834#54834 Answer by robot for Minimal distance between a point and a manifold M (M is the intersection of a ball and an ellipsoid) robot 2011-02-08T23:46:15Z 2011-02-09T12:51:03Z <p>Lagrange method is based on a fact that extrema can occur only at points where the gradient of $f$ is a linear combination of gradients of the constraints -- i.e. at points where $\{\nabla f,\nabla g_1, \nabla g_2 \}$ is linearly dependent with coefficient in front of $\nabla f$ nontrivial. If the constraints are independent ($\nabla g_1 \neq c \nabla g_2$) then you can test this linear depenedence by determinant of the matrix $\begin{pmatrix} \partial_x f &amp;\partial_y f &amp;\partial_z f \\ \partial_x g_1 &amp;\partial_y g_1 &amp;\partial_z g_1 \\ \partial_x g_2 &amp;\partial_y g_2 &amp;\partial_z g_2\end{pmatrix}$. This gives you the third equations to your constaints $g_1=0$, $g_2=0$. This may be more amenable to numerical solutions. I've tried solving the resulting equations in Maple and it did produce a result, but it is too long to display. For example $z$ variable is a solution of a polynomial of degree 8 with coefficients being polynomial expressions of degree up to 16. One can go further and try to find Groebner basis for this system of polynomial equations, but I don't think that it'll lead to anything more useful than direct numerical solution.</p>