# Optimizing the solution of an underdeterminate system

Given a $3 \times 4$ matrix $M$ with the following structure,

$$M = \left(\begin{array}{cccc}a & b & 0 &0\\ c & d &e & f\\ 0 & 0 & g & h\end{array}\right),$$

I'm aiming to optimize the position of 4 points $\mathbf{P_k}$ in $\mathbb{R}^2$, such that

$$M \left(\begin{array}{c}P_{1x} \\ P_{2x} \\ P_{3x} \\ P_{4x}\end{array}\right) = \left(\begin{array}{c}A_x\\ B_x \\ C_x\end{array}\right)$$

and

$$M \left(\begin{array}{c}P_{1y} \\ P_{2y} \\ P_{3y} \\ P_{4y}\end{array}\right) = \left(\begin{array}{c}A_y\\ B_y \\ C_y\end{array}\right),$$

where $\mathbf{P_k}$ has coordinates $(P_{kx},P_{ky})$, and $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$ are known values, of course also in $\mathbb{R}^2$.

In vector form, the system can be written as

$$M \left(\begin{array}{c}\mathbf{P_1} \\ \mathbf{P_2} \\ \mathbf{P_3} \\ \mathbf{P_4}\end{array}\right) = \left(\begin{array}{c}\mathbf{A}\\ \mathbf{B} \\ \mathbf{C}\end{array}\right).$$

Clearly, the system is underdetermined with 4 unknowns and only 3 equations. In general, the rank of $M$ is $\mathcal{R}(M) = 3$ (it's an assumption I can make within the context of the problem, I'll leave out the details), therefore the kernel of $M$ is one-dimensional, i.e. $\mathcal{N}(M) = 1$.

Now, in addition to $M$, I'd like the points $\mathbf{P_k}$ to be close together. That is a bit of a vague condition, but perhaps I can state it such that the summed (squared) distance between all points is within a certain range, say

$$m < \|\mathbf{P_1}-\mathbf{P_2}\|_2 + \|\mathbf{P_2}-\mathbf{P_3}\|_2 + \|\mathbf{P_3}-\mathbf{P_4}\|_2 + \|\mathbf{P_4}-\mathbf{P_1}\|_2 < n,$$

with $m,n \in \mathbb{R}$ indicating the range. In other words, I don't necessarily want to minimize this summed (squared) distance — e.g. all points overlapping, resulting in a summed (squared distance) of $0$, is not acceptable (so $m > 0$).

I'm a bit lost with regard to finding a suitable method to approach this problem. Quadratic programming seems likely, maybe re-formulating the problem using KKT conditions... Any hints or references would be most welcome.

Also, since the problem is geometrical in nature (points in $\mathbb{R}^2$), I was wondering how to visualise the space of possible solutions. Given that $\mathcal{N}(M) = 1$, we're basically looking for the (in some sense) optimal position on a line embedded in $\mathbb{R}^4$ (for both $x$ and $y$ individually I suppose, as we still have a vector degree of freedom left).

A possible formulation is a Second Order Cone Problem (SOCP), which you can easily enter into and solve in a convex optimization system, such as CVX (MATLAB) or CVXPY (Python). This formulation minimnizes the maximum distance between your points, subject to satisfying your linear equalities.

The objective is to minimize t. The constraints are:

norm(P1 - P2) $\le t$

norm(P1 - P3) $\le t$

norm(P1 - P4) $\le t$

norm(P2 - P3) $\le t$

norm(P2 - P4) $\le t$

norm(P3 - P4) $\le t$

The optimization (decision) variables are t, P1, P2, P3, P4.

BTW, in your discussion, the only way m can = 0 is if P1 = P2 = P3 = P4 is a feasible solution (satisfies your linear equalities).