Standard Forms of Linear and Quadratic Programming
Linear and quadratic programming problemsLinear programsA 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 Example: A drug production problem. Quadratic programsA quadratic program (or QP, for short) is an optimization problem in the standard form above, where:
![]() for some vector Example: Projection on a polyhedron. GeometryEach constraint in an LP is a single affine inequality in the decision vector An LP is to minimize a linear function over a polyhedron. Geometrically, this means ‘‘going as far as possible in the direction Examples: Standard formsStandard inequality formAs seen here, a function ![]() for some appropriate vector Hence, a linear program can be expressed as ![]() for some appropriate vectors 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 constraintsIn LP or QP models, we can have equality constraints as well. For example, the LP ![]() where ![]() Conic formA 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 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 implementationBasic implementationConsider 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 Some do's and don'ts of CVXConsider the case when 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). |