Compactness of a set of feasible solutions

[gjones89]

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 \{\lambda_1,\lambda_2,...,\lambda_n\} which satisfies the following constraints:

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

\lambda_i\geq 0 for all i\in\{1,2,...,N\}.

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!

 

[fzero]

If the solution set \{\lambda_1,\lambda_2,...,\lambda_n\} 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.

 

[gjones89]

Hi,

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

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

\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\}.

where \lambda is a positive real number.

Thanks for your help!

 

[Dick]

Hi,

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

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

\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\}.

where \lambda is a positive real number.

Thanks for your help!

It's just Bolzano-Weierstrass, isn't it? Closed and bounded.