 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$$.
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: Let $$P \subset \mathbb{R}^n$$ be a polytope and let $$f : P \rightarrow \mathbb{R}$$ be a convex function. Consider the optimisation problem $$\text{max } f(x) \text{ s.t. } x \in P$$ and let $$x \in P$$ be an optimal solution. Suppose $$x$$ is not a vertex of $$P$$. Then, by the equivalence of vertices and extreme points, we know that $$x$$ can be written as $$x = \lambda y + (1-\lambda)z$$ with $$\lambda \in (0,1)$$ and $$y, z$$ are vertices of $$P$$. Now, by definition of a convex function we get $$f(x) = f(\lambda y + (1-\lambda)z) \leq \lambda f(y) + (1-\lambda) f(z)$$. The latter implies that either $$f(x) \leq f(y)$$ or $$f(x) \leq f(z)$$ or both. In other words, either $$y$$ or $$z$$ or both will also be optimal.