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

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.

Only $z,w$ have printed nonnegativity restrictions; $x,y$ are unrestricted. In four-dimensional space, a vertex of a linear polyhedron needs four independent active constraints. There are exactly four available constraints, so all must be active. Solving them givesand therefore the only possible vertex of a linear polyhedron is $(x,y,z,w)=(2,3,0,0)$. It is feasible, and its four active normals are independent, so it is indeed a vertex of a linear polyhedron.

One can also see uniqueness geometrically from the slack variables $s_1=1-2x+y-5w$ and $s_2=3-y-z-w$. The feasible region is in affine bijection with the nonnegative orthant in $(s_1,s_2,z,w)$:That orthant has only the origin as an extreme point, giving the same unique vertex of a linear polyhedron.

Use the standard maximum form of a linear program convention $\max c^{T}u$ subject to $Mu\le b$ and $u\ge 0$. Split the unrestricted variables as $x=x^{+}-x^{-}$ and $y=y^{+}-y^{-}$, with all four new variables nonnegative. The resulting linear program isIf equality-constraint standard form is preferred, add a nonnegative slack variable to each inequality.

Give the two inequalities nonnegative dual variables $\alpha ,\beta$. The dual linear program isThe paired inequalities encode equalities for the two original unrestricted variables. Equivalently, the dual linear program has $2\alpha =2$, $-\alpha +\beta =3$, $\beta \ge 4$, $5\alpha +\beta \ge 7$ and $\alpha ,\beta \ge 0$. Thus its only feasible point is $(\alpha ,\beta )=(1,4)$, of objective function value $13$.

The point $(1,4)$ satisfies dual feasibility and supplies an upper bound of $13$ by weak duality. Directly, take one copy of the first constraint and four copies of the second:Since $w\ge 0$, the original objective function is at most $13-2w\le 13$. The feasible point $(2,3,0,0)$ attains $13$. HenceThere are also nonvertex optima. In terms of the slack variables, the exact objective function identity isEquality requires $s_1=s_2=w=0$, leaving the entire optimal faceNegative $x$ or $y$ on this ray are allowed. This illustrates why the single vertex of a linear polyhedron does not imply a unique optimum.

First suppose the stated nonnegative vectors $y,z$ exist. If $x\in P\cap Q$, multiply $Ax\le b$ by $y^T$ and $Cx\le d$ by $z^T$. Since $x\ge 0$ and $y^{T}A+z^{T}C\ge 0$, this gives the contradictionThus the certificate implies $P\cap Q=\varnothing$.

For the converse, putA common feasible point exists exactly when $Mx\le h$, $x\ge 0$. Introducing a nonnegative vector of slack variables $s$ makes this equivalent toIf this system is infeasible, the nonnegative-equations version of Farkas' lemma supplies an unrestricted vector $u$ such thatSplit $u=(y,z{)}^T$ according to the original two blocks of inequalities. The three conditions become $y,z\ge 0$, $y^{T}A+z^{T}C\ge 0$ and $y^{T}b+z^{T}d<0$, exactly the desired certificate. Both directions are proved. The role of $x\ge 0$ is essential: it is why the combined normal need only be nonnegative rather than zero.^[ref]

Let $B=A^T$ and choose any column probability vector $q$, for example the first coordinate unit vector. Because $A$ has nonnegative entries and each row sums to one, $B$ maps the probability simplexinto itself: $Bv\ge 0$ and $1^{T}Bv=(A1{)}^{T}v=1^{T}v=1$.

The iterates $B^{j}q$ need not converge, so take their arithmetic averages,A telescoping sum givesBoth vectors on the right before subtraction have L1 norm one, so $\Vert B{x}_N-x_N{\Vert }_1\le 2/N\to 0$.

The probability simplex is closed and bounded in finite-dimensional Euclidean space, hence compact by the Heine-Borel theorem. It follows that a subsequence $x_{N_j}$ converges to some $x\in \Delta$. Passing to the limit in the displayed identity, using continuity of the linear map $B$, gives $A^{T}x=Bx=x$, with $x\ge 0$ and ${\sum }_i{x}_i=1$.

This proves stationary distribution existence for a finite Markov chain without any Markov chain irreducibility or aperiodicity assumption. Those stronger hypotheses concern uniqueness and convergence, not the existence required here.