# Converting nonlinear program into linear program

Consider the following nonlinear optimization problem \begin{align} \min \quad c^Tx &+ f(d^Tx)\\ \text{s.t.} \quad Ax &\geq b\\ x &\geq 0 \end{align}

where $$f(y) = \begin{cases} -y+2 \quad &\text{if}\quad y\leq2\\ 0 \quad &\text{if}\quad 2\lt y\leq 4\\ \frac{1}{2}y-2 &\text{if}\quad y\gt 4 \end{cases}$$

and $A\in\mathbb{R}^{m\times n}$, $b \in \mathbb{R}^m$, and $c,d\in\mathbb{R}^n$ are given.

(a) Carefully sketch the function $f(y)$. (done)

(b) Reformulate the optimization problem as an equivalent Linear Program. (done)

(c) Write your Linear Program in the form \begin{align} \min \quad a^T w &\\ \text{s.t.}\quad Bw &\geq g\\ w &\geq 0 \end{align}

providing the relevant definitions of $a$, $w$, $B$ and $g$.

I've already reformulated the optimization problem as: \begin{align} \min\quad c^Tx + z& \\ \text{s.t.}\qquad Ax &\geq b\\ d^Tx+z &\geq 2\\ -\frac{1}{2}d^Tx + z &\geq -2\\ x &\geq 0\\ z &\geq 0 \end{align}

where $z \equiv \max(-y+2, 0, \frac{1}{2}y-2)$. I'm not quite sure how to start part c. Can someone point me in the right direction?

• I think your answer on (b) is not correct. Think about the following. In your linear problem: Is $z$ a unknown or a parameter? What is $y$ (on which $z$ depends)? – gerw Feb 5 '15 at 7:49
• @gerw I edited it. Not entirely sure why I had constants instead of z in the reformulated LP. Must be getting late. – slsniff Feb 5 '15 at 8:50
• Now simply define $w = (x,z)$ and write everything in a matrix format. Note, $z$ is not equal to the max function as you write. It is intended to act as an upper bound of that function, but at optimality, equality will hold (as z would be sub-optimal otherwise) – Johan Löfberg Feb 5 '15 at 9:25
• @JohanLöfberg: This could serve as an answer. – gerw Feb 5 '15 at 10:14