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

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.

-
Do you mean "region" instead of "resign?" Not sure what "feasible resign" means. – Thomas Andrews Dec 10 '12 at 18:53
@ThomasAndrews: you are right, I meant region. I edited text. Thanks for informing me. – fayzur Dec 10 '12 at 19:05
I answered speculatively but it would help if you told us what you already know about solving the problem when the feasible region is not like this. (P.S. your use of "disjoint" is incorrect here; a set cannot be disjoint on its own, it has to be disjoint from another set. I guessed in my answer that you meant "not connected", i.e. consisting of several separated components.) – Ben Millwood Dec 10 '12 at 19:16

1 Answer

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.

-