Analyzing lexicographical linear inequality systems via convex hulls

Abstract

<jats:p> Lexicographical extensions of well-known separation theorems for convex sets in <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathbb {R}^n$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula> are provided in the literature. Particularly, recent theorems regarding open and closed separation of a convex set from any outside point by linear operators from <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathbb {R}^n$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula> to <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathbb {R}^m$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula> , in the sense of the lexicographical order of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathbb {R}^m$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula> , for each <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$m\in \{1,\ldots ,n\}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> , allow to define two new families of properties for convex sets. Based on these results, that we review and extend in this paper, we provide dual characterizations for the consistency of two kinds of systems defined by weak and/or strict lexicographical linear inequalities, and for those inequalities which are satisfied for every solution of a given system. Such results are formulated in terms of appropriate convex hulls of certain sets depending on the coefficients of the system. </jats:p>