| # Standard Forms of Linear and Quadratic Programming LP and QP > Polyhedra | Standard forms | Polyhedral Functions | Min-Cardinality | Applications 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: the objective function , and the constraint functions , , are all affine. (Since affine functions are linear plus constant, and constant terms in the objective do not matter, we can always assume that 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 , , are all affine, as in LP; the objective function is quadratic convex, that is, its values can be expressed as for some vector and ( is positive-semidefinite: it is symmetric, and everyone of its eigenvalues is non-negative). LPs are special cases of QPs, in which the matrix is zero. Example: Projection on a polyhedron. ## Geometry Each constraint in an LP is a single affine inequality in the decision vector . Hence, each constraint says that the decision vector should lie in a half-space. Taken together, the constraints require that 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 ’’, where 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: An LP in two variables. A QP in two variables. ## Standard forms ### Standard inequality form As seen here, a function is affine if and only if it can be expressed via the scalar product, as for some appropriate vector and scalar . Hence, a linear program can be expressed as for some appropriate vectors and scalars . We can use the component-wise inequality convention and put the above problem into the inequality standard form: where Similarly, for QP a standard form is ### Equality constraints In LP or QP models, we can have equality constraints as well. For example, the LP where , define the equality constraints, can be put in standard inequality form, as ### Conic form A problem of the form 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 , where 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 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 is positive semi-definite; otherwise, it will fail. ### Some do's and don'ts of CVX Consider the case when , the identity. Then . 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)`.