Convex polytopes and linear programming

[16/75%]

Show

LaTeX

Show LaTeX

Problem 236 from Kirillov A.A., Gvishiani A.D. "Теоремы и задачи функционального анализа" [KiGv88]More problems in Subsection III.1.2 "Dual Spaces"

Suppose that the unit ball $B$ of the normed space $L$ is a convex polyhedron. Construct a natural correspondence between the $k$ -dimensional faces of $B$ and the $(n-k)$ -dimensional faces of the unit ball $B'$ in $L'$ .

Problem 3.5.31 from Кудрявцев Л.Д., Кутасов А.Д., Чехлов В.И., Шабунин М.И. "Функции многих переменных" [ККЧ+03]More problems in Subsection 3.5.2 "Problems"

(1)(2)(3)(4)

Find the greatest value $M$ and the smallest value $m$ of the function $u$ on the given set.

(1)

$u = x+2 y+3 z, x+y \leqslant 3, x+y \leqslant z, 3 x+3 y \geqslant z, x \geqslant 0$ , $y \geqslant 0$

(2)

$u = 3 z-y-2 x, x+y \geqslant 2,3 x+y \leqslant 6,0 \leqslant z \leqslant 3, x \geqslant 0$ ;

(3)

$u = x+y+z, x^{2}+y^{2} \leqslant z \leqslant 1$

(4)

$u = x^{2}+2 y^{2}+3 z^{2}, x^{2}+y^{2}+z^{2} \leqslant 100$ .

Problem 50.2 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

Prove that a subset of a flat $P$ of an affine space $A$ is a convex polytope in $P$ if and only if it is a convex polytope in $A$ .

Problem 50.3 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

Let a convex polytope $M$ in an affine space be given by a system of linear inequalities

f_{i}(x) \geqslant 0 \quad \left(i=1, \ldots , k ; \quad f_{i} \neq \text{ const }\right).

Prove that for every nonempty subset $J \subseteq \left\{ 1, \ldots , k\right\}$ the set $M^{J}$ , defined by the conditions $f_{i}(x)=0$ for $i \in J, f_{i}(x) \geqslant 0$ for $i \notin J$ , if nonempty, is a face of the polytope $M$ , and, conversely, every face of the polytope $M$ has the form $M^{J}$ for some set $J \subseteq \left\{ 1, \ldots , k\right\}$ .

Problem 50.7 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

Find the vertices and describe the shape of the convex polytope in a three-dimensional affine space given by the inequalities

\begin{gathered} x_{1} \leqslant 1, \quad x_{2} \leqslant 1, \quad x_{3} \leqslant 1 \\ x_{1}+x_{2} \geqslant -1, \quad x_{1}+x_{3} \geqslant -1, \quad x_{2}+x_{3} \geqslant -1. \end{gathered}

Problem 50.25 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

Prove that the maximum of an affine linear function on a compact convex set is attained at some extreme point (but may also be attained at other points).

Problem 50.26 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

Prove that the extreme points of a convex polytope are its vertices.

Problem 50.27 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

Prove that every bounded convex polytope coincides with the convex hull of the set of its vertices.

Problem 50.28 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

Prove that the convex hull of a finite number of points is a convex polytope.

Problem 50.29 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

(a)(b)

Give, by a system of linear inequalities, the convex hull of the indicated points of a four-dimensional affine space, and find the three-dimensional faces of this convex polytope:

(a)

$O=(0,0,0,0), \quad a=(1,0,0,0), \quad b=(0,1,0,0)$ , $c=(1,1,0,0), \quad d=(0,0,1,0), \quad e=(0,0,0,1), \quad f=(0,0,1,1) ;$

(b)

$O=(0,0,0,0), \quad a=(1,0,0,0), \quad b=(0,1,0,0)$ , $c=(0,0,1,0), \quad d=(1,1,0,0), \quad e=(1,0,1,0), \quad f=(0,1,1,0)$ , $g=(1,1,1,0), \quad h=(0,0,0,1)$ .

Problem 50.33 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

(a)(b)

Let $F$ be an affine bilinear function on the direct product of affine spaces $A$ and $B$ , and let $M$ and $N$ be compact convex subsets of the spaces $A$ and $B$ , respectively.

Prove that:

(a)

$\max_{x \in M} \min_{y \in N} F(x, y)=\min_{y \in N} \max_{x \in M} F(x, y)$ ;

(b)

there exist points $x_{0} \in M, y_{0} \in N$ such that for all $x \in M$ , $y \in N$

F\left(x, y_{0}\right) \leqslant F\left(x_{0}, y_{0}\right) \leqslant F\left(x_{0}, y\right).

