| # Polyhedral Functions LP and QP > Polyhedra | Standard forms | Polyhedral Functions | Min-Cardinality | Applications Polyhedral functions: definition and examples Minimization via LP CVX implementation ## Definition and examples ### Definition We say that a function is polyhedral if its epigraph is a polyhedron. That is, a function is polyhedral if and only if the epigraph can be expressed as a polyhedron: there exist a matrix and a vector such that ### Maxima of affine functions Polyhedral functions include in particular, functions that can be expressed as a maximum of a finite number of affine functions: where , , . Indeed, the epigraph of : can be expressed as the polyhedron Example: The -norm function, with values , is polyhedral, as it can be written as the maximum of affine functions: ### Sums of maxima of affine functions Polyhedral functions include more general functions. For example, a function that can be expressed as a sum of functions themselves expressed as maxima of affine functions: for appropriate vectors and scalars , is polyhedral. Indeed, the condition is equivalent to the existence of a vector such that Hence, is the projection (on the space of -variables) of a polyhedron, which is itself a polyhedron. Note however that representing this polyhedron in terms of a set of affine inequalities involving only, is complicated. Example: The -norm function, with values , is polyhedral, as it can be written as the sum of maxima of affine functions: ## Minimization of Polyhedral Functions Using LPs, we can minimize polyhedral functions, under polyhedral constraints. Indeed, consider the problem with polyhedral. We can solve the problem as the LP ### Minimization of maxima of affine functions For example, assume that is defined as the maximum of linear functions as above. The problem can be expressed as the LP (in variables and The above problem is indeed an LP: The objective of the problem is linear in the variables ; the constraints are ordinary inequalities involving affine functions. ### Minimization of a sum of maxima of affine functions We can formulate the problem of minimizing the function with values under polytopic constraints, as an LP. We use the same trick as before, introducing a new variable for each max-linear function that appears in the function . We obtain the LP representation Examples: - and -norm regression problems. ## CVX implementation In CVX, there is no need to introduce new variables in order to transform a polyhedral function minimization. We can directly minimize the function expressed as a maximum of affine functions. The snippet below implements the problem where are given vectors in . We assume that exists in the workspace. CVX implementation
    cvx_begin
       variable x(n,1)
       minimize( max(C'*x) )
       subject to
            A*x <= b;
    cvx_end
For minimizing - or -norms, we can simply rely on the corresponding matlab functions, as they are overloaded in CVX. The following snippet solves where , exist in the workspace. CVX implementation
    cvx_begin
       variable x(n,1)
       minimize( norm(A*x-b,inf) + norm(x,1) )
    cvx_end