Formulate a convex minimization without constraints

Question

I am totally desperate, because I am not able to solve following task. I really appreciate any help. I've already tried to solve that for hours....

Be $G_1 = \{a+tv \mid t∈\mathbb{R}\}$ and $G_2 = \{b+tw \mid t∈\mathbb{R}\}$ two lines in $\mathbb{R}^n$ given by two points $a,b$ and direction vectors $v,w$. Find two points $m_1∈G_1$ and $m_2∈G_2$, so that the euclidean distance between them is minimal.

Formulate this problem as a convex minimization problem without constraints.and solve it afterwards.

Thank you in advance.

Answer 1

Calling

$$ f(t_{1},t_{2})=\left\Vert a+t_{1}v-(b+t_{2})\right\Vert ^{2}=\left\Vert a-b\right\Vert ^{2}+t_{1}^{2}\left\Vert v\right\Vert ^{2}+t_{2}^{2}\left\Vert w\right\Vert ^{2}-2t_{1}t_{2}\left\langle v,w\right\rangle +2t_{1}\left\langle v,a-b\right\rangle -2t_{2}\left\langle w,a-b\right\rangle $$

we have

$$ \nabla f(t_{1},t_{2})=\left(\begin{array}{c} 2t_{1}\left\Vert v_{1}\right\Vert ^{2}-2t_{2}\left\langle v,w\right\rangle +2\left\langle v,a-b\right\rangle \\ 2t_{2}\left\Vert w\right\Vert ^{2}-2t_{1}\left\langle v,w\right\rangle -2\left\langle w,a-b\right\rangle \end{array}\right)=\left(\begin{array}{c} 0\\ 0 \end{array}\right) $$

and solving for $t_{1},t_{2}$ we obtain $t_{1}^{*},t_{2}^{*}$ such that $d=\sqrt{f(t_{1}^{*},t_{2}^{*})}$

Answer 2

The optimization problem is \begin{equation} \begin{aligned}\label{e1} \min_{m_1\in G_1,m_2\in G_2} \|m_1-m_2\|^2. \end{aligned} \end{equation}

Since $m_1\in G_1 \iff m_1 = a+tv$ for some $t$ and $m_2 \in G_2 \iff m_2 = b+sw$ for some $s$, we see previous optimization problem is equivalent to \begin{equation} \begin{aligned} \min_{s,t} \|a+tv - (b+sw)\|^2. \end{aligned} \end{equation}

This is an unconstrained convex optimization problem. We aim to minimize $$f(s,t) = \|a+tv - (b+sw)\|^2.$$

The derivative is $$ \nabla f(s,t) =\begin{bmatrix} 2(a+tv - (b+sw))\cdot v\\ -2(a+tv - (b+sw))\cdot w \end{bmatrix},$$ where $\cdot$ is the dot product.

Set it to zero gives the value of $t$ and $s$. Now use $m_1 =a+tv$ and $ m_2 = b+sw$ to get back the points. Give some special care when $v=w$ or $v = -w$.