Problem 50.35 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

Determine whether the polytopes given by the following inequalities are bounded:

(a)

$-3 x_{1}+5 x_{2} \leqslant 10, \quad 5 x_{1}+2 x_{2} \leqslant 35, \quad x_{1} \geqslant 0, \quad x_{2} \geqslant 0 ;$

(b)

$-x_{1}+x_{2} \leqslant 2, \quad 5 x_{1}-x_{2} \leqslant 10$ ;

(c)

$3 x_{1}-x_{2} \geqslant 4, \quad -x_{1}+3 x_{2} \geqslant 4$ ;

(d)

$-3 x_{1}+4 x_{2} \leqslant 17, \quad 3 x_{1}+4 x_{2} \leqslant 47, \quad x_{1}-x_{2} \leqslant 4, \quad x_{1}+x_{2} \geqslant 0$ ;

(e)

$-x_{1}+2 x_{2} \leqslant 6, \quad 5 x_{1}-2 x_{2} \leqslant 26, \quad x_{1}+2 x_{2} \geqslant 10$ ;

(f)

$5 x_{1}-2 x_{2} \geqslant 6, \quad 5 x_{1}-2 x_{2} \leqslant 36, \quad 2 \leqslant x_{1} \leqslant 7$ .

Problem 50.36 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

(a)(b)(c)(d)

Find the vertex points of the polytopes:

(a)

$x_{1}+2 x_{2}+x_{3}+3 x_{4}+x_{5}=5, \quad x_{1}+x_{3}-2 x_{4}=3$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0 ;$

(b)

$x_{1}+x_{2}-x_{3}=10, \quad x_{1}-x_{2}+7 x_{3}=7$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0 ;$

(c)

$4 x_{1}+5 x_{2}+x_{3}+x_{4}=29, \quad 6 x_{1}-x_{2}-x_{3}+x_{4}=11$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0 ;$

(d)

$x_{1}+2 x_{2}+x_{3}=4, \quad 2 x_{1}+2 x_{2}+5 x_{3}=5$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0$ .

Problem 50.37 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 50 "Convex sets"

(a)(b)(c)(d)

Find the maximum and minimum values of the linear function $z$ on a bounded polytope:

(a)

$x_{1}+2 x_{2}+x_{3}+3 x_{4}+x_{5}=5, \quad 2 x_{1}+x_{3}-2 x_{4}=3$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0$ , $z=x_{1}-2 x_{2}+x_{3}+3 x_{5}$ ;

(b)

$3 x_{1}-x_{2}+2 x_{3}+x_{4}+x_{5}=12, \quad x_{1}-5 x_{2}-x_{4}+x_{5}=-4$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0$ , $z=4 x_{1}-x_{2}+2 x_{3}+x_{5} ;$

(c)

$5 x_{1}+2 x_{2}-x_{3}+x_{4}+x_{5}=42, \quad 4 x_{1}-4 x_{2}+x_{3}+x_{4}=16$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0$ , $z=x_{1}-2 x_{2}+4 x_{4}-x_{5}$ ;

(d)

$x_{1}-3 x_{2}+x_{3}+2 x_{5}=8, \quad 4 x_{2}-3 x_{4}-x_{5}=3$ , $x_{1} \geqslant 0, \quad x_{2} \geqslant 0, \quad x_{3} \geqslant 0, \quad x_{4} \geqslant 0, \quad x_{5} \geqslant 0$ , $z=x_{1}-2 x_{2}+x_{3}-x_{5}$ .

Problem II.7.3.1 from Кострикин А.И. "Линейная алгебра" [Кос00]More problems in Section II.7.3 "Convex polyhedra and linear programming"

Prove that every bounded polytope is the convex hull of the set of its vertices.

Problem II.7.3.2 from Кострикин А.И. "Линейная алгебра" [Кос00]More problems in Section II.7.3 "Convex polyhedra and linear programming"

Using Exercise 1 and Theorem 13 from § 3, Ch. 4, prove that the maximum of a linear function on a bounded polytope is attained at one of its vertices.

References

[KiGv88] Kirillov A.A., Gvishiani A.D. Теоремы и задачи функционального анализа. 2-е изд., Наука, 1988.

[ККЧ+03] Кудрявцев Л.Д., Кутасов А.Д., Чехлов В.И., Шабунин М.И. Функции многих переменных. 2-е изд., ФИЗМАТЛИТ, 2003.

[Кос15] Кострикин А.И. Сборник задач по алгебре. МЦНМО, 2015.

[Кос00] Кострикин А.И. Линейная алгебра. ФИЗМАТЛИТ, 2000.