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 $\{p_i\}_{i=1}^n,\ 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 helpful comments regarding how to find the vertices? Also, please refer to some relevant literature. Thanks in advance.
 A: Let 
\begin{equation*}
 h_i:=v_i-v_{i+1}\quad\forall i\in[n]:=\{1,\dots,n\},\quad \text{with}\ v_{n+1}:=0. 
\end{equation*}
Then 
\begin{equation*}
 \sum_{i=1}^n p_iv_i=\sum_{i=1}^n p_i\sum_{j=i}^n h_j=\sum_{j=1}^n c_jh_j,\quad 
 c_j:=\sum_{i=1}^j p_i>0. \tag{0}
\end{equation*}
So, the problem reduces to finding the extreme points of the convex polytope $P$ defined by 
\begin{gather*}
 h_j\ge0\quad\forall j,\\
 q_2\le\sum_{j=1}^n c_jh_j\le q_1, \\
 \sum_{j=1}^n h_j\le a_1. 
\end{gather*}
Suppose that $h=(h_1,\dots,h_n)\in P$ and there is a subset $J$ of the set $[n]$ such that the cardinality of $J$ is $3$ and $h_j>0$ for all $j\in J$. The system of equations $\sum_{j\in J} c_j y_j=0$ and $\sum_{j\in J} y_j=0$ has a nonzero solution $y=(y_1,\dots,y_n)$ with $y_j=0$ for $j\notin J$. Then $h\pm ty\in P$ for small enough $t>0$. So, $h\notin ext\,P$, where $ext\,P$ denotes the set of extreme points of $P$. 
So, for any $h=(h_1,\dots,h_n)\in ext\,P$ the set $\{i\colon h_i\ne0\}$ is of cardinality $\le2$. 
(In view of (0), this means that, if $v=(v_1,\dots,v_n)$ is a vertex of the original polytope in the OP, then the $v_i$'s take at most three values, at most two of them nonzero.)  
For any $h\in ext\,P$, denoting the only possible nonzero values of $h_i$'s by $u$ and $v$, we see that the problem reduces to finding the extreme points of the convex polytopes $P_{j,k}$ in $\mathbb R^2$ defined by conditions 
\begin{equation*}
\begin{gathered}
 u,v\ge0,\\
 q_2\le c_ju+c_k v\le q_1  \\
 u+v\le a_1, 
\end{gathered} \tag{$\ast$} 
\end{equation*}
for $j,k\in[n]$. The case $j=k$ is very easy. 
So, it remains to consider the problem of finding the extreme points of $P_{j,k}$ for any fixed integers $j,k$ such that $1\le j<k\le n$, so that 
\begin{equation*}
 0<c_j<c_k. 
\end{equation*} 
Without loss of generality (wlog) $0<q_2<q_1$ (otherwise, the problem becomes very easy). 
The conditions $u,v\ge0$ and $q_2\le c_ju+c_k v\le q_1$ define the trapezoid $T$ in $\mathbb R^2$ with vertices $(u_1,0)$, $(u_2,0)$, $(0,v_1)$, $(0,v_2)$, where 
\begin{equation*}
 u_i:=\frac{q_i}{c_j},\quad v_i:=\frac{q_i}{c_k}, 
\end{equation*}
so that 
\begin{equation*}
 u_1>\max(v_1,u_2)\ge\min(v_1,u_2)>v_2.  \tag{$\ast$$\ast$}
\end{equation*}
The set of vertices of the polytope $P_{j,k}$ will depend on the position of the line $\ell:=\{(u,v)\colon u+v=a_1\}$ 
relative to the trapezoid $T$. 
For each $i=1,2$, let $(U_i,V_i)$ be defined as the solution of the system of equations 
\begin{equation*}
\begin{gathered}
c_jU_i+c_k V_i=q_i, \\
 U_i+V_i=a_1. 
\end{gathered} 
\end{equation*}
Geometrically, $(U_i,V_i)$ is the point of intersection of lines $\ell$ and $\ell_i:=\{(u,v)\colon c_ju+c_k v\le q_i\}$. Note that 
\begin{equation*}
 U_i,V_i\ge0\iff v_i\le a_1\le u_i. \tag{$\ast$$\ast$$\ast$}
\end{equation*}
The following picture shows the $5$ possible cases depending on the position of the line $\ell$ (with the $u$- and $v$-intercepts equal $a_1$)
relative to the trapezoid $T$, with the color of the colored line $\ell$ depending on the case, with $(c_j, c_k, q_1, q_2)=(1, 2, 3, 2)$ and thus with $u_1=3$, $u_2=2$, $v_1=3/2$, $v_2=1$:   

The $5$ possible cases are as follows: 
"Black" case: $a_1>u_1$. Then, by ($\ast$$\ast$$\ast$) and ($\ast$$\ast$), condition $U_i,V_i\ge0$ holds for neither $i=1$ nor $i=2$. Here the vertices of $P_{j,k}$ are the same as the vertices of $T$: $(u_1,0)$, $(u_2,0)$, $(0,v_1)$, $(0,v_2)$. 
"Blue" case: $u_2<v_1\le a_1\le u_1$. Then condition $U_i,V_i\ge0$ holds for $i=1$ but not for $i=2$. Here the vertices of $P_{j,k}$ are $(a_1,0)$, $(u_2,0)$, $(0,v_1)$, $(0,v_2), (U_1,V_1)$ -- with the possibility that $(U_1,V_1)=(a_1,0)$, when $a_1=u_1$.  
"Green" case: $v_1\le a_1\le u_2$. Then condition $U_i,V_i\ge0$ holds for both $i=1$ and $i=2$. Here the vertices of $P_{j,k}$ are $(0,v_1)$, $(0,v_2)$, $(U_1,V_1)$, $(U_2,V_2)$ -- with the possibility that $(U_2,V_2)=(0,v_1)$, when $a_1=v_1$.  
"Yellow" case: $v_2\le a_1\le u_2<v_1$. Then condition $U_i,V_i\ge0$ holds for $i=2$ but not for $i=1$. Here the vertices of $P_{j,k}$ are $(0,v_2)$, $(0,a_1)$, $(U_2,V_2)$ -- with the possibility that $(0,v_1)=(0,a_1)=(U_2,V_2)$, when $a_1=v_2$. 
"Red" case: $a_1<v_2$. Then $P_{j,k}=\emptyset$.   
