Constraint optimisation of an objective function

Question

I have below objective function

$S = \lvert 18 - a - b \rvert + \lvert 15 - a - 2b \rvert + \lvert 11.1 - a - 3b \rvert + \lvert 7 - a - 4b \rvert + \lvert 3.4 - a - 5b \rvert + \lvert -1.5 - a - 6b \rvert$

Subject to $a + 3b = 5$

Replacing $a = 5 - 3b$, we can have the objective function as

$S \\= \lvert 18 - 5 + 3b - b \rvert + \lvert 15 - 5 + 3b - 2b \rvert + \lvert 11.1 - 5 + 3b - 3b \rvert + \lvert 7 - 5 + 3b - 4b \rvert + \lvert 3.4 - 5 + 3b - 5b \rvert + \lvert -1.5 - 5 + 3b - 6b \rvert \\ =\lvert 13 + 2b \rvert + \lvert 10 + b \rvert + \lvert 2 - b \rvert + \lvert 1.6 - 2b \rvert + \lvert -6.5 - 3b \rvert$

(excluding the constant term)

Is there any trick to proceed further to solve this optimisation without using any computer program?

One question : Does it make sense if I replace the absolute with square for each individual components of S, and then proceed with regular Derivative calculations?

Answer 1

Write $S$ as follows:

$$S = 2 \cdot \lvert b - (-6.5) \rvert + \lvert b - (-10) \rvert + \lvert b - 2 \rvert + 2 \cdot \lvert b - 0.8 \rvert + 3 \cdot \lvert b - 2.1666\ldots \rvert.$$

Now do a case analysis, based on which of the following ranges $b$ is in:

• $b \in (-\infty,-10]$,
• $b \in (-10,-6.5]$,
• $b \in (-6.5, 0.8]$,
• $b \in (0.8,2]$,
• $b \in (2,2.1666\ldots]$,
• $b \in (2.1666\ldots,+\infty)$

(Here $-10,-6.5,0.8,2,2.1666\ldots$ is a sorted list of the numbers appearing inside the absolute values.)

You can notice in each case, $S$ can be written as a linear function of $b$, since we know, for each absolute value, whether the value inside the $\lvert \cdots \rvert$ will be positive or not. Of course, minimizing a linear function of $b$ within a particular range is easy (the answer will be either the value at the left endpoint or the value at the right endpoint, depending on whether the slope of the line is positive or negative). Do that for each case, and take the smallest such point.

This can be easily done by hand.

---

The general version of this is that you have

$$S = \sum_i \beta_i \cdot |b-\gamma_i|,$$

where the $\beta_i,\gamma_i$ are known constants. The solution involves sorting the $\gamma_i$ in increasing order, dividing $\mathbb{R}$ into ranges as above, then doing a case analysis on which range $b$ is found within, and minimizing $S$ over each range.

You can also implement this on a computer, and the running time will be $O(n \log n)$, where $n$ counts the number of terms in the sum.

---

No, you cannot replace the absolute values with squares. That will change the objective function and the optimal solution to the modified objective function is likely to be different from the optimal solution to the original objective function.

Answer 2

This is a convex problem so:

1- Take the terms as $\alpha_i|b-\beta_i|$.

2-Define $f(b) = \sum_i \alpha_i|b-\beta_i|$.

3-Order those therms according to $\beta_i$.

4-Calculate $f(\beta_i)$ according to this order.

When the $f(\beta_i)$ values begin to increase, the previous $\beta_i$ corresponds to the minimum location.