3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Pat Devlin Apr 28 at 18:47
  • $\begingroup$ 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. $\endgroup$ – Samrat Mukhopadhyay Apr 29 at 2:52
  • $\begingroup$ Are the $p_i$'s nonnegative? $\endgroup$ – Iosif Pinelis Apr 29 at 23:45
  • $\begingroup$ Yes @IosifPinelis. Sorry I forgot to include that important condition earlier in the question. I have included that now. $\endgroup$ – Samrat Mukhopadhyay Apr 30 at 9:13
4
+50
$\begingroup$

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$:

enter image description here

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Samrat Mukhopadhyay Apr 30 at 7:27
  • $\begingroup$ 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? $\endgroup$ – Samrat Mukhopadhyay Apr 30 at 13:37
  • $\begingroup$ I have added a simple algorithm to compute the extreme points of the convex polytopes $P_{J,K}$. $\endgroup$ – Iosif Pinelis Apr 30 at 14:16
  • $\begingroup$ 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. $\endgroup$ – Samrat Mukhopadhyay Apr 30 at 14:17
  • $\begingroup$ 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? $\endgroup$ – Samrat Mukhopadhyay Apr 30 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.