Standard Forms and Geometry

Up | Next

Linear Programs

A linear program (or LP, for short) is an optimization problem in the standard form introduced here:
 displaystylemin_x : f_0(x) ~:~ f_i(x) le 0, ;; i=1,ldots, m ,
where the objective function f_0, and the constraint functions f_i, i=1,ldots,m, are all affine.

Since affine functions are linear plus constant, and constant terms in the objective do not matter, we can always assume that f_0 is actually linear.

Examples:

Quadratic programs

A quadratic program (or QP, for short) is an optimization problem in the standard form above, where:

  • the constraint functions f_i, i=1,ldots,m, are all affine, as in LP;

  • the objective function f_0 is quadratic convex, that is, its values can be expressed as
     f_0(x) = c^Tx + x^TQx
    for some vector c in mathbf{R}^n and Q = Q^T succeq 0 (Q is symmetric, and all of its eigenvalues is non-negative).

Geometry

Each constraint in an LP is a single affine inequality in the decision vector x. Hence, each constraint says that the decision vector x should lie in a half-space. Taken together, the constraints require that x should like in the intersection of those half-spaces, that is, a polyhedron.

The geometry of LP is to minimize a linear function over a polyhedron. The geometry of QP is to minimize a convex (bowl-shaped) quadratic function over a polyhedron.

Examples: