Injective convex polyhedra

. As an application, we prove that if the set of solutions to a linear system of inequalities with at most two variables per inequality is non-empty, then it is injective when endowed with the

l_{i n f t y}

-metric.

Review text

Given \(x \in {\mathbb R}^n\), let \(\| x \|_{\infty} = \max |x_i|\), \(\| x \|_1 = \sum^n_{i=1} |x_i|\), and let \(S \subset {\mathbb R}^n\), endowed with the metric \(d_{\infty}\) defined by \(\| x \|_{\infty}\), be an injective object in the category of metric spaces and distance non-increasing maps. This \((S, d_{\infty})\) is called \textit{injective}. The main results of the paper are devoted to characterization of injective convex polyhedra and injective convex polyhedral cones in terms of their facets and tangent cones (Theorems 1, 2) and Theorem 8. {Let \(P \subset {\mathbb R}^n\) be a convex polyhedron with non-empty interior. Then the following two conditions are equivalent: (i) \(P\) is injective; (ii) \(T_p P\) is injective for every \(p \in \partial P\).} Here \(T_p P\) is the tangent cone to \(P\) at \(p \in \partial P\). The author applies these results to the linear programming in the case of at most two variables per inequality (TVLI). Let \(I_n := \{1,2,\ldots n\}\), \(I_m := \{1,2,\ldots m\}\). Theorem 3. {Consider \(f,g: I_m \to I_n\) and for \(i \in I_m\), \(a_i, b_i, c_i \in {\mathbb R}\) so that \[ P = \bigcap_{i \in I_m} \{x \in {\mathbb R}^n: a_i x_{f(i)} + b_i x_{g(i)} \geq c_i \} \] satisfies \(\mathrm{int}(P) \neq \emptyset\), and \(P \neq {\mathbb R}^n\). Then, \(P\) is injective.} A characterization of injective linear subspaces of \({\mathbb R}^n\) is obtained as well: Theorem 6. Let \(\emptyset \neq X \subset {\mathbb R}^n\) be a linear subspace, \(\dim X=k\). Then, the following conditions are equivalent: (i) \(X \) is injective; (ii) There is a subset \(J \subset I_n\), with \(|J| = k\) such that for any \(i \in I_n \setminus J\) there exist real numbers \(\{\alpha (i,j) \}_{j \in J}\) such that \(\sum_{j \in J} |\alpha (i,j)| \leq 1\) and such that \[ X = \{x\in {\mathbb R}^n: \text{ for all } i \in I_n \setminus J,\, x_i = \sum_{j \in J} \alpha (i,j) x_j \}. \] In particular, Theorem 7. Let \(\nu \in {\mathbb R}^n \setminus \{0\}\). The hyperplane \(X=\{x\in {\mathbb R}^n: x \cdot \nu = 0 \} \subset {\mathbb R}^n\) is injective if and only if \(\| \nu \|_1 \leq 2 \|\nu \|_{\infty}\). Here \(x \cdot \nu\) is the standard scalar product. Reviewer's remark: It seems to the reviewer that on the page 593, line 8, one should read ``satisfying \(r_y + r_z \geq d_{\infty} (y,z)\) for every \(y,z \in Y\), not ``\(r_y + r_z \geq d_{\infty} (x,z)\) since there are no ``\(x\) in these considerations.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Injective convex polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q331374)