Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 2 / a

Take $u,v\in P$ and $0\le \lambda \le 1$. Their convex combination satisfiesThus every such convex combination remains in $P$, so $P$ is a convex set. The assertion also holds when $P$ is empty.

An extreme point $p\in P$ cannot be written as a nontrivial convex combination of two distinct points of $P$: if $p=\lambda u+(1-\lambda )v$ with $u,v\in P$ and $0<\lambda <1$, then $u=v=p$.

A vertex of a linear polyhedron is a feasible point at which the active constraints include $n$ linearly independent row normals. Equivalently, some $n$ independent bounding hyperplanes intersect uniquely at that point. This definition does not require $P$ to be bounded or full-dimensional. For a linear polyhedron, it is also equivalent to the point uniquely maximizing a suitable linear function: sum the selected active inequalities to construct one such linear function.

Let $p$ be a vertex of a linear polyhedron and choose $n$ independent active constraints, written $Bp=d$, with $B$ invertible. Suppose $p=\lambda u+(1-\lambda )v$, where $u,v\in P$ and $0<\lambda <1$. Each selected inequality has $B_{i}u\le d_i$ and $B_{i}v\le d_i$, whileSince both weights are positive, equality in this weighted upper bound forces $B_{i}u=B_{i}v=d_i$ for every selected row. Hence $Bu=Bv=d$, and invertibility gives $u=v=p$. Therefore every vertex of a linear polyhedron is an extreme point.

No. For the linear polyhedron $P=[0,1{]}^2$, take $c=(1,0{)}^T$ and $x^{\ast }=(1,1/2{)}^T$. The maximum of $c^{T}x$ is one, attained at $x^{\ast }$. Yetso $x^{\ast }$ is not an extreme point, hence not a vertex of a linear polyhedron. An optimal face can contain many points; an arbitrary maximizer need not be one of its vertices of a linear polyhedron.