# optimization question

Minimize $x_1+6x_2-x_3$ subject to $7x_1+x_2-x_3=6$, $3x_1+x_2+2x_3\leq 6$, $x_1,x_2\in\mathbb{R_+}$.

I first tried to represent $x_3$ in terms of $x_1$ and $x_2$, so $x_3=7x_1+x_2-6$, substituting this into the cost function: $\min\{x_1+6x_2-7x_1-x_2+6\}\iff \min\{-6x_1+5x_2+6\}$ subject to $3x_1+x_2+2(7x_1+x_2-6)\leq 6\iff 17x_1+3x_2\leq 18$; I'm kind of stuck here. Any pointers?

-
What is the domain of your variables? $\mathbb{Z}$ or $\mathbb{R}$ or something more exotic? – m_l Apr 19 '12 at 15:11
sorry -- it's $\mathbb{R}$. – Emir Apr 19 '12 at 16:28

Disclaimer: Optimization is certainly not my field of expertise. That being said, this particular example can be solved by some multivariate calculus, I think.

I assume that linear programming will solve this in the blink of an eye, but I know next to nothing about it, so here is a very basic approach:

The graph of the function $$(x_1,x_2) \mapsto -6x_1+5x_2+6$$ you are trying to minimize is a plane with non-vanishing slope (i.e. the gradient has no zeroes). So there can't be a minimum in the domain defined by $x_1, x_2 > 0$, $17x_1+3x_2 < 18$. Thus, the minimum (which exists, because $x_1, x_2 \ge 0$, $17x_1+3x_2 \le 18$ defines a compact subset of $\mathbb{R}^2$) must lie on the boundary of said domain. You can easily parametrize the boundary (it is the union of three straight lines), plug the parametrization into the original function and solve the resulting one dimensional problem.

Note that the answer to your simplified problem is obvious (make $x_1$ as big as possible, $x_2$ as small as possible). I did all this hokum to provide a more or less formal proof that this is indeed the correct answer.

-

Have you considered thinking in terms of linear programming ideas? The original statement talks about the variables being positive.

-

You appear to have had the right idea, but you handled the inequality constraint somewhat too specifically. We get somewhat more freedom in working with the intersection of the two planes if we treat the inequality as describing a family of planes, $\ 3x_1 \ + \ x_2 \ + \ 2x_3 \ = \ c \$ , with $\ c \ \le \ 6 \$ . Combining this with the fixed constraint plane, $\ 7x_1 \ + \ x_2 \ - \ x_3 \ = \ 6 \$ , gives us the relation $\ 4x_1 \ - \ 3x_3 \ = \ 6 \ - \ c \$ . We will be interested in the points on the fixed plane (where the solution must lie) which obey this constraint, for which we obtain the relation given by

$$7x_1 \ + \ x_2 \ - \ \frac{1}{3} (4x_1 \ - \ 6 \ + \ c ) \ = \ 6 \ \ \Rightarrow \ \ \frac{17}{3}x_1 \ + \ x_2 \ + \ 2 \ - \frac{1}{3} c \ = \ 6$$ $$\Rightarrow \ \ \frac{17}{3}x_1 \ + \ x_2 \ = \ \frac{12 + c}{3} \ \ .$$

We can now bring in the other implicit constraints, namely that $\ x_1 \ \ge \ 0 \$ and $\ x_2 \ \ge \ 0 \$ . These will permit us to locate endpoints of line segments where the two constraint planes intersect (marked in yellow on the graph above). One endpoint occurs where $\ x_2 \ = \ 0 \$ , giving us

$$\frac{17}{3}x_1 \ + \ 0 \ = \ \frac{12 + c}{3} \ \ \Rightarrow \ \ x_1 \ = \ \frac{12 + c}{17}$$

$$\Rightarrow \ \ 7 \ \left( \frac{12 + c}{17} \right) \ + \ 0 \ - \ x_3 \ = \ 6 \ \ \Rightarrow \ \ x_3 \ = \ \left( \frac{84 + 7c}{17} \right) \ - \ 6 \ = \ \frac{7c - 18}{17} \ \ .$$

The other endpoint occurs where $\ x_1 \ = \ 0 \$ , from which we obtain

$$0 \ + \ x_2 \ = \ \frac{12 + c}{3} \ \ \Rightarrow \ \ 7 \cdot 0 \ + \ \left( \frac{12 + c}{3} \right) \ - \ x_3 \ = \ 6$$ $$\Rightarrow \ \ x_3 \ = \ \left( \frac{12 + c}{3} \right) \ - \ 6 \ = \ \frac{c - 6}{3} \ \ .$$

We note that the two endpoints $\ \left( \frac{12 + c}{17} , \ 0 , \ \frac{7c - 18}{17} \right) \$ and $\ \left( 0 , \ \frac{12 + c}{3} , \ \frac{c - 6}{3} \right) \$ "merge" at $\ (0, \ 0, \ -6) \$ on the constraint plane with $\ c \ = \ -12 \$ . (We can also figure this out by examining the behavior of the lines where the constraint planes intersect the coordinate planes $\ x_1 \ = \ 0 \$ and $\ x_2 \ = \ 0 \$ . ) So we may conclude that the extremal points lie somewhere in the region, including its edges, defined by this family of line segments in the interval $\ -12 \ \le \ c \ \le \ 6 \$ .

We can now bring in the multilinear function we wish to minimize, $f(x_1, \ x_2, \ x_3)$ $= \ \ x_1 \ + \ 6x_2 \ - \ x_3 \$ . On the graph above, we see that the "level surfaces" of this function appear as a family of parallel planes, shifting generally in the negative $\ x_2-$ direction as the value of the function decreases. This will mean that the extremal values will occur at vertices of the irregular three-dimensional volume bounded by the constraint planes and the coordinate planes $\ x_1 \ = \ 0 \$ and $\ x_2 \ = \ 0 \$ , analogously to what we see in linear programming for two variables. (Regrettably, the three-dimensional graph for this is not particularly intelligible.)

Upon calculating the values of the function for the endpoints of the line segments we described earlier, we obtain

$$f \left( \frac{12 + c}{17}, \ 0, \ \frac{7c - 18}{17} \right) \ = \ \frac{30 - 6c }{17} \ \ , \ \ f \left( 0 , \ \frac{12 + c}{3} , \ \frac{c - 6}{3} \right) \ = \ \frac{5c + 78}{3} \ \ ,$$

limited to the interval $\ -12 \ \le \ c \ \le \ 6 \$ .

A graph of these results, presented above, illustrates that the value of the function at the $\ x_1 \ = \ 0 \$ endpoint decreases with decreasing $\ c \$ . So the function attains its smallest value at that end where it meets the line on the plane $\ x_2 \ = \ 0 \$ , for $\ c \ = \ -12 \$ . However, the value of the function at the $\ x_2 \ = \ 0 \$ endpoints decrease with increasing $\ c \$ . The global minimum for the function thus occurs for $\ c \ = \ 6 \$ , at the vertex $\ \left( \frac{12 + 6}{17}, \ 0, \ \frac{7 \cdot 6 - 18}{17} \right) \ = \ \left( \frac{18}{17}, \ 0, \ \frac{24}{17} \right) \$ , that value being

$$f \left( \frac{18}{17}, \ 0, \ \frac{24}{17} \right) \ = \ \frac{30 - 6 \cdot 6 }{17} \ = \ -\frac{6 }{17} \ \ .$$

[From the same graph, we observe that the maximum value of the function is $\ f \left( 0, \ 6, \ 6 \right)$ $= \ \frac{5 \cdot 6 \ + \ 78}{3} \ = \ 36 \$ . ]

-