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.