Given \( M = \sum^{n}_{i=1} |a_ix - b_i| \), find \(x\) that minimizes \(M\).
The solution to the problem hinges on the following lemma:
Lemma 1:
If \(x\) minimizes M, then \(x \in \{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \} \).
Proof:
The proof comes from an observation that the curve for M is made up of segments of straight lines with sharp turns on each \(x \in \{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \} \). Why? Let's assume without losing generality that \(\{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \}\) is sorted in increasing order. Each \( (\frac{b_k}{a_k}, \frac{b_{k+1}}{a_{k+1}}) \) forms a segment on the real number line, and \(x\) can only be one of the segment at any point of time. In any segment, each \(a_ix - b_i\) will be either positive or negative and the parity will not change as long as \(x\) stays in the same segment. This means that in each segment, \(M = Ax - B\), which is a straight line. From here it is clear that if \(x\) minimizes M, it cannot be in the middle of the line segment, since moving along the downward slope will gives us even smaller M. Hence \(x\) must be on the segment ends, and hence leads to Lemma 1.
From here, we can perform a \(O(N^2)\) complete search to find \(x\).
No comments:
Post a Comment