Finding the optimal value in an optimization problem

Question

Given the optimization problem

$$\text{minimize}\ f_0(x_1,x_2)$$ $$\text{subject to}\ 2x_1+x_2 \ge 1$$ $$x_1+3x_2 \ge 1$$ $$x_1 \ge 0, x_2 \ge 0$$

Let the objective function be $f_0(x_1,x_2) = x_1^2 + 9x_2^2$. What is the optimal value?

I sketched the feasible set, and that is the convex hull of $(0,\infty),(0,1),(\frac{2}{5},\frac{1}{5}),(1,0),(\infty,0)$.

Normally I would try the corner points on the objective function to see which one gives me the minimal value, or draw the objective function to see where on the boundary does it intersect the feasible set. But I don't know what to do with this one.

Answer 1

Let's do a transformation $y = \frac{x_2}{3}$. Then your problem will be equivalent to minimizing $x_1^2+y^2$ subject to $x_1\geq 0$, $y\geq 0$, $x_1+y\geq 1$, and $x_1+\frac{y}{6}\geq 1$.

If the last inequality holds with equality, and we forget about the third one, the answer would need to have $x_1=y=1/2$. This satisfies all other inequalities. Moreover, if you consider any other scenario, it must have $x_1+y= z>1$, in the absence of any other constraints, the function would minimize at $x_1=y=z/2$ which would yield a value higher than what it would be when $x_1=y=1/2$. Therefore, regardless of the other constraints, the minimum value this function can take is $(1/2)^2+(1/2)^2$. Hence, we were able to find a minimizer.

Finally, this function is strictly convex, which allows us to say that the minimizer is unique.

Answer 2

This is fairly easy to guess if you draw the feasible set (the lines $2x_1+x_2 =1, x_1+3 x_2 = 1$ are easy to draw) and then draw the level sets of $f_0$ (ellipses).

The picture suggests that the $x_1+3 x_2 \ge 1$ constraint is active, so consider the problem $\min \{ f_0(x) | x_1+3 x_2 \ge 1 \}$ which can be solved using Lagrange multipliers to get $({1 \over 2}, {1 \over 6})$ (the constraint must be active since $f_0$ has a global minimum at $(0,0)$). Since this is feasible, and solves the relaxed problem, it must solve the original problem.