Let $\mathcal{P} \subset \mathbb{R}^d_+$ be a polytope. I want to define the "lower boundary" of $\mathcal{P}$, which we'll call $\ell(\mathcal{P})$. Here's a picture of what I have in mind.
I assume this object has been studied already in linear programming or convex analysis.
Question 1: Can someone point me to a reference that discusses this "lower boundary" of $\mathcal{P}$?
My main question is regarding two definitions I have for $\ell(\mathcal{P})$, which I believe to be equivalent. To state these definitions, we'll need to introduce the component-wise ordering. For two vectors $x,y \in \mathbb{R}^d$, we write that $x \preceq y$ if $x(i) \leq y(i)$ for all components $i=1 \dots d$. The relation $\prec$ is defined analagously. Here are the two possible definitions for $\ell(\mathcal{P})$:
\begin{align} A &= \{ x \in \mathcal{P} : \not\exists y \in \mathcal{P} \text{ such that } y \prec x \} \\ B &= \bigcup_{\substack{c \succeq 0 \\ c \neq 0}} \text{argmin}_{x \in \mathcal{P}} \langle c , x \rangle \end{align}
Question 2: Is it true that $A = B$?
I know that $B \subset A$. We can show this by proving the contrapositive; that is, if $x \notin A$ then $x \notin B$. If $x \notin A$ then there exists $y \in \mathcal{P}$ such that $y \prec x$. Then, for all linear functions $c \succeq 0$ (with $c \neq 0$), we have that $$ \langle c , y \rangle < \langle c , x \rangle $$ so that $x$ is not a minimizer over $\mathcal{P}$ for any of these linear functions. Thus, $x \notin B$.
The other direction $A \subset B$ is harder to prove. If you want to show it directly by showing $x \in A \rightarrow x \in B$, then you need to construct a linear function $c$ for which $x$ is the minimizer over $\mathcal{P}$. This seems challenging if all the information we have is that there is no $y \in \mathcal{P}$ such that $y \prec x$. On the other hand, proof by contrapositive ($x \notin B \rightarrow x \notin A$) has similar challenges because we would need to construct a $y \in \mathcal{P}$ so that $y \prec x$ knowing only that $x$ is not a minimizer for any of these linear functions $c \succeq 0$.
I think that $A = B$ but perhaps my intuition in two dimensions is throwing me off here.
Thanks to Sekhar Tatikonda for pointing out to me that the other direction can be proved using the separating hyperplane theorem. In short, the separating hyperplane theorem allows us to, given $x \in A$, existentially obtain the linear function $c$ in the definition of $B$. In this argument, the convexity of the set is the important part; the fact that it is polyhedral doesn't really matter. For this reason, let me re-state the claim.
Claim: Let $\mathcal{C}$ be a non-empty convex set in the positive orthant $\mathbb{R}^d_+$. Then, $$ A \triangleq \{ x \in \mathcal{C} : \not\exists y \in \mathcal{C} \text{ such that } y \prec x \} = \bigcup_{\substack{c \succeq 0 \\ c \neq 0}} \text{argmin}_{x \in \mathcal{C}} \langle c , x \rangle \triangleq B $$
Proof: First, we show that $B \subset A$ by proving the contrapositive; that is, if $x \notin A$ then $x \notin B$. If $x \notin A$ then there exists $y \in \mathcal{C}$ such that $y \prec x$. Then, for all non-negative linear functions $c \succeq 0$ (with $c \neq 0$), we have that $$ \langle c , y \rangle < \langle c , x \rangle $$ so that $x$ is not a minimizer over $\mathcal{C}$ for any of these linear functions. Thus, $x \notin B$.
Next, we show that $A \subset B$ directly, by a separating hyperplane argument to prove the existence of a linear function $c$ we want to use. Let $x \in A$ be given. Define $F_x = \{ y \in \mathbb{R}^d : y \prec x \}$. Because $x \in A$, there is no element $y \in \mathcal{C}$ such that $y \prec x$, which means that $F_x \cap \mathcal{C} = \emptyset$. Observe also that the set $F_x$ is convex and and nonempty, where non-emptiness follows from the fact that $\mathcal{C}$ is in the non-negative orthant. Because the two sets $F_x$ and $\mathcal{C}$ are disjoint and convex, there exists a separating hyper plane between them. That is, there exists a vector $c \in \mathbb{R}^d$ and scalar $\alpha$ so that \begin{align} \langle c, y \rangle \leq \alpha &\text{ for all } y \in F_x \\ \langle c, y \rangle \geq \alpha &\text{ for all } y \in \mathcal{C} \end{align} To continue, we need a small Lemma which we prove later.
Lemma 1: The vector $c$ satisfies $c \succeq 0$, $c\neq 0$ and $\alpha = \langle c , x \rangle$. (proven below)
Now, we claim that $x \in \text{arg}\min_{y \in \mathcal{C}} \langle c , y \rangle$. For sake of contradiction, suppose that there is an element $x^* \in \mathcal{C}$ with strictly smaller objective value. Together with Lemma 1, this means that $$ \langle c, x^* \rangle < \langle c , x \rangle = \alpha.$$ But we have reached a contradiction because by the property of the separating hyperplane, this implies that $x^* \notin \mathcal{C}$. Therefore, $x \in \text{arg}\min_{y \in \mathcal{C}} \langle c , y \rangle$. By Lemma 1, $c \succeq 0$ and $c \neq 0$ so $x \in B$. $\square$
Proof of Lemma 1 Obviously, $c \neq 0$ because otherwise the hyperplane cannot be separating. Now let's show that $c \succeq 0$. For sake of contradiction, suppose that the $i$th coordinate of $c$ is negative, i.e. $c(i) < 0$. Let an arbitrary $z \in F_x$ be given. For any $\beta > 0$, $ z - \beta e_i \preceq z \prec x$ so that $z - \beta e_i \in F_x$. Thus, by the separating hyperplane, $$ \langle c , z - \beta e_i \rangle \leq \alpha.$$ However, for any $\beta > \frac{\alpha - \langle c , z \rangle}{|c(i)|}$, we have that $$ \langle c , z - \beta e_i \rangle = \langle c , z \rangle - \beta \langle c , e_i \rangle = \langle c , z \rangle + \beta |c(i)| > \alpha $$ which contradicts the separating property of the hyperplane. Thus, $c \succeq 0$.
Finally, we show that $\langle c , x \rangle = \alpha$. Define the sequence $\{ y_k \}_{k=1}^\infty \in F_x$ by $ y_k = x - \frac{1}{k} \mathbf{1}$. Clearly, $\lim y_k \rightarrow x$ and so $$ \lim \langle c , y_k \rangle \rightarrow \langle c , x \rangle $$ Thus, if $\langle c , x \rangle > \alpha$, then there exists $k$ such that $\langle c , y_k \rangle > \alpha$. This violates the separating hyperplane property, as $y_k \in F_x$. Thus, $\langle c , x \rangle = \alpha$. $\square$
It's worth noting too that this argument works for general conic inequalities $\preceq$.