find points close to targets, but at least min_dist apart

Question

Given a number of target points $t_1,\dots,t_n\in\mathbb{R}$, I would like to find matching $x_i$ such that they are as close as possible to their $t_i$ partner, but at least $a>0$ apart. In math: $$ \frac{1}{2}\sum_i (x_i - t_i)^2 \to \min_x,\\ (x_i - x_j)^2 \ge a^2 \quad \forall i,j. $$ How to best solve this? (Solutions that are easily implementable in Python preferred.)

Answer 1

One idea would be to convert it to a problem with non-negativity constraints. For this, make sure that the $x_i$ are sorted and use the variables $$ \begin{split} \tilde{x}_0 &= x_0 - x_0^{\text{min}}\\ d_i &= x_i - x_{i-1} - a \end{split} $$ and note that $$ \frac{1}{2}\sum_i (x_i - t_i)^2 = \frac{1}{2} \sum_i \left(\tilde{x}_0 + \sum_{j=1}^i d_j - (t_i - i a - x_0^{\text{min}})\right)^2. $$ This can be treated with a non-negative least-squares solver (e.g., from scipy); the system matrix $A$ will be lower triangular.