Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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$. –  Henning Makholm 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 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 5 '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 5 '12 at 17:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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