# Minimum distance problem: Optimize function

I have a function of $4$ variables: (distance function) $$d(x,x_1,y,y_1)=(x−x_1)^2+(y−y_1)^2$$ subject to $2$ constraints:

1. $\frac{(x+h)^2}{a^2}+\frac{(y+k)^2}{b^2}= 1$

2. $\frac{(x_1+h_1)^2}{a_1^2}+\frac{(y_1+k_1)^2}{b_1^2}= 1$

Using Lagrange multipliers, what are the values of $x$, $x_1$, $y$ and $y_1$ in terms of $h$, $k$, $a$, $b$, $h_1$, $k_1$, $a_1$, and $b_1$?

-
I typset your equations in TeX to make them easier to read - can you check I didn't introduce any mistakes? Mainly in the definition of $d$, you had (x-x1)2, so I assumed the 2 was a ^2. – Matthew Pressland Sep 10 '12 at 12:40
No it is all as it is meant to be. What is TeX? Can I download it from somewhere? Thanks by the way:) – David Hoffman Sep 10 '12 at 12:42
@ David Hoffman: in optimization problems, constraints are either equalities or inequalities. Your "constraints" are neither. You may want to take a look at lyx.org – Rod Carvalho Sep 10 '12 at 12:44
Both of them are equal to 1. Sorry. – David Hoffman Sep 10 '12 at 12:46
@ David Hoffman: shouldn't the variables be only $x$ and $y$, and the rest be mere parameters? Also, do you have numerical values for the parameters? – Rod Carvalho Sep 10 '12 at 12:50

I don't like the notation you're using, so I will use a different one. Consider the ellipses defined below

$$\mathcal{E}_1 := \displaystyle\left\{ (x_1, y_1) \in \mathbb{R}^2 : \left(\frac{ x_1 - x_{10}}{a_1}\right)^2 + \left(\frac{ y_1 - y_{10}}{b_1}\right)^2 = 1 \right\}$$

$$\mathcal{E}_2 := \displaystyle\left\{ (x_2, y_2) \in \mathbb{R}^2 : \left(\frac{ x_2 - x_{20}}{a_2}\right)^2 + \left(\frac{ y_2 - y_{20}}{b_2}\right)^2 = 1 \right\}$$

Note that we have 4 unknowns and 2 constraints. Hence, we have 2 degrees of freedom. It would be neater to solve the optimization problem in 2 variables only. But, how?

I introduce functions $\gamma_1, \gamma_2 : [0, 2 \pi] \to \mathbb{R}^2$ defined by

$$\gamma_1 (\theta_1) = \left[\begin{array}{c} x_{10} + a_1 \cos(\theta_1)\\ y_{10} + b_1 \sin(\theta_1)\end{array}\right]$$

$$\gamma_2 (\theta_2) = \left[\begin{array}{c} x_{20} + a_2 \cos(\theta_2)\\ y_{20} + b_2 \sin(\theta_2)\end{array}\right]$$

In other words, I have parametrized the ellipses. Since you want to minimize the distance between the elipses, we have the following optimization problem

$$\displaystyle\min_{(\theta_1, \theta_2)} \| \gamma_1 (\theta_1) - \gamma_2 (\theta_2)\|_2^2 \quad{} \text{subject to} \quad{} (\theta_1, \theta_2) \in [0, 2 \pi]^2$$

which you can solve using partial derivatives. No need for Lagrange multipliers.

-
Thank you very much. This is really good. How about this: I have ellipse E_1: (x-3)^2/2^2+(y-2)^2/1=1 and ellipse E_2: (x-1)^2/1+(y+2)^2/2^2=1. How would you find the minimum distance between these two ellipses? – David Hoffman Sep 10 '12 at 19:19
@ David Hoffman: Have you had any multivariable calculus? Just take the partial derivatives of the objective function with respect to $\theta_1$ and $\theta_2$, see where they vanish, find the minimizers, and finally evaluate the objective function at the minimizers to obtain the minimum distance. – Rod Carvalho Sep 10 '12 at 19:24
So you're saying that I would have to minimize (a_1cos(t)+ x_1-a_2cos(s)-x_2)^2+(b_1sin(t)+y_1-b_2sin(s)-y_2)^2? – David Hoffman Sep 11 '12 at 13:07
@ David Hoffman: Pretty much. But you used $x_i$ and $y_i$ in your expression, instead of $x_{i0}$ and $y_{i0}$. – Rod Carvalho Sep 11 '12 at 13:19
I could not solve this symbolically. I managed to express (t) in terms of (s), which was a polynomial of 8th degree. When I plugged it into the other partial derivative equation, I nor a computer program designated for such stuff could not solve it. – David Hoffman Sep 19 '12 at 9:39