The Question:
In a certain nonlinear programming problem, the objective is to maximize the function
$$f(x_1) + 2x_2 – 5x_3,$$
where
$$f(x_1) = \begin{cases}
2x_1 + 1 & \text{if } 0 \leq x_1 < 1 \\
x_1 + 2 & \text{if } 1 \leq x_1 < 2 \\
-2x_1 + 8 & \text{if } 2 \leq x_1
\end{cases}$$
subject to some linear constraint involving $x_1,x_2,$ and $x_3$ and nonnegativity restrictions on $x_1,x_2$, and $x_3$.
a. Describe how to linearize the objective function so that the problem may be solved via a single linear program. Hint: Graph $y = 2x_1 + 1$, $y= x_1 + 2$, and $y= -2x_1 + 8$, and $y = f(x_1)$ for $0 \leq x_1 \leq 3$. How does the graph of $y=f(x_1)$ relate to the graphs of $y = 2x_1 + 1$, $y= x_1 + 2$, and $y= -2x_1 + 8$?
b. Now suppose that
$$f(x_1) = \begin{cases}
-x_1 + 4 & \text{if } 0 \leq x_1 < 1 \\
x_1 + 2 & \text{if } 1 \leq x_1 < 2 \\
-2x_1 + 8 & \text{if } 2 \leq x_1 \\
\end{cases}$$
Would the same approach work here? Explain why or why not.
Can someone give me some ideas on how to solve this? Thank you!
Best Answer
Provided that the piecewise linear function to be maximized is continuous and concave down, we can transform it into
\begin{align} \mbox{maximize }\,&y+2x_2-5x_3\\ \mbox{subject to }\,&y\leq 2x_1+1,\\ & y\leq x_1+2,\\ & y\leq -2x_1+8.\\ \end{align} The variables are $x_1,x_2,x_3,y$. The nonnegative constraints are $\,x_1\geq 0, x_2\geq 0, x_3\geq 0\,$ as usual. If the piecewise function is not concave down, the maximization requires trials and errors.
For problem b, one can study two cases: $x_1\leq 1$ and $x_1\geq 1$. In the two ranges of $x_1$, the problem is concave down and has a unique maximum. Then compare the two maxima to see which one is the global maximum. The method is called branch and bound, which is useful for solving non-convex (because optimization theory often deals with minimization problems) or integer programming problems.