Tags: alg, optimization

This post is a note on epigraphs, infimal convolution, Minkowski sum & convex conjugate of piecewise linear convex functions in $R^{d}$ . I want to provide proofs for relations between these operations and counterexamples for wrong guesses.

Notions:

infimal convolution: $□$ ,
Minkowski sum: $\oplus$ ,
convex conjugate: $f^{*}$ ,
epigraph: $epi f$ .

some notes:

1 piecewise linear function $f : R^{d} \to R$

A intuitive but very complex definition is the following[1],

Definition1

Let $P$ be a set of bounded convex polytopes in $R^{d}$ . A piecewise linear function $f$ can be defined as

$f (x) = c_{P}^{T} x + d_{P}, for x \in P,$ where $(c_{P}, d_{P}) \in R^{d + 1}$ is a vector associated with polytope $P$ .

For continuity, we require

$c_{P}^{T} x + d_{P} = c_{Q}^{T} x + d_{Q}, \forall x \in P \cap Q, \forall P, Q \in P$

For convexity, we further require that

for any subset $P^{'} \subset P$ , $\cup_{P \in P^{'}}$ is convex;(for polytopes)
the restriction of $f$ to any two polytopes from P that share a facet is convex.[2] (for $f$ . In fact, 1 is already included in 2.)

(Later I find a much simpler definition in [3] example 3.5.)

Definition2piecewise linear function in

R^{d}

$f (x) = max {a_{1}^{T} x + b_{1}, \dots, a_{L}^{T} x + b_{L}}$

It is shown in exercise 3.29 that every piecewise linear convex function can be expressed in this form.

Proof

We have $f (αx + (1 - α) y) \leq α f (x) + (1 - α) f (y)$ for any $α \in [0, 1]$ . $αx + (1 - α) y$ can locate in the same $X_{i}$ as $y$ since we can arbitrarily choose $α$ . Thus $f (x) \geq \frac{f ( αx + ( 1 - α ) y ) - ( 1 - α ) f ( y )}{α}$ . Note that $f$ is linear in each $X_{i}$ . Thus $f (x) \geq \frac{a _{i}^{T} ( αx + ( 1 - α ) y ) + b _{i} - ( 1 - α ) ( a _{i}^{T} y + b _{i} )}{α} = a_{i}^{T} x + b_{i}$ . Thus $f (x) = max_{i} a_{i}^{T} x + b_{i}$ .

Now given these definitions we are particularly interested in the minimum number of polytopes which define the piecewise liner convex function in high dimension.

2 properties

pwl = piecewise linear. Let $L$ be the number of hyperplanes in the definition of $f$ .

2.1 convex conjugate

Observation3

Let $f^{*}$ be the convex conjugate of a pwl convex function $f$ . $f^{*}$ is also pwl convex if restricted to $dom f^{*}$ .

Consider the convex conjugate from a geometric view. The epigraph of our pwl convex function $f$ is some convex polytope in $R^{d} \times \overline{R}$ . The convex conjugate is $f^{*} (z) = sup_{x} {z^{T} x - f (x)}$ . $z^{T} x$ is a hyperplane with normal vector $z$ and passing through the origin. Now $sup_{x} {z^{T} x - f (x)}$ is the amount of space hyperplane $z^{T} x$ has to shift along the $d + 1$ dimension to make itself a supporting hyperplane of $epi f$ . Note that the tangent points are exactly vertices of $epi f$ .

Proof

It is safe to write $f^{*} (z) = max_{x} {z^{T} x - f (x)}$ since we only consider the extended domain. Thus we have $f^{*} (z) = max_{x} {z^{T} x - max_{i} {a_{i}^{T} x + b_{i}}} = max_{x} {max_{i} {z^{T} x - a_{i}^{T} x + b_{i}}}$ . Let $n$ be the number of vertices on $conv (epi f)$ . One can see that $f^{*} (z)$ is the maximum of $O (n L)$ affine functions.

I believe there will be only $O (n)$ hyperplanes on $f^{*}$ instead of $O (n L)$ … However, we know that in general $f^{*}$ is the maximum of at least $O (n)$ functions since every vertex corresponds to a hyperplane in $epi f^{*}$ .

2.2 pwl convex function in $R$ $\circ$ a linear mapping

Problem4

Let $f : R^{d} \to R$ be a pwl convex function. Does there always exist a pwl convex $g : R \to R$ and a linear mapping $a^{T} x - b : R^{d} \to R$ such that $f (x) = g (a^{T} x - b)$ .

As you expected, the answer is no. Let $f : R^{2} \to R$ be the maximum of a set of 2D planes. Consider a series of points ${p_{1}, p_{2}, ..., p_{k}}$ on the 2D plane. After applying the linear mapping to $P = {p_{1}, p_{2}, ..., p_{k}}$ , we will get a sequence of numbers(points in 1D) $P^{'} = {p_{1}^{'}, p_{2}^{'}, ..., p_{k}^{'}}$ . We assume that $P^{'}$ is non-decreasing. Note that the value of $g$ on $P^{'}$ is always unimodal since $g$ is convex. However, the value of $f$ on $P$ may not be unimodal. Thus the composition of a linear mapping and a pwl convex function in 1D is not equivalent to pwl convex functions in high dimensions.

3 sum of pwl convex functions

I want to show that in general the number of hyperplanes in the sum of pwl convex functions can be large.

It is known that for two pwl convex functions $f, g$ , $f^{*} + g^{*} = (f □ g)^{*}$ . It is also known that $epi f \oplus epi g = epi f □ g$ (with some requirements on $f$ and $g$ ). There is a theorem in [4] section 4.3 which shows that the number of faces of the Minkowski sum of two polytopes can be huge. The bound can be reached by sums of cyclic polytopes.

We can define pwl convex functions based on cyclic polytopes and we know that the Minkowski sum will have lots of faces(of different dimensions). We also know that the number of faces in $f^{*}$ is at least $n$ where $n$ is the number of vertices(faces of 1D) in $epi f$ . Now if the infimal convolution of two pwl convex functions also has many faces, the number of faces in the sum of pwl convex functions will be large.

Problem5

Let $f_{1}, f_{2}$ be two pwl convex functions in $R^{d}$ . Let $n_{1}, n_{2}$ be the number of hyperplanes in $f_{1}, f_{2}$ respectively. What is the minimum number of hyperplanes in $f_{1} □ f_{2}$ ?

References

[1]

A. Toriello, J.P. Vielma, Fitting piecewise linear continuous functions, European Journal of Operational Research. 219 (2012) 86–95 10.1016/j.ejor.2011.12.030.

[2]

J.M. Tarela, E. Alonso, M.V. Martínez, A representation method for PWL functions oriented to parallel processing, Mathematical and Computer Modelling. 13 (1990) 75–83 10.1016/0895-7177(90)90090-a.

[3]

S.P. Boyd, L. Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, UK ; New York, 2004.

[4]

T. Mountford, T. Liebling, K. Fukuda, P. Gritzmann, G. Ziegler, Minkowski Sums of Polytopes: Combinatorics and Computation, PhD thesis, n.d.

Piecewise Linear Convex Functions

1 piecewise linear function f:Rd→R