Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.