Why are the other constraints inactive?

Question

My task is to find $maximum$ of function $f(x) = x_1 x_2$ on convex hull of points: $(2,0), (8,0), (10,4,), (5,8) (0,6), (0, \frac32)$.

I am aware that I should find $max f$ as $-min(-f)$ on set of constraints $G$. Functions of constraints are those linear functions that wrap around (and make) the convex hull.

Trivially is deduced that those functions are (I am using inequalities to describe the convex hull):

1. $3 x_1 + 4 x_2 \ge 6$

2. $2 x_1 - x_2 \le 16$

3. $4 x_1 + 5 x_2 \le 60$

4. $-2 x_1 + 5 x_2 \le 30$

   and obvious $x_1 \ge 0, x_2 \ge 0.$ However, the book suggest that the only active constraint is the third one and furthermore uses only that when determining $KKT$ points. How do I prove that? I had tried with subtracting $6x_1$ from third inequality to obtain the fourh one, but I did not succeed. Thank you in advance.

Answer 1

As we need only consider positive $x,y$, the target function increases as we move either directly up or directly to the right. Any point $(x,y)$ of the convex hull that is not on the line segment between $(10,4)$ (the unique point with maximal $x$) and $(5,8)$ (the unique point with maximal $y$) cannot be a maximizer because either $(x+\epsilon,y)$ or $(x,y+\epsilon)$ is still the convex hull.

Answer 2

I don't know how this problem is solved using "standard algorithms". Instead I'd draw a figure. The objective function is constant on the hyperbolic arcs $x_1x_2=c>0$ and increases when moving northeast. It is then obvious that it takes its maximum on the given polygon along the edge connecting the points $(10,4)$ and $(5,8)$.