1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Assume that the cost of blindly computing the function value at all of the points is prohibitive" does not make any sense, any method will need to iterate over the extreme points at least once $\endgroup$ – LinAlg Nov 13 at 17:46
  • $\begingroup$ Good point. The idea is that we are looking for an algorithm that can perform better than just computing the objective at every point in the best case scenario. Such as in a case where we are given a good initial guess. $\endgroup$ – MeowBlingBling Nov 13 at 18:30
  • $\begingroup$ Even if I give you an optimal solution, you will still need to check every coordinate of every other point to guarantee optimality unless $c_i=0$ for that coordinate. $\endgroup$ – LinAlg Nov 13 at 18:44
  • $\begingroup$ @LinAlg You could add this as an answer. Could you also provide some justification as to why no faster methods would exist? I.e. we have no certificate of optimality otherwise. $\endgroup$ – MeowBlingBling Nov 13 at 19:06
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.