Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Standard Forms of Linear and Quadratic Programming

  • Linear and quadratic programing problems

  • Geometry

  • Standard forms

  • CVX implementation; some do's and don'ts

Linear and quadratic programming problems

Linear programs

A linear program (or LP, for short) is an optimization problem with linear objective and affine inequality constraints. In the standard form introduced here:

displaystylemin_x : f_0(x) ~:~ f_i(x) le 0, ;; i=1,ldots, m ,

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.)

Example: A drug production problem.

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 positive-semidefinite: it is symmetric, and everyone of its eigenvalues is non-negative). LPs are special cases of QPs, in which the matrix Q is zero.

Example: Projection on a polyhedron.

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.

An LP is to minimize a linear function over a polyhedron. Geometrically, this means ‘‘going as far as possible in the direction -c’’, where c is the vector that defines the (linear) objective function. The geometry of a QP is to minimize a convex (bowl-shaped) quadratic function over a polyhedron.

Examples:

Standard forms

Standard 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 ,

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. We call this representation a ‘‘conic’’ form. 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 convex 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.

CVX implementation

Basic implementation

Consider the QP with equality and inequality constraints

displaystylemin_x : c^Tx+x^TQx ~:~ Ax le b , ;; Cx = d .

In CVX, we use component-wise inequalities to specify the affine inequality constraints. Note that equality constraints need to be coded with the double inequality sign ==.

CVX implementation
cvx_begin
   variable x(n,1)
   minimize( c'*x+x'*Q*x )
   subject to
        A*x <= b;
        Cx == d;
cvx_end
pstar = cvx_optval; % optimal value of the problem

CVX will only solve the problem if Q is positive semi-definite; otherwise, it will fail.

Some do's and don'ts of CVX

Consider the case when Q = I, the identity. Then x^TQx = x^Tx = |x|_2^2. We can be tempted to write the above problem in CVX as follows.

A wrong CVX implementation
cvx_begin
   variable x(n,1)
   minimize( c'*x+norm(x,2)^2 )
   subject to
        A*x <= b; Cx == d;
cvx_end

However, CVX will fail with this expression of the problem, as it cannot recognize the convexity of the squared norm function. The reason is that the square of a convex function is only convex if that function is non-negative. To square a function that is non-negative, we use the square_pos function.

CVX implementation
cvx_begin
   variable x(n,1)
   minimize( c'*x+square_pos(norm(x,2)) )
   subject to
        A*x <= b; Cx == d;
cvx_end

Alternatively, we can use the function sum_square, replacing the last term in the objective in the above with sum_square(x).