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


No Trackbacks


Display comments as Linear | Threaded

No comments

Add Comment

Standard emoticons like :-) and ;-) are converted to images.
You can use [geshi lang=lang_name [,ln={y|n}]][/geshi] tags to embed source code snippets.
Markdown format allowed
Form options