 ## 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: ...

## math - dimensions film

There is a math film called Dimensions that was made for a wide audience. I have not watched it yet, but it can be downloaded for free and the images on the web page seem very promising. Do not forget that we still have the year of mathematics.

## Geometrie und Revolte

Am 26. März bringt Deutschlandradio Kultur eine Sendung über Alexander Grothendieck mit dem Titel: "Geometrie und Revolte - Die radikale Wende im Leben des Mathematikers A.G." Ein Fields-Medaillen Gewinner, der politisch sehr engagiert war, seit zwei Jahrzehnten aber völlig aus dem öffentlichen Leben verschwunden ist.