 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/algorithms/2/a/i/solution

Take

u, v \in P

and

0 \leq λ \leq 1

A (λ u + (1 - λ) v) = λ A u + (1 - λ) A v \leq λb + (1 - λ) b = b .

Thus every such convex combination remains in

P

, so $P$ is a convex set. The assertion also holds when

P

is empty.

 New to topics? Read the docs here!