In model QP4 we developed an NLP model with an objective function consisting of squares of sums. In some cases an NLP model may be not very satisfactory, for instance when other constraints in the model make it an integer programming model, or when the model is extremely large.

In this case we can approximate the objective function by a linear one. This is a two step process: first we replace the squares by absolute values and then we reformulate the absolute values into sums of two non-negative variables. Mathematically:

sum(t, w(t)*w(t)) approx. sum(t,|w(t)|) = sum(t,wplus(t)+wminus(t))

where   w(t) = wplus(t) - wminus(t), wplus(t) >=0, wminus(t) >= 0
        |w(t)| = wplus(t) + wminus(t)
        wplus(t) * wminus(t) = 0

The last (non-linear) condition (either the plus term is zero or the min term is zero) is automatically enforced if we minimize the absolute values. So this condition does not have to specified in the model.

The resulting model is now a completely linear model which can be solved with any LP solver.