How to maximize a piecewise linear convex function $f: \mathbb{R}^n\to \mathbb{R}$?

Question

How to maximize a piecewise linear convex function $f: \mathbb{R}^n\to \mathbb{R}$? I can see that there are many references for minimizing a piecewise linear convex function but not maximizing such a function. Is this problem so trivial or it is so hard (i.e., NP-hard)? I appreciate it if you could also give a reference/hint for maximizing such functions.

Answer 1

Suppose your function is constant everywhere, then everywhere is a maximum.

Suppose it is not a constant and suppose it attains maximum value at $x_0$ with value $M$. Then consider $\{ x: f(x) < M\}$, which is a convex set that do not include $x_0$ but $x_0$ is a limit point for the set. If the set is empty, then we have a constant function. Suppose not, it means $x_0$ must be a boundary point, but your domain is unbounded. The maximum doesn't exist.

If your domain is bounded and the function is not constant, check the boundary to look for the maximum value.

Answer 2

Convexity implies the epigraph is a convex set. A function with a maximum would imply that small deviations from the maximum would be lower than or equal to the maximum. Taking two points on either side of the maximum. If one of them is not equal to the maximum then the line connecting the two points on either side of the maximum will be less than the maximum so at the point where the maximum is obtained the line would be outside the epigraph contradicting convexity. The only other possibility is that all values are the same, which is to say the function is constant. This class of functions is certainly easy to maximize, so the problem is trivial.

Answer 3

If your problem is to maximize a convex function with no constraints, then the solution is trivially $+\infty$, unless the function is constant everywhere, in which case the solution is the constant value.