Transforming a linear program using a convex function into standard form

Question

A paper that I am reading has a linear program of the following form:

$ \text{minimize}\ \sum_{i=1}^n f_i(x_i) + c \cdot \sum_{i=1}^n (x_i - x_{i - 1})^+ $

where $f_i$ is a non-negative convex function and $(\cdot)^+ := \text{max}\{0, \cdot\}$.

How can such a linear program be transformed into a standard form like:

$ \text{minimize}\ c^T x \\ \text{subject to} \\ Ax \leq b \\ x \geq 0 $

(for both integer and continuous linear programs)

Answer 1

I don't think you can linearize $f_i(x_i)$, but (assuming $c>0$) you can linearize the $(.)^+$ part by introducing nonnegative variables $y_i$, replacing the second sum in the objective with $c\sum_i y_i$, and imposing constraints $y_i \ge x_i - x_{i-1}$.