Minimize distance between points using equality constraints with unknown variable(s)

258 Views Asked by At

I'm looking for an approach to minimize the distance in $\|\cdot\|_2$ between a pair of unknown points $\mathbf{P}_1, \mathbf{P}_2 \in \mathbb{R}^3$ and a preferred set of points $\mathbf{R}_1, \mathbf{R}_2 \in \mathbb{R}^3$.

There is a set of equality constraints, each one involving $\mathbf{P}_1$ and/or $\mathbf{P}_2$, which together form a linear system of vector equations.

In addition, these equality constraints contain unknown scalar variables (at least one in total, likely more).

Probably the simplest case is a square non-singular system of equations (i.e. the equality constraints) and a single unknown scalar variable. In that case, the problem amounts to optimizing the value of that scalar variable, in the sense that it minimises $\sum \|\mathbf{R}_i - \mathbf{P}_i\|_2$.

Consider for example the following equality constraints:

$$\left(\begin{array}{cc} a & b\\ c & d \end{array}\right) \left(\begin{array}{c} \mathbf{P_1}\\ \mathbf{P_2} \end{array}\right) = \left(\begin{array}{c} e\mathbf{Q_1} + \lambda(\mathbf{Q_2} - \mathbf{Q_1})\\ f\mathbf{Q_2} + \lambda(\mathbf{Q_3} - \mathbf{Q_2}) \end{array}\right),$$

with

  • $a$, $b$, $c$, $d$, $e$ and $f$ known values in $\mathbb{R}$,
  • $\mathbf{P_i}$, $i \in \{1,2\}$ unknown elements of $\mathbb{R}^3$,
  • $\mathbf{Q_j}$, $j \in \{1,2,3\}$ known elements of $\mathbb{R}^3$,
  • $\lambda$ an unknown value in $\mathbb{R}$.

Other cases are underdetermined systems of equations and overdetermined ones, both of which can occur within my context.

Different aspects of the problem seem to point into different directions (e.g. least squares, normal equations for solving under-/over-determined systems, Lagrange multipliers, ...). As I'm not sure how to proceed from here, references, hints or (partial) solutions would be most welcome.


[Edit] Updated formulation of the question (removed an aspect that was previously there and has been solved below).

1

There are 1 best solutions below

9
On

Hint

So we have

$$\left(\begin{array}{cc} a & b\\ c & d \end{array}\right) \left(\begin{array}{c} \mathbf{P_1}\\ \mathbf{P_2} \end{array}\right) = \left(\begin{array}{c} e\mathbf{Q_1} + \lambda(\mathbf{Q_2} - \mathbf{Q_1})\\ f\mathbf{Q_2} + \lambda(\mathbf{Q_3} - \mathbf{Q_2}) \end{array}\right),$$

The main step is to choose a vectorization for the unknowns, for example $\left(\begin{array}{c} \mathbf{P_1}\\ \mathbf{P_2}\\\lambda \end{array}\right)$

Now try and rewrite your expression to one involving the vectorized unknowns with matrix multiplication and addition.


additional hint scalar multiplication $s{\bf A}$ is "syntactic sugar" for $(s{\bf I}){\bf A}$, in other words there is a hidden identity matrix involved.

If $3$ dimensional vectors we can write $$\left[\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}\right] \cdot s=\left[\begin{array}{ccc}s&0&0\\0&s&0\\0&0&s\end{array}\right]$$ but in general we want a Kronecker product : ${\bf I_N}\otimes s$.

It means inserting copies of $s$ into each element of $\bf I_N$ and multiplying with the scalar there.


I can solve it more completely later if you want me to, but it is a good exercise to try do the following procedure oneself.