Suppose I have a polyhedron given as $$ Ax \le b , x \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$$ and I have a collection of functions $c_1^Tx , c_2^T x ,\ldots, c_k^Tx$ that I want to maximize against this system.

A naive way to do this would be to just run each as a traditional linear program which would take worst case $O(kn^{3.5}L)$ which roughly would be $O(kn^{4.5}m)$ assuming constant bitsized coefficients.

Now I'm curious if that bound can be beat, for example one idea is to consider $u_1 = \frac{c_1}{\|c_1\|},u_2 = \frac{c_2}{\|c_2\|} ,\ldots, u_k =\frac{c_k}{\|c_k\|}$ And then note that we can compute distances between $u_i$ and $u_j$ for all combinations of $i,j$ in $O(k^2)$ time.

From here we have that we can maximize $c_1$ then pick our next $c_i$ as the $u_i$ whose distance from $u_1$ is minimal, and has not already been visited, supplying as a starting point to that linear program,the optimal point from $c_1$.

Naturally this has to reduce the distance travelled, but it's hard to estimate how big of a difference this makes, for small $k$ its easy to make cases that run in maximal possible time.

Are there any algorithms out there that are provably more efficient, as opposed to just heuristics such as the type I have suggested?

But also of interest to me, there any more complex heuristics that fair quite well in practice for speeding up multiple levels of optimization?

  • 1
    $\begingroup$ What about using an advanced basis from a previous solve? $\endgroup$ – Erwin Kalvelagen Aug 30 '16 at 13:20
  • 1
    $\begingroup$ This is along the same lines of using a solution from a previous solve, i'm unable to determine if that logically yields a reduction in asymptotic runtime $\endgroup$ – frogeyedpeas Aug 30 '16 at 22:14

Your Answer

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

Browse other questions tagged or ask your own question.