I have a question on convex analysis, which I require in one step of my research work. Before stating it, let me give a small background.

Let $Y, X_1,\ldots,X_n$ be $n+1$ points in $\mathbb{R}^d$. Denote the convex hull of $X_1,\ldots,X_n$ by $C(X_1,\ldots,X_n)$. Suppose that someone is interested in finding a condition equivalent to saying that $Y \notin C(X_1,\ldots,X_n)$. An easy consequence of the separating hyperplane theorem gives one such equivalent condition, which is, "$\exists v \in \mathbb{R}^d$ such that $v^\top(Y-X_i) > 0$ for all $1\leq i\leq n$." This alternative characterization is helpful when, for instance, one is given all the points $Y,X_1,\ldots,X_n$, and he/she wishes to check whether $Y \in C(X_1,\ldots,X_n)$ or not, by implementing a linear program (he/she simply determines the feasibility of the program, which maximizes an arbitrary constant objective, say the constant function $1$, subject to the equivalent constraint described above).

Okay, so this concludes the background part. Now, coming to my problem, let's define: $$\hat{C}(X_1,\ldots,X_n) := \{Z \in \mathbb{R}^d: X \preccurlyeq Z~\textrm{for some}~X \in C(X_1,\ldots,X_n)\}~,$$ where for two points $A=(A^1,\ldots,A^d)$ and $B=(B^1,\ldots,B^d) \in \mathbb{R}^d$, the notation $A \preccurlyeq B$ denotes that $A_i \leq B_i$ for all $1\leq i \leq d$. It is convenient to call $\hat{C}(X_1,\ldots,X_n)$, the $upper ~orthant$ of $C(X_1,\ldots,X_n)$ (one can quickly visualize how this set looks like in $\mathbb{R}^2$, to get a better geometric feeling; if you call the direction $y=\infty$ North, then you just take those $X_i$'s in the $\textit{South-West part}$ of $C(X_1,\ldots,X_n)$ which are incomparable with each other in the $\preccurlyeq$ ordering, draw a vertical ray originating from the highest such point and a horizontal ray originating from the incomparable point with the largest $x-$coordinate, and consider the area bounded by these two rays and the incomparable points, in the North-East direction).

My question is, can you give me an equivalent condition to the statement $Y \notin \hat{C}(X_1,\ldots,X_n)$, which is similar in spirit to the alternative characterization described in my background (in the sense that the characterization can be looked upon as the constraints in a linear program in some auxiliary variable(s) $v$)?

I understand that my question is not very direct, but that's how research is! However, feel free to ask me to be more precise, if you need. Thanks for your help in advance!


I think I could solve the problem I posted above. The characterization remains the same, with the additional assumption that the vector $v$ has all entries non-negative. By the way, thanks for your efforts.

  • $\begingroup$ Please: if you have a solution to your question, then that is what should be posted here. Not an assurance that you know how to do it; that is of no use to the community. Finally, the last sentence smacks of sarcasm. $\endgroup$ – Todd Trimble Feb 13 '19 at 12:40

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.