Skip to content

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

Movie recommendation

Watched this one a few days ago. I came across it because it won the 'Palme d'Or' and several European film awards. The trailer really hooked me and I was very happy when I found out that it's currently on Netflix.

Simplicity

"With constant pressure to add features and options and configurations, and to ship code quickly, it's easy to neglect simplicity, even though in the long run simplicity is the key to good software. Simplicity requires more work at the beginning of a project to reduce an idea to its essence and more discipline over the lifetime of a project to distinguish good changes from bad or pernicious ones. With sufficient effort, a good change can be accommodated without compromising what Fred Brooks called the 'conceptual integrity' of the design but a bad change cannot, and a pernicious change trades simplicity for its shallow cousin, convenience. Only through simplicity of design can a system remain stable, secure, and coherent as it grows." (Preface, The Go Programming Language)