3

I'm trying to find the lexicographical maximum point of a bounded polyhedron, i.e. I have a set $P = \{x \in \mathbb{R}^n : Ax \leq b\}$ and I'm looking for the lexicographic maximum point of this set. Note also that every component of $x$ is bounded by a constant.

I want to solve this problem using a linear program. How would you proceed?

ocalex86
  • 55
  • 4
    If I had a linear-programming solver, I would have it maximize $x_1+\varepsilon x_2+\varepsilon^2 x_3+\cdots+\varepsilon^{n-1}x_n$, and choose $\varepsilon$ to be comfortably smaller than the ratio between any two nonzero entries of $A$. – hmakholm left over Monica Nov 10 '11 at 21:51
  • 1
    You could also do it iteratively, first finding the value of $x_1$, then $x_2$ and so on. – Yuval Filmus Nov 10 '11 at 22:16

1 Answers1

4

There's a proof in this paper by Stef Tijs that the approach Henning suggests of maximizing $x_1 + \epsilon x_2 + \epsilon^2 x_3 + \cdots + \epsilon^{n-1} x_n$, for sufficiently small $\epsilon$, will work. Unfortunately, the proof is nonconstructive, so it doesn't tell you exactly which value of $\epsilon$ to use. It just proves that there exists some $\hat{\epsilon}$ such that, for all $\epsilon \leq \hat{\epsilon}$, maximizing $x_1 + \epsilon x_2 + \epsilon^2 x_3 + \cdots + \epsilon^{n-1} x_n$ over $P$ will give you the lexicographic maximum of $P$. I think Henning's suggestion to let $\epsilon$ be smaller than the ratio between any two nonzero entries of $A$ should work, though.

Yuval's idea of finding the lexicographic maximum by iteratively finding the value of $x_1$, then $x_2$, and so forth should also work. The disadvantage there is that it might take up to $n$ separate linear programming problems, while Henning's suggestion for small enough $\epsilon$ would find the lexicographic maximum with just one LP.

Mike Spivey
  • 55,550
  • Might seem like a dumb question, but to get the lexicographic minimum is it maximizing the program $-(x_1 + \epsilon x_2 + \epsilon^2 + \cdots + \epsilon^{n-1} x_n)$? – Tim Seguine Dec 05 '12 at 13:30
  • @Tim: Yes, that should give the lexicographic minimum. (And thanks for forcing me to look at my answer again; it has a couple of typos.) – Mike Spivey Dec 05 '12 at 17:34