Other Standard Forms

Up | Back

Inequality form

As seen here, a function f : mathbf{R}^n rightarrow mathbf{R} is affine if and only if it can be expressed via the scalar product, as
 f(x) = a^Tx - b
for some appropriate vector a and scalar b.

Hence, a linear program can be expressed as
 displaystylemin_x : c^Tx ~:~ a_i^Tx le b_i , ;; i=1,ldots, m ,
for some appropriate vectors c,a_1,ldots,a_m in mathbf{R}^n and scalars b_1,ldots,b_m in mathbf{R}.

We can use the component-wise inequality convention and put the above problem into the inequality standard form:
 displaystylemin_x : c^Tx ~:~ Ax le b ,
where
 A := left( begin{array}{c} a_1^T  vdots  a_m^T end{array}right) in mathbf{R}^{m times n}, ;; b = left( begin{array}{c} b_1  vdots  b_m end{array}right) in mathbf{R}^{m}.
Similarly, for QP a standard form is
 displaystylemin_x : c^Tx + x^TQx ~:~ Ax le b ,

QPs with equality constraints

In LP or QP models, we can have equality constraints as well. For example, the LP
 displaystylemin_x : c^Tx ~:~ Ax le b , ;; Cx = d,
where C in mathbf{R}^{p times n}, d in mathbf{R}^p define the equality constraints, can be put in standard inequality form, as
 displaystylemin_x : c^Tx ~:~ Ax le b , ;; Cx le d, ;; -Cx le -d.

Conic form

A problem of the form
 displaystylemin_x : c^Tx ~:~ Ax = b, ;; x ge 0
is an LP. Conversely, any LP can be put in the above form (Proof). A similar result holds for QP. (The reason of the term ‘‘conic’’ comes from the fact that the above problem is part of a more general class known as conic problems, in which the sign constraints on the variables are replaced with x in mathbf{K}, where mathbf{K} is a cone.)

The above form is useful to develop theory and algorithms for LP, as it puts all the ‘‘data’’ of the problem into the linear objective and the linear equality constraints, while the inequalities have a very simple, data-independent structure.