Linear program with unknown constraints(just extreme points)

Question

Suppose you are given a set $F$ consisting of $n$ mutually distinct bounded points in $\mathbb{R}^d$. We can define a linear program
\begin{align}\max \ c^Tx \\\text{s.t.}\ \ x \in \text{Hull}(F)\end{align}
where $\text{Hull}$ denotes the convex hull and $c\in\mathbb{R}^d$ is arbitrary.

How can we solve this linear program by leveraging the fact that we already know all of the extreme points of the feasible region?

Ideally we are looking for a solution that does not require defining constraints and then running Simplex or Interior Point Methods and that performs better than exhaustive search in the best case, i.e. given a good initial guess.

Answer 1

The fastest method is to go over all points in $F$ and compute the objective values, which takes $\mathcal{O}(nd)$ steps, with $n$ the cardinality of $F$.

Suppose you are told that the optimum is $x^*$ or has an objective value close to $c^Tx^*$, you still need to check every coordinate of every other point, becuase for any other $x$, $c_j x_j$ can be arbitrarily large.