0

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.

Rayne
  • 331

2 Answers2

3

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.

Adam
  • 153
  • 5
  • Should the transformation be $y = 3x_2$ instead? And the constraints become $x_1 \ge 0, y \ge 0, x_1 + y \ge 1$, and $2x_1 + \frac{y}{3} \ge 1$? – Rayne Feb 15 '16 at 05:48
  • I tried solving the last 2 constraints and still get the intersection of the last 2 constraints as $x_1 = \frac{2}{5}, y = \frac{1}{5}$, which gives me $x_2 = \frac{1}{15}$. How did you get $x_1 = \frac{1}{2}$? – Rayne Feb 15 '16 at 06:04
0

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.

copper.hat
  • 172,524
  • How do I draw the level sets of $f_0$? Also, why does $f_0$ have a global minimum at $(0,0)$? Is it by differentiating $f_0(x) = 3x_1^2 + 9x_2^2$ and setting it to 0? But doesn't the point $(0,0)$ not satisfy the constraint $x_1 + 3x_2 \ge 1$? – Rayne Feb 13 '16 at 13:54
  • The level sets can be drawn, for example, by solving $f_0(x) = 0,1,2,...$. The solutions are ellipses centred at $(0,0)$. It is easy to see that $f_9(x) \ge 0$ and $f_0((0,0)) = 0$, so $(0,0)$ is the global and only (since strictly convex) minimiser. The global minimiser is not feasible. The point was that in the relaxed problem the constraint must be active (otherwise the minimiser would be the unconstrained minimiser, which is infeasible, so it can't be :-)). – copper.hat Feb 13 '16 at 17:26
  • The constraint $x_1 + 3x_2 \ge 1$ is active because one of the level sets intersects it? – Rayne Feb 14 '16 at 06:56
  • If it was not active at a solution then $x_1+3x^2>1$ and then $(x_1,x_2)$ would be an unconstrained minimiser of $f_0$. However, since $(0,0)$ is not feasible, we know that this cannot hold, hence the constraint must be active at a minimiser. – copper.hat Feb 14 '16 at 08:18