1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Compactness of a set of feasible solutions

  1. Dec 20, 2013 #1
    Hi everyone,

    I am working on a problem in Operations Research but I need to prove a property related to compactness of a set. Although I expect it is quite elementary, I have never studied Analysis at an advanced level so am not sure how to do it.

    I have an optimisation problem in which a feasible solution may be expressed as a set of real numbers [itex]\{\lambda_1,\lambda_2,....,\lambda_n\}[/itex] which satisfies the following constraints:

    [itex]\sum\limits_{i=1}^n \lambda_i\leq \lambda[/itex] (here [itex]\lambda[/itex] is a positive real number),

    [itex]\lambda_i\geq 0[/itex] for all [itex]i\in\{1,2,...,N\}[/itex].

    The problem is I need to prove that the set of feasible solutions satisfying the above constraints is a compact set (closed and bounded), because this will enable me to prove that an optimal solution exists to the optimisation problem I am working on. I am sure this is probably quite standard and perhaps someone might be able to point me towards a theorem somewhere which will give me what I need, or just provide an outline of the proof if it is simple.

    Thanks a lot!
     
  2. jcsd
  3. Dec 21, 2013 #2

    fzero

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If the solution set [itex]\{\lambda_1,\lambda_2,....,\lambda_n\}[/itex] consists of a finite set of points, then it is certainly compact. The closed interval ##[0,\lambda]## that contains all possible solutions is also a compact space.
     
  4. Dec 21, 2013 #3
    Hi,

    Sorry, I think I may not have explained it well enough. By 'set of feasible solutions' I mean the set of all sets [itex]\{\lambda_1,\lambda_2,...,\lambda_n\}[/itex] satisfying the constraints [itex]\sum_{i=1}^n \lambda_i\leq \lambda[/itex] and [itex]\lambda_i\geq 0[/itex] for all [itex]i\in\{1,2,...,N\}[/itex]. This set will obviously be infinite (and uncountable), as there are infinitely many possible combinations [itex]\{\lambda_1,\lambda_2,...,\lambda_n\}[/itex] that satisfy these constraints.

    To put it another way, I am trying to prove compactness of the following set:

    [itex]\left\{(\lambda_1,\lambda_2,...,\lambda_n)\in\mathbb{R}^n:\sum\limits_{i=1}^n \lambda_i\leq \lambda\text{ and }\lambda_i\geq 0\text{ for all }i\right\}.[/itex]

    where [itex]\lambda[/itex] is a positive real number.

    Thanks for your help!
     
    Last edited: Dec 21, 2013
  5. Dec 21, 2013 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It's just Bolzano-Weierstrass, isn't it? Closed and bounded.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Compactness of a set of feasible solutions
  1. Compact Set (Replies: 14)

  2. Compact set (Replies: 3)

  3. Compact Sets (Replies: 6)

Loading...