This unit develops a foundational modeling technique within linear programming: exact linear formulations of absolute deviations and minimax objectives.
Motivation
A solver can optimize only the model it is given. Before choosing a pivot rule, we must decide what a variable means and whether an inequality expresses the decision maker's intent. Suppose one setting is to approximate several measurements. Minimizing the largest error protects the worst observation; minimizing the sum of errors measures a different trade-off. Neither objective looks linear because errors contain absolute values and a maximum. Introducing auxiliary variables makes each problem a linear program (LP), provided the inequalities point in the right direction.
The point of a formulation is equivalence. An auxiliary variable may have many feasible values for the same original decision, so equality of individual feasible points is not the appropriate test. Instead, check that every original decision can be extended to the new variables and that optimizing over those extensions gives exactly the original objective.
Definitions
Definition 20.1.1
(Residuals and epigraphs)
Let be a nonempty polyhedron; further affine equalities and variable bounds may be included. For a finite number of affine residuals and weights , the weighted absolute-deviation problem is
An epigraph of a real-valued function on is the set of pairs with and . For a finite family of affine functions , the condition is exactly the collection for every .
Here the objective is bounded below by zero, and the LP attainment theorem ensures that the nonempty feasible LP attains its finite optimum. We retain infimum notation to make the value comparison explicit. We treat as free unless its bounds are explicitly stated. In the transformed LP every residual is represented by an auxiliary variable with and . These two inequalities already imply ; writing that bound separately is harmless but redundant.
Theorem/proposition
Theorem 20.1.2
(Exact formulation and recovery)
For nonnegative weights , the deviation problem has the same infimum as the LP
If either problem attains its infimum, so does the other. The -part of any optimal LP solution is optimal for the original problem. If , every optimal LP solution satisfies ; for this equality need not hold, though one may choose it.
Similarly, minimizing is equivalent to minimizing subject to and for all . This is a finite LP, even when is unbounded or free. The feasible set need not itself be bounded.
Proof sketch or proof idea
Fix any . The two inequalities for say precisely that . Thus the choice is feasible and minimizes for that fixed . Since all weights are nonnegative, every extension has objective at least the original deviation objective, and this particular extension attains it. Taking infima over proves equality of values. If the original has an optimizer, extend it by these absolute values; if the LP has an optimizer, comparison with all such extensions shows that its is optimal for the original. For a strictly positive weight, a strict surplus in could be reduced and would improve the LP objective, contradicting optimality. Zero weights do not give this strict improvement.
For the worst-case model, is at least every one of the signed residuals if and only if it is at least their maximum, which equals . The same fixed- comparison proves equivalence and optimizer recovery. This proof does not require differentiability or a unique solution.
Proof X-ray
Why an inequality can represent an equality at the optimum
The inequalities only give lower bounds on at a feasible point. Minimization with a positive coefficient is the separate reason that the lower bound is tight at an optimum. The proof compares feasible extensions for each fixed ; it is not a claim that every feasible auxiliary variable equals an absolute value. Always check the sign of the coefficient and whether the variable is constrained elsewhere before using this argument.
Worked examples
Worked example 20.1.3
(One setting for three measurements)
Choose a real setting for target values . To minimize the total absolute error, solve
For the objective after eliminating is ; on it is ; on it is ; and for it is . These expressions agree at the breakpoints. The minimum is at , with . This is the median, not the mean .
For the worst error, minimize subject to and . The endpoints alone imply . At all three errors are at most , attaining this lower bound. Hence the minimum worst error is , with setting . The middle measurement affects the total-error calculation but does not change this worst-case solution.
Worked example 20.1.4
(A coupled resource decision and a certificate)
Let , , and minimize the largest shortfall from targets 3 and 3, allowing oversupply to count as deviation:
Adding the two inequalities gives , so . The feasible choice attains the bound. The calculation proves global optimality without assuming which constraints are active at an unknown solution. If oversupply should not be penalized, the correct shortfall is , a different model; include and the shortfall inequalities.
Common mistakes and subtle points
Counterexample mode
A negative weight reverses the incentive
Consider minimizing with fixed. Its value is zero. Replacing by with and gives over , which is unbounded below. The inequalities describe the epigraph, but minimizing a negative multiple rewards an artificial surplus. Likewise, maximizing under these lower bounds does not model maximizing . A nonconvex equality or a discrete formulation may be needed in other contexts.
A constraint is represented exactly by for fixed . In contrast, for is the disjunction or ; enforcing both is impossible, and replacing it by imposes no restriction on at all, since can always be chosen large enough. Epigraph formulations must be checked in context.
Quick check
If a zero-weight residual has value , may its auxiliary variable equal in an optimal LP solution? Yes, provided all other constraints and objective terms are satisfied: its epigraph constraints only require . One can replace it by without changing the objective in this formulation.
Exercises
Quick check
(Minimize over real . Give the minimizer and its value, and write the LP.)
Solution · Answer
Use , , , and , and minimize . For the original objective is ; for it is ; for it is . It decreases up to and increases thereafter, so the unique minimizer is and the value is .
Quick check
(Minimize subject to . Prove the answer by a bound and a feasible point.)
Solution · Answer
Since , the second error is . At , the two errors are and , so the minimum is . The lower bound and feasible choice establish optimality, independent of any drawing.
Quick check
(A proposed model for minimizes subject only to . Find its value and explain the repair.)
Solution · Answer
The proposed LP has at its optimum and value at , whereas the true minimum is at . Add ; both signs are needed. The resulting smallest feasible is on the given interval.