QBUS2310 Chap.5 Linearisation and Piecewise Objectives
Linearisation and Piecewise Objectives
Some nonlinear-looking objectives can be represented exactly by a linear model when they are finite piecewise-linear envelopes. The direction of each auxiliary inequality matters. For minimising a maximum, an epigraph variable sits above every component and the objective pushes it down.
Similar constructions handle absolute values and max-min fairness, while genuinely curved functions may require approximation rather than an exact LP. These terms let a reader confirm an epigraph reformulation still matches the original piecewise objective. Epigraph Variable is an auxiliary variable used as an upper bound on objective components. Affine Function is a linear expression plus a constant.
Piecewise Linear is built from linear pieces joined at breakpoints. Absolute Value is distance from zero, representable by two linear lower bounds in common minimisation models. Max-Min Rule is a criterion that maximises the smallest achieved performance. Linearisation is an exact reformulation or approximation using linear variables and constraints.
The epigraph reformulation above is verified as follows: The LP minimises t subject to the two lower bounds on t and the bounds on x. Its optimum is (x,t)=(1,1). Reversing either epigraph inequality would no longer model the maximum.
What this chapter covers
- 01
Epigraph reformulation
- 02
Maximum of affine functions
- 03
Sum of maxima
- 04
Absolute-value objectives
- 05
Piecewise-linear convexity
- 06
Concave maximisation
- 07
Max-min fairness
- 08
Exactness versus approximation
Linearisation and Piecewise Objectives worked example
- +1Introduce t as an upper bound on both affine expressions.
- +1Write t at least 2x-1 and t at least -x+2, together with zero at most x at most three.
- +1The minimum upper envelope occurs where the two active pieces meet: 2x-1=-x+2.
- +1Solving gives x=1 and t=1. Check endpoints to confirm their envelope values are larger.
Key terms
- Epigraph Variable
- An auxiliary variable used as an upper bound on objective components.
- Affine Function
- A linear expression plus a constant.
- Piecewise Linear
- Built from linear pieces joined at breakpoints.
- Absolute Value
- Distance from zero, representable by two linear lower bounds in common minimisation models.
- Max-Min Rule
- A criterion that maximises the smallest achieved performance.
- Linearisation
- An exact reformulation or approximation using linear variables and constraints.
Linearisation and Piecewise Objectives FAQ
Why does epigraph reformulation matter?
Epigraph Variable: An auxiliary variable used as an upper bound on objective components. Affine Function: A linear expression plus a constant. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
How can I check absolute-value objectives?
Affine Function: A linear expression plus a constant. Piecewise Linear: Built from linear pieces joined at breakpoints. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
What separates epigraph variable from affine function?
Piecewise Linear: Built from linear pieces joined at breakpoints. Absolute Value: Distance from zero, representable by two linear lower bounds in common minimisation models. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
Which error is most likely around concave maximisation?
Absolute Value: Distance from zero, representable by two linear lower bounds in common minimisation models. Max-Min Rule: A criterion that maximises the smallest achieved performance. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
How should I practise exactness versus approximation?
Max-Min Rule: A criterion that maximises the smallest achieved performance. Linearisation: An exact reformulation or approximation using linear variables and constraints. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
Exam move
Say what the auxiliary variable bounds before writing symbols. For a minimum of a maximum, it is an upper bound; for a maximum of a minimum, it is a lower bound. Rehearse the chapter method in this order: Introduce t as an upper bound on both affine expressions. Write t at least 2x-1 and t at least -x+2, together with zero at most x at most three.
The minimum upper envelope occurs where the two active pieces meet: 2x-1=-x+2. Solving gives x=1 and t=1. Check endpoints to confirm their envelope values are larger.
Working through Linearisation and Piecewise Objectives in QBUS2310? Sia is AskSia’s AI Mathematics tutor — ask any QBUS2310 Linearisation and Piecewise Objectives question and get a clear, step-by-step explanation grounded in how QBUS2310 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
