Given points $(x_i,y_i),i=1,2,\cdots,N$ and transform $v_i=x_i+ky_i(i=1,2,\cdots,N)$, where $k\in\mathbb R$ is unknown.
Our goal is to find proper $k^*$ to minimize the range of $v$, which means $$k^*=\text{argmin}\max_{i,j}\|v_i-v_j\|$$
The function $\max_{i,j}\|v_i-v_j\|$ are piecewise for different $k$ may be discussed in different cases, which may be complicated for programming.
I notice that if to minimize variance $\frac{1}{N-1}\sum_{i=1}^N(v_i-\bar v)^2$ instead of range $\max_{i,j}\|v_i-v_j\|$, the target function is quadratic, then the analytical solution can be obtained as $$k^*=-\frac{\text{Cov}(x_i,y_i)}{\text{Var}(y_i)}$$
However, it does not make sense, because the variance is a lower bound of the range.
In my study, the approximate solution by minimizing the upper bound of the function $\max_{i,j}\|v_i-v_j\|$ is allowed. When approximate is allowed, is simple analytical expression can be obtained?
Is there an effective way to solve this problem? I would really appreciate any help.
You can solve the problem via linear programming as follows. Let $z$ represent the range. The problem is to minimize $z$ subject to \begin{align} z &\ge v_i - v_j &&\text{for all $i,j$} \tag 1 \end{align} Equivalently, minimize $z$ subject to \begin{align} z &\ge x_i - x_j + k (y_i - y_j) &&\text{for all $i,j$} \tag 2 \end{align}