When we consider a linear programming of the following form:
$$\begin{equation}
\begin{aligned}
\min_{x}
\quad & { c^Tx} \\
\textrm{subject to}
\quad & x\in P \\
\end{aligned}
\end{equation}$$
where $P=\{x\in \mathbb{R}^n:a_i^Tx\leq b_i,~~\forall i=1,2,…,m\}$ denotes a non–empty polyhedron. Suppose we rule out the possibility of the optimal value being $-\infty$. Then we must have an optimal solution on the vertex.
I wanna ask: if we've checked ALL the vertices, and we know there is only one vertex attains the optimal value (aka, other vertices all give strictly higher objective function values). Can we say that the optimal solution is unique given these said?
Or, what further assumptions are needed if we want the statement above is true?
Best Answer
If $P$ is non empty & compact (equivalently, contains no half lines) then the result is true.
The key results are (i) that a compact convex set $C \subset \mathbb{R}^n$ is equal to the convex hull of its extreme points (see Corollary 18.5.1 in Rockafellar, "Convex Analysis", cf. Krein Millman) and (ii) the vertices of a polyhedron are the same as the extreme points (this is not immediate, but straightforward, but I can't find the result in any texts at hand).
Then, if $E$ are the extreme points of $E$ we have $\min_{ x \in P} c^T x = \min_{ x \in \operatorname{co} E} c^T x = \min_{ x \in E} c^T x$.
If $\arg \min_{x \in E} c^Tx$ is a singleton, then so is $\arg \min_{ x \in P} c^Tx$ (otherwise we get a straightforward contradiction). In particular, the solution is unique.
I found a pdf here that shows the equivalence of extreme points, vertices & basic feasible solutions for a polyhedron. Also see Misha Lavrov's notes.