1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$... $\endgroup$ – Micah Apr 6 at 16:50
  • $\begingroup$ @Micah Can you expand? I don't quite understand how that would work. $\endgroup$ – shmth Apr 6 at 21:55
  • $\begingroup$ @shmth: Done!${}$ $\endgroup$ – Micah Apr 6 at 22:02
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.