# How to minimize $\| x \mathrm a - \mathrm b \|_1$ without using linear programming?

The following question is a generalization of a question asked earlier today:

Given vectors $$\mathrm a, \mathrm b \in \mathbb R^n$$, can one solve the following minimization problem in $$x \in \mathbb R$$

$$\begin{array}{ll} \text{minimize} & \| x \mathrm a - \mathrm b \|_1\end{array}$$

without using linear programming? If so, how?

If $$\mathrm a = 1_n$$, one can use the median. If $$\mathrm a = \begin{bmatrix} 1 & 2 & \cdots & n\end{bmatrix}^\top$$, Siong showed that one can also use the median. What can one do in the general case?

• Generate a list of candidate values $b_i/a_i$, sort them, and use convexity to do a binary search for the norm-minimizing one? I'm not sure whether this counts as "without using linear programming," but unless I'm missing something it runs in time $n \log n$... – Micah Apr 6 at 16:50
• @Micah Can you expand? I don't quite understand how that would work. – shmth Apr 6 at 21:55
• @shmth: Done!${}$ – Micah Apr 6 at 22:02

I'm not sure if this counts as "without using linear programming", but it's at least relatively fast (it has runtime $$O(n \log n)$$).

Let $$f$$ be the objective function. Notice that $$f(x)=\sum_{i=1}^n |a_i x - b_i|$$ is piecewise linear, and also (non-strictly) convex, and so the slope of $$f$$ is a (non-strictly) increasing function. The minimum of $$f$$ will occur either on an interval where the slope is zero, or at a point where it switches from positive to negative. We can proceed as follows.

1) Compute all the points of nonlinearity $$b_i/a_i$$ ($$O(n)$$) and sort them ($$O(n \log n)$$). Call the sorted values $$x_1,x_2\dots,x_n$$.

2) Let $$k=\left\lfloor\frac{x}{2}\right\rfloor$$ and compute the slope of $$f$$ on the interval of linearity $$[x_k,x_{k+1}]$$ ($$O(n)$$). If this slope is positive, we're to the right of the minimum; if it's negative, we're to the left of the minimum.

3) Perform a binary search, doing step 2) $$\log n$$ more times with different values of $$k$$ ($$O(n\log n)$$). Eventually you will find some $$x_\ell$$ such that either $$f$$ has slope zero on $$[x_\ell,x_{\ell+1}]$$, or the slope is negative on $$[x_{\ell-1},x_\ell]$$ but positive on $$[x_\ell,x_{\ell+1}]$$. Then $$f(x_\ell)$$ is your minimum value.

If you walked through adjacent values of $$x_k$$ instead of doing a binary search, you would essentially be minimizing $$f$$ via the simplex method, which is why I'm not totally sure this isn't linear programming. But it does seem like the binary search essentially exploits the one-dimensionality of the problem.