Skip to main content
2 of 5
edited title

How to find the vertices of the set $\{v_i\in \mathbb{R}:a_1\ge v_1\ge v_2\ge \cdots\ge v_n\ge 0,\ q_2\le \sum_{i=1}^n p_iv_i\le q_1\}$?

I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, $q_2\le \sum_{i=1}^n p_iv_i\le q_1$, with $q_1,q_2$ positive reals, and only one bound for the coordinates: $v_1\le a_1$, where $a_1\ge 0$. My question is:

What are the vertices of the polytope created by these set of constraints?

I could easily find the vertices when $a_1=\infty$, by equating $k$ of the variables, at a time, for $1\le k\le n$, and finding the solution from the second inequality. However, I am not sure how to incorporate the bound on $v_1$ to find the vertices. I suspect there will be more vertices than the ones found when there is no upper bound on $v_1$, similar to this problem here. Can anyone kindly give some pointers regarding how to find the vertices? Also, please refer to some relevant literature. Thanks in advance.