how can I proof the GLOBAL optimality of a problem where the feasible region is disjoint?

Question

I want to minimize the following function. It has two variable, $x$ and $y$ are real. I want proof the global optimality. But the feasible region of the variables are disjoint. My question is, how can I proof the GLOBAL optimality of the solution?

$$ \min f(x,y) = x^2+ y^2. $$ s.t., $$ 10\leq x\leq 20 $$ $$ 30\leq x\leq 40 $$ $$ 15\leq y\leq 25 $$ $$ 70\leq y\leq 86 $$

Please help on this.

Answer 1

There are two approaches:

• Solve the problem in each connected subregion (i.e. solve four problems, since the feasible region consists of four disjoint rectangles) and pick the best of the four solutions. Then this is clearly optimal globally.
• Connect the rectangles up by removing some constraints, solve the new problem (with a single connected feasible region), and observe that in this case the optimal solution satisfies the original constraints. Since it was optimal for the new problem, and any solution of the original problem is also feasible for the new problem, it must also be optimal for the original problem.

Obviously the second approach will not always work, if in connecting the disjoint regions you introduce new solutions. But if the objective function and constraints are linear (which, sadly, they are not in this case) then taking the convex hull of your problem produces a problem with the same solution and a connected region.