Piecewise Linear Convex Functions

Posted on September 16, 2024 by Yu Cong
Tags: ,

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

Notions:
  • infimal convolution: ▫\square,
  • Minkowski sum: ⊕\oplus,
  • convex conjugate: f*f^*,
  • epigraph: epi⁡f\mathop{\mathrm{epi}}f.

some notes:

1 piecewise linear function f:ℝd→ℝf:\mathbb{R}^d\to \mathbb{R}

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

Let 𝒫\mathcal P be a set of bounded convex polytopes in ℝd\mathbb{R}^d. A piecewise linear function ff can be defined as

f(x)=cPTx+dP, for x∈P, f(x)=c_P^T x+d_P, \text{ for } x\in P, where (cP,dP)∈ℝd+1(c_P,d_P)\in \mathbb{R}^{d+1} is a vector associated with polytope PP.

For continuity, we require

cPTx+dP=cQTx+dQ,∀x∈P∩Q,∀P,Q∈𝒫 c_P^T x+d_P=c_Q^T x+d_Q, \; \forall x\in P\cap Q, \forall P,Q\in \mathcal{P}

For convexity, we further require that
  1. for any subset 𝒫′⊂𝒫\mathcal{P'}\subset \mathcal P, ∪P∈𝒫′\cup_{P\in \mathcal P'} is convex;(for polytopes)
  2. the restriction of ff to any two polytopes from P that share a facet is convex.[2] (for ff. 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⁡{a1Tx+b1,…,aLTx+bL} f(x)=\max \{a_1^Tx+b_1,\ldots,a_L^Tx+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)≤αf(x)+(1−α)f(y)f(\alpha x+(1-\alpha)y)\leq \alpha f(x)+(1-\alpha)f(y) for any α∈[0,1]\alpha\in [0,1]. αx+(1−α)y\alpha x+(1-\alpha)y can locate in the same XiX_i as yy since we can arbitrarily choose α\alpha. Thus f(x)≥f(αx+(1−α)y)−(1−α)f(y)αf(x)\geq \frac{f(\alpha x+(1-\alpha)y)-(1-\alpha)f(y)}{\alpha}. Note that ff is linear in each XiX_i. Thus f(x)≥aiT(αx+(1−α)y)+bi−(1−α)(aiTy+bi)α=aiTx+bif(x)\geq \frac{a_i^T(\alpha x+(1-\alpha)y)+b_i-(1-\alpha)(a_i^Ty+b_i)}{\alpha}=a_i^Tx+b_i. Thus f(x)=max⁡iaiTx+bif(x)=\max_i a_i^Tx+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 LL be the number of hyperplanes in the definition of ff.

2.1 convex conjugate

Observation3

Let f*f^* be the convex conjugate of a pwl convex function ff. f*f^* is also pwl convex if restricted to dom⁡f*\mathop{\mathrm{dom}}f^*.

Consider the convex conjugate from a geometric view. The epigraph of our pwl convex function ff is some convex polytope in ℝd×ℝ¯\mathbb{R}^d\times \overline{\mathbb{R}}. The convex conjugate is f*(z)=sup⁡x{zTx−f(x)}f^*(z)=\sup_x\{z^Tx-f(x)\}. zTxz^Tx is a hyperplane with normal vector zz and passing through the origin. Now sup⁡x{zTx−f(x)}\sup_x\{z^Tx-f(x)\} is the amount of space hyperplane zTxz^Tx has to shift along the d+1d+1 dimension to make itself a supporting hyperplane of epi⁡f\mathop{\mathrm{epi}}f. Note that the tangent points are exactly vertices of epi⁡f\mathop{\mathrm{epi}}f.
Proof

It is safe to write f*(z)=max⁡x{zTx−f(x)}f^*(z)=\max_x\{z^Tx-f(x)\} since we only consider the extended domain. Thus we have f*(z)=max⁡x{zTx−max⁡i{aiTx+bi}}=max⁡x{max⁡i{zTx−aiTx+bi}}f^*(z)=\max_x\{z^Tx-\max_i\{a_i^Tx+b_i\}\}=\max_x\{\max_i\{z^Tx-a_i^Tx+b_i\}\}. Let nn be the number of vertices on conv⁡(epi⁡f)\mathop{\mathrm{conv}}(\mathop{\mathrm{epi}}f). One can see that f*(z)f^*(z) is the maximum of O(nL)O(nL) affine functions.

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

2.2 pwl convex function in ℝ\mathbb{R} ∘\circ a linear mapping

Problem4

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

As you expected, the answer is no. Let f:ℝ2→ℝf:\mathbb{R}^2\to \mathbb{R} be the maximum of a set of 2D planes. Consider a series of points {p1,p2,...,pk}\left\{ p_1,p_2,...,p_k \right\} on the 2D plane. After applying the linear mapping to P={p1,p2,...,pk}P=\left\{ p_1,p_2,...,p_k \right\}, we will get a sequence of numbers(points in 1D) P′={p1′,p2′,...,pk′}P'=\left\{ p_1',p_2',...,p_k' \right\}. We assume that P′P' is non-decreasing. Note that the value of gg on P′P' is always unimodal since gg is convex. However, the value of ff on PP 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,gf,g, f*+g*=(f▫g)*f^*+g^*=(f\square g)^*. It is also known that epi⁡f⊕epi⁡g=epi⁡f▫g\mathop{\mathrm{epi}}f \oplus \mathop{\mathrm{epi}}g=\mathop{\mathrm{epi}}f\square g(with some requirements on ff and gg). 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*f^* is at least nn where nn is the number of vertices(faces of 1D) in epi⁡f\mathop{\mathrm{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 f1,f2f_1,f_2 be two pwl convex functions in ℝd\mathbb{R}^d. Let n1,n2n_1,n_2 be the number of hyperplanes in f1,f2f_1,f_2 respectively. What is the minimum number of hyperplanes in f1▫f2f_1 \square 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.