This blog is going to talk about Piecewise linear convex objective functions. Why we study that? Becasue this kind of problems can be cast as “Linear Programming Problems”.

Piecewise linear convex functions

Preparation

*1. Let ${ \alpha_1, \alpha_2,\cdots, \alpha_m}$ and ${ \beta_1, \beta_2,\cdots, \beta_m}$ be real number such that${ \forall i \in [1,m], \alpha_i \leq \beta_i}$

• Claim ${ \max\{ \alpha_1, \alpha_2,\cdots, \alpha_m \} \leq \max \{ \beta_1, \beta_2,\cdots, \beta_m\} }$

Proof. ${\forall i, \alpha_i \leq \beta_i \leq \max { \beta_1, \beta_2,\cdots, \beta_m} }$, so

$$ \max \{ \alpha_1, \alpha_2,\cdots, \alpha_m\} \leq \max \{ \beta_1, \beta_2,\cdots, \beta_m\} $$

*2. Let ${ a_1, a_2,\cdots, a_m}$ and ${ b_1, b_2,\cdots, b_m}$ be real number. ${ \max \{a_1+b_1, a_2+b_2, \cdots, a_m+b_m\} \leq \max \{ a_1, a_2,\cdots, a_m\} + \max \{ b_1, b_2,\cdots, b_m\}}$

• Claim ${ \max \{a_1+b_1, a_2+b_2, \cdots, a_m+b_m\} \leq \max \{ a_1, a_2,\cdots, a_m\} + \max \{ b_1, b_2,\cdots, b_m\}}$

We have ${ a_k + b_k \leq a_k + \max \{ b_1, b_2,\cdots, b_m\} \leq \max \{ a_1, a_2,\cdots, a_m\} + \max \{ b_1, b_2,\cdots, b_m}, \forall k \in {1,2,\cdots, m\}}$

so ${ \max \{a_1+b_1, a_2+b_2, \cdots, a_m+b_m\} \leq \max \{ a_1, a_2,\cdots, a_m\} + \max \{ b_1, b_2,\cdots, b_m\}}$

Proof of theorem

• Theorem: If ${ f_1, f_2, \cdots, f_m: \mathbb{R}^n \rightarrow \mathbb{R} }$ are convex functions, then the function ${ f }$ defined by

$$ f(\bar{x}) = \max \{f_1(\bar{x}), \cdots, f_m(\bar{x})\} $$

is also a convex function.

Proof. ${ \forall \bar{x},\bar{y} \in\mathbb{R}^n ,\forall \lambda \in [0,1]}$

${ f_i }$ is convex, that means

$$ f_i((1-\lambda)\bar{x}+\lambda\bar{y}) \leq (1-\lambda) f_i(\bar{x}) + \lambda f_i(\bar{y}) $$

Therefore,

$$ \begin{aligned} f((1-\lambda)\bar{x}+\lambda{y}) & = \max_{i\in\{1,2,\cdots,m\}} \{f_i((1-\lambda)\bar{x}+\lambda\bar{y}) \} \\ & \leq \max_{i\in\{1,2,\cdots,m\}} \{(1-\lambda) f_i(\bar{x}) + \lambda f_i(\bar{y}) \} \\ & \leq \max_{i\in\{1,2,\cdots,m\}} \{(1-\lambda) f_i(\bar{x})\}+\max_{i\in\{1,2,\cdots,m\}}\{\lambda f_i(\bar{y})\} \end{aligned} $$

Here, ${ (1-\lambda),\lambda \geq 0 }$, so

$$ \begin{aligned} f((1-\lambda)\bar{x}+\lambda{y}) & \leq \max_{i\in\{1,2,\cdots,m\}} \{(1-\lambda) f_i(\bar{x})\}+\max_{i\in\{1,2,\cdots,m\}}\{\lambda f_i(\bar{y})\} \\ & \leq (1-\lambda)\max_{i\in\{1,2,\cdots,m\}} \{f_i(\bar{x})\}+ \lambda \max_{i\in\{1,2,\cdots,m\}}\{ f_i(\bar{y})\} \\ & = (1-\lambda)f(\bar{x}) + \lambda f(\bar{y}) \end{aligned} $$

• Corollary: Any function ${ f:\mathbb{R}^n \rightarrow \mathbb{R} }$ of type

$$ f(\bar{x}) = \max_{j\in\{1,2,\cdots,m\}} \{\bar{c_j}^T\bar{x}+ K_j\} $$

is convex

Proof. Each function is an affine function, which is convex. So, the function in above form is convex.

• Definition: This form ${ f(\bar{x}) = \max_{j\in{1,2,\cdots,m}} \{\bar{c_j}^T\bar{x}+ K_j\} }$ is called piecewise linear convex function