Polyhedral Functions
Definition and examplesDefinitionWe say that a function That is, a function ![]() can be expressed as a polyhedron: there exist a matrix ![]() Maxima of affine functionsPolyhedral functions include in particular, functions that can be expressed as a maximum of a finite number of affine functions: ![]() where ![]() can be expressed as the polyhedron ![]() Example: The ![]() 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 Indeed, the condition ![]() Hence, Example: The ![]() Minimization of Polyhedral FunctionsUsing LPs, we can minimize polyhedral functions, under polyhedral constraints. Indeed, consider the problem ![]() with ![]() Minimization of maxima of affine functionsFor example, assume that ![]() can be expressed as the LP (in variables ![]() The above problem is indeed an LP:
Minimization of a sum of maxima of affine functionsWe can formulate the problem of minimizing the function ![]() 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 ![]() 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 CVX implementation
cvx_begin variable x(n,1) minimize( max(C'*x) ) subject to A*x <= b; cvx_end For minimizing ![]() where CVX implementation
cvx_begin variable x(n,1) minimize( norm(A*x-b,inf) + norm(x,1) ) cvx_end |