## Does a convex objective subject to a polytope attain its optimum at a vertex?

Today, while thinking about a work-related optimisation problem, I asked myself whether, given a domain corresponding to a nonempty polytope $$P$$ and a convex objective, is there always an optimal solution which is a vertex of $$P$$ ?

To warm up let's look at the linear programming case first. Given a nonempty polytope $$P = \{x \in \mathbb{R}^n: Ax \geq b \}$$ and a linear objective $$c \in \mathbb{R}^n$$ it's well known that there is a vertex $$v \in P$$ which is optimal for $$\text{min } c \cdot x \text{ s.t. } x \in P$$. We can prove this as follows: Let $$Q$$ be the set of all optimal solutions and let $$w \in \mathbb{R}$$ be the optimal objective value. Then, $$Q = \{ x \in \mathbb{R}^n : Ax \geq b, c \cdot x = w \}$$ is itself a polytope. Since $$Q \subset P$$, it does not contain any lines implying it has at least one vertex. Let $$v \in Q$$ be a vertex of $$Q$$. We show that $$v$$ is also a vertex of $$P$$. Suppose $$v$$ is not a vertex of $$P$$. Then, there are $$x, y \in P$$ such that $$x \neq v, y \neq v$$ and some $$\lambda \in [0,1]$$ such that $$v = \lambda x + (1-\lambda)y$$. Moreover, we get $$w = c \cdot v = \lambda c \cdot x + (1-\lambda) c \cdot y$$. The latter can be used to show that $$x \in Q$$ and $$y \in Q$$ which contradicts that $$v$$ is a vertex of $$Q$$.

Given a convex objective function, it turns out that we have to distinguish between minimisation and maximisation unlike in the linear programming case.

Minimisation: Let the polytope $$P \subset \mathbb{R}^2$$ be given by the convex combination of the four vertices $$(1,0), (0,-1), (-1,0), (0,1)$$ and let $$f : P \rightarrow \mathbb{R}$$ be given by $$f(x) = x_1^2 + x_2^2 + x_1 x_2.$$ Consider $$\text{min } f(x) \text{ s.t. } x \in P$$. It's not hard to see that none of the vertices corresponds to an optimal solution which is given by the interior point $$(0,0) \in P$$. In other words, if we minimise a convex function subject to a polytope, then we can generally not assume that an optimal solution is given by a vertex.

Maximisation: ... 