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.

Trackbacks

No Trackbacks

Comments

Display comments as Linear | Threaded

education articles on :

Vertex is also sometimes used to indicate the 'top' or high point of something, like the vertex of an isosceles triangle , which is the 'top' corner opposite its base as well this is not its strict mathematical definition.

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