Lipschitz constant of piecewise linear (vector valued) functions

Suppose we have a collection of sets {\{\Omega_i \subset \mathbb{R}^{n}\}_{i=1}^d} and a set of {d} linear functions {\{f_i(x) = A_ix +c_i\mid x\in \Omega_i, i=1,\dots, d\}} where each {\Omega_i} being closed polyhedrons in {\mathbb{R}^{n}}, i.e., {\Omega_i = \{x\mid a_{i_j}^Tx + b_{i_j} \leq 0,\forall j\leq k(i)\}} for some {a_{i_j} \in \mathbb{R}^{n},b_{i_j}\in \mathbb{R},k(i)\in \mathbb{N}}, and {A_i\in \mathbb{R}^{m\times n}} and {c_i \in \mathbb{R}^{m}}. Moreover, for any {i\not =j}, and {x\in \Omega_i \cap \Omega_j}, we have {f_i(x) = f_j(x)}. Then we can define function {f} on {\Omega =\cup_{i=1}^d \Omega_i} such that

\displaystyle f(x) = f_i(x) \quad \text{if} \; x\in \Omega_i.

We further assume \Omega is convex. We now state a theorem concerning the Lipschitz constant of {f}.

Theorem 1 Under the above setting, given arbitrary norms {\|\cdot\|_\alpha,\|\cdot\|_\beta }, {f} is {\max_{i\leq d}\{\|A_i\|_{\alpha,\beta}\}}-Lipschitz continuous with respect to {\|\cdot\|_\alpha} and {\|\cdot \|_\beta }, i.e., for all {x_1,x_2 \in \Omega},

\displaystyle \begin{aligned} \| f(x_2) - f(x_1)\|_\alpha \leq \max_{i\leq d}\{\|A_i\|_{\alpha,\beta }\}\|x_2-x_1\|_\beta . \end{aligned} \ \ \ \ \ (1)

Here {\|A_i\|} is {\|A_i\|_{\alpha,\beta } = \max_{\|x\|_\beta \leq 1}\|A_ix\|_{\alpha}}.

Proof: By letting {g(t) = x_1 + t(x_2 - x_1)}, {L = \max_{i\leq d}\{\|A_i\|_{\alpha,\beta }\}\|x_2-x_1\|_\beta } and {h= f\circ g}. we see the inequality (1) is equivalent to

\displaystyle \begin{aligned} \|h(1)- h(0)\|_\alpha \leq L. \end{aligned} \ \ \ \ \ (2)

Using the property that {f} is well-defined on {\Omega_i\cap \Omega_j} for any {i,j}, we have that there exists {0=t_0\leq \dots \leq t_l\leq \dots \leq t_K\leq t_{K+1}=1, l=1,\dots,K} and corresponding {i_1,\dots ,i_K} such that

\displaystyle \begin{aligned} h(t_l)= A_{i_l}x^{(l)}+c_{i_l} = A_{i_{l-1}}x^{(l)}+c_{i_{l-1}} \end{aligned} \ \ \ \ \ (3)

for all {1\leq l\leq K} where {x^{(l)} = g(t_l)}. We also let {x^{(0)} =g(t_0) =x_1} and {x^{(K+1)}=g(t_{{K+1}}) =x_2}. These {x_l}s have the property that

\displaystyle \begin{aligned} \sum_{l=0}^{K}\|x_{i_{l+1}} -x_{i_l}\|_\beta = \sum_{l=0}^{K}(t_{l+1}-t_l)\|x_2 -x_1\|_\beta = \|x_2-x_1\|_\beta . \end{aligned} \ \ \ \ \ (4)

Thus we can bound the term {\|h(1)- h(0)\|_\alpha } by

\displaystyle \begin{aligned} \|h(1) - h(0)\|_\alpha &\leq \sum_{l=0}^{K} \|h(t_{l+1}) -h(t_{l})\|_\alpha \\ & \leq \sum_{l=0}^{K} \|A_{i_{l+1}}x_{l+1} +c_{i_{l+1}} - A_{i_l}x_{l} -c_{i_l}\|_\alpha \\ &\overset{(i)}{\leq } \sum_{l=0}^{K-1} \|A_{i_{l}}x_{l+1} +c_{i_{l}} - A_{i_l}x_{l} -c_{i_l}\|_\alpha \\ & = \sum_{l=0}^{K} \|A_{i_{l}}x_{l+1} - A_{i_l}x_{l} \|_\alpha \\ &\overset{(ii)}{\leq}\sum_{l=0}^{K}\|A_{i_l}\|_{\alpha,\beta } \|x_{l+1}-x_{l}\|_\beta \\ & \leq \max_{i}\{\|A_i\|_{\alpha,\beta },i\leq d\}\sum_{l=0}^{K} \|x_{l+1}-x_{l}\|_\beta \\ & \overset{(iii)}{\leq}\max_{i}\{\|A_i\|_{\alpha,\beta },i\leq d\} \|x_2-x_1\|_\beta \\ & = L, \end{aligned} \ \ \ \ \ (5)

where {(i)} is due to inequality (3), {(ii)} is due to the definition of operator norm and {(iii)} is using equality (4). This proves inequality (1). \Box

2 thoughts on “Lipschitz constant of piecewise linear (vector valued) functions

Leave a Reply to Chao Huang Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s