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?

  • $\begingroup$ 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)? $\endgroup$ – gerw Feb 5 '15 at 7:49
  • $\begingroup$ @gerw I edited it. Not entirely sure why I had constants instead of z in the reformulated LP. Must be getting late. $\endgroup$ – slsniff Feb 5 '15 at 8:50
  • 2
    $\begingroup$ 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) $\endgroup$ – Johan Löfberg Feb 5 '15 at 9:25
  • $\begingroup$ @JohanLöfberg: This could serve as an answer. $\endgroup$ – gerw Feb 5 '15 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.