1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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


    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

    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


    User Avatar
    Science Advisor
    Homework Helper

    It's just Bolzano-Weierstrass, isn't it? Closed and bounded.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted