Looking for algorithm (or at least name) for this optimization problem
If I understand your problem correctly, we can formulate it like so: given pairs $(\alpha_k,\beta_k)$ and $\Delta_0$, find $s &gt; 0$ such that $\max_k (s\alpha_k + \beta_k) = \Delta_0$. Here is one way to solve this (this algorithm can be made more efficient). Go over all possible $k$. For each $k$, find the value of $s$ such that $s\alpha_k + \beta_k = \Delta_0$ (namely $s = (\Delta_0 - \beta_k)/\alpha_k$), check that it's positive, and check that for all $l \leq k$, $s\alpha_l + \beta_l \leq \Delta_0$. This runs in $O(m^2)$, where $m$ is the number of pairs (in your case, $m = n(n-1)$); you can probably get the running time down to quasilinear. Your case is more structured, so you may be able to get an even faster algorithm.