This blog is still talking about Piecewise linear convex objective functions. And today we will give some examples of transformation.

Piecewise linear function in Objective functions

Consider the following generalization of a LO problem, where the objective function is piecewise linear convex rather than linear:

$$ \begin{equation} \begin{aligned} &\text{minmize} && \max_{i\in \{1,\cdots,m\}}\{\bar{c_i}^T\bar{x}+k_i\} \\ &\text{subject to} && A\bar{x} \geq \bar{b} \end{aligned} \end{equation} $$

In fact, this optimization problem can be reformulated as a linear optimization problem as follow:

$$ \begin{equation} \begin{aligned} &\text{minmize} && z \\ &\text{subject to} && z \geq \bar{c_i}^T\bar{x}+k_i, \text{ for } i = 1,2,\cdots, m\\ & && A\bar{x} \geq \bar{b} \end{aligned} \end{equation} $$

Piecewise linear function in Contraints

A constriant of the form ${ f(\bar{x}) \leq \gamma }$ where ${ f }$ is a piecewise linear convex function

$$ f(\bar{x}) = \max_{i\in \{1,\cdots,m\}}\{\bar{c_i}^T\bar{x}+k_i\} $$

Can be rewritten as ${ m }$ linear constraints

$$ \begin{equation} \begin{aligned} \bar{c_1}^T\bar{x}&+k_1 \leq \gamma \\ \bar{c_2}^T\bar{x}&+k_2 \leq \gamma \\ &\vdots \\ \bar{c_n}^T\bar{x}&+k_n \leq \gamma \\ \end{aligned} \end{equation} $$