Polyhedral Functions
Definition and examplesDefinitionWe 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 functionsPolyhedral 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 functionsPolyhedral 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 FunctionsUsing 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 functionsFor 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:
Minimization of a sum of maxima of affine functionsWe 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: CVX implementationIn 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 |