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.)
the constraint functions , , are all affine, as in LP;
the objective function is quadratic convex, that is, its values can be expressed as
Example: Projection on 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.
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:
Similarly, for QP a standard form is
where , define the equality constraints, can be put in standard inequality form, as
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.
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.
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).