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


No Trackbacks


Display comments as Linear | Threaded on :

Does a convex objective subject to a polytope attain its optimum at a vertex, Make things more good at the place when you are facing to get convex objects ever with the help of polytope attain. You have much information in all the place.

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