# 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.

• To clarify, do you want an algorithm that takes parameters $p_1, \ldots, p_n$ and also $a_1, q_1,$ and $q_2$ and outputs a list of vertices? Or would you like to quickly test a point $x \in \mathbb{R}^n$ to see if it is a vertex? Or perhaps you would like to know something less computational (like how many vertices this has or where they are). – Pat Devlin Apr 28 at 18:47
• I am more interested in finding a description of the vertices. To elaborate, I want to know what steps I have to go through to find these vertices, for example for the problem with $a_1=\infty$, I know how to find the vertices, as described in the question. So it might be mixture of the first and third points in your comment. – Samrat Mukhopadhyay Apr 29 at 2:52
• Are the $p_i$'s nonnegative? – Iosif Pinelis Apr 29 at 23:45
• Yes @IosifPinelis. Sorry I forgot to include that important condition earlier in the question. I have included that now. – Samrat Mukhopadhyay Apr 30 at 9:13

## 1 Answer

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, so that $$\begin{equation*} 0 Without loss of generality (wlog) $$0 (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. 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. 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. Then $$P_{j,k}=\emptyset$$.

• Thanks for the nice answer. Your reformulation of my problem now asks for finding the vertices of the polytope bounded by two hyperplanes and the coordinate axes. Is there a simple algorithm for that, given the pis, and $q_1,q_2,a_1$? – Samrat Mukhopadhyay Apr 30 at 7:27
• If I apply your argument, that was used to prove that the extreme point nonzero $h_i$'s cannot take more than two distinct positive values, I think I can also prove that if $v_1<a_1$, the extreme point $v$ can have nonzero $v_i$s which can only take the same positive values. Similarly, if $v_1=a_1$, the other nonzero coordinates can take either the value $a_1$ or a distinct positive value. Can you kindly comment on the validity of these observations? – Samrat Mukhopadhyay Apr 30 at 13:37
• I have added a simple algorithm to compute the extreme points of the convex polytopes $P_{J,K}$. – Iosif Pinelis Apr 30 at 14:16
• Thank you for the very nice illustration of the algorithm. It will also be very kind of you if you can verify the validity of my second comment. – Samrat Mukhopadhyay Apr 30 at 14:17
• I was actually arguing as you argued. That is if $v$ is an extremal vertex, then, if $v_1=a_1$, and the rest of the positive coordinates are of, let's say two different values, then one can find nonzero solution for a vector y, on the support of the vector v, such that y satisfies $\sum_i p_iy_i=0.$ Shouldn't this imply that there can be at most one more distinct positive value for $v_i$s? Am I missing anything? – Samrat Mukhopadhyay Apr 30 at 16:19