This blog is talking about the relation between extreme points and optimality of LO Problem.

Let’s first we study the relation between extreme points and optimality through following theorem.

Theorem: Consider the problem of minimizing ${ \bar{x} \mapsto \bar{c}^\top \bar{x} }$ over a polyhedron ${ P = \{\bar{x} \in \mathbb{R}^n \mid A \bar{x} \geq \bar{b}\} }$ possessing at least one extreme point. Then

1. either the optimal cost is equal to ${ -\infty }$

2. or the optimal cost is attained at an extreme point. (possibly at more than one extreme point)

Proof of the theorem

Given a point ${ \bar{p} \in P }$, let ${ I_{\bar{p}} = \{i \mid \bar{a_i}^\top \bar{p}= b_i\} }$. The number of dim ${span \{\bar{a_i} \mid i \in I_{\bar{p}} \} }$ will be called the type of ${ \bar{p} }$.

Let’s assume that the optimal cost is finite (i.e. optimal cost is not ${ -\infty }$).

We will show following claim

Claim Given a point ${ \bar{p} \in P }$ of type ${ k < n }$, ${ \exists }$ a point ${ \bar{q} \in P }$ which has greater type and such that ${ \bar{c}^\top \bar{q} \leq \bar{c}^\top \bar{p} }$.

Proof. Since ${ k<n }$, so ${ span \{\bar{a_i} \mid i \in I_{\bar{p}}\} \subsetneq \mathbb{R}^n}$ and we can choose ${ \bar{d} \in \left( span \{\bar{a_i} \mid i \in I_{\bar{p}}\}\right)^\perp, \bar{d} \neq \bar{0} }$.

Without loss generality, we can assume that ${ \bar{c}^\top \bar{d} \leq 0 }$ (because if ${ \bar{c}^\top \bar{d} > 0 }$, then we have ${ \bar{c}^\top (- \bar{d}) < 0 }$).

Case 1: suppose ${ \bar{c}^\top \bar{d} < 0 }$, consider the half line ${ \bar{p} + \lambda \bar{d}, \lambda \in [0,+\infty) }$. For ${ i \in I_{\bar{p}} }$, we have ${ \bar{a_i}^\top (\bar{p} + \lambda \bar{d}) = \bar{a_i}^\top \bar{p} + \lambda \bar{a_i}^\top \bar{d} = \bar{a_i}^\top \bar{p} +0 = b_i }$.

Hence, all the constraints active at ${ \bar{p} }$ are still active at every point of the half line.

Since ${ \bar{c}^\top \bar{d} < 0 }$, the cost ${ \bar{c}^\top (\bar{p} + \lambda \bar{d}) }$ decrease as ${ \lambda }$ increases.

The half line must eventually exit ${ P }$, otherwise the optimal cost is ${ - \infty }$.

The last point on the half line before exiting ${ P }$ is ${ \bar{q} := \bar{p} + \lambda ^* \bar{d} }$ for some ${ \lambda^* > 0 }$. At that point ${ \bar{q} }$, one of the constraints not active in ${ \bar{p} }$ must become active i.e. ${ \bar{a_j}^\top \bar{q} = b_j }$ for some ${ j \notin I_{\bar{p}} }$.

And, we note that ${ \bar{c}^\top \bar{q} = \bar{c}^\top \bar{p} + \lambda^* \bar{c}^\top \bar{d} < \bar{c}^\top \bar{p}}$.

So the type of ${ \bar{q} }$ is at least ${ k+1 }$.

Case 2: suppose ${ \bar{c}^\top \bar{d} = 0 }$. The line ${ \bar{p} + \lambda \bar{d}, \lambda \in \mathbb{R} }$ must exit ${ P }$, otherwise ${ P }$ contain a line. Furthermore, the last point ${ \bar{q} }$ has same properties like above discussion. And ${ \bar{c}^\top \bar{q} = \bar{c}^\top \bar{p}}$.

So, we prove the claim.

By claim, we can repeat this process as many times as needed, we end up with a vector ${ \bar{w} \in P }$ of type ${ n }$ such that ${ \bar{c}^\top \leq \bar{c}^\top \bar{p} }$. Note that ${ \bar{w} }$ is a basic feasible solution.

In other words, given any point ${ \bar{p} \in P }$, there exist an extreme point ${ \bar{w} }$ such that ${\bar{c}^\top \bar{w} \leq \bar{c}^\top \bar{p} }$.

It’s clear we have finite basic feasible solutions, denoted as ${ \bar{w_1},\cdots,\bar{w_\ell} }$. Let ${ \bar{w}^* }$ be the bfs with smallest cost. So, given any point ${ \bar{p} }$, we will find ${ \bar{w_i} }$ such that ${ \bar{c}^\top \bar{w_i} \leq \bar{c}^\top \bar{p} }$, So, ${ \bar{c}^\top \bar{w}^* \leq \bar{c}^\top \bar{w_i} \leq \bar{c}^\top \bar{p} }$, hence ${ \bar{w}^* }$ is optimal. ${ \square }$

Corollary

Corollary: Consider the problem of minimizing ${ \bar{x} \mapsto \bar{c}^\top \bar{x}}$ over a non-empty polyhedron ${ P }$. Then

1. either the optimal cost is equal to ${ -\infty }$

2. or there exists an optimal solution.

Proof. If ${ P }$ possesses an extreme point, then by above theorem we get the conclusion. If ${ P }$ doesn’t have extreme point, we can transform it to equivalent LO problem in standard form. And we known the new problem has extreme point and we can use above theorem to get proof. ${ \square }$