Standard form

Definition: Standard form

An optimization problem is in standard form if it is of the form for some matrix , vector and vector .

An immediate observation is that problems of standard form are linear; we simply choose the inequality matrix as , the inequality vector as , the equality matrix as and the equality vector as . However, the implication goes both ways.

The idea is that free variables can be represented as differences between nonnegative variables, and that inequality constraints can be replaced by equality constraints where we add a so-called slack variable, "gapping" the distance in the inequality.

Theorem: Standard form

Any linear optimization problem is equivalent to a problem in standard form.

Proof:
Consider a linear optimization problem For each variable , add a corresponding variable . Whenever is not a constraint, replace with two variables and replace all occurences of with . This is equivalent to having a free variable since the difference is free.

For each inequality constraint, add a so called slack variable and rewrite the inequality constraint as . This is equivalent to the inequality constraint since .

Remark

Note that we do not restrict ourselves by further assuming that . Since we only consider equality constraints, whenever some constraint can be written as a linear combination of other constraints, the constraint is always implied (or causes a contradiction).

Remark

It follows directly that every linear optimization problem is equivalent to a problem of the form This form is sometimes called the canonical form.