Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a matrix $A$, each element $A_{i,j} \geq 0$, find the vector $\vec x$ that maximizes the minimum element in $\vec b$ ($\vec b = A \vec x$). Note that this is not a linear equation system as I don't know $\vec b$.

Extra contraints on the solution are $x_i \geq 0$, and $\sum x_i = 1$.

Is this possible to solve, and if so, how? Can it have 0 or more than one solution?

share|improve this question
1  
For A a matrix, what does A >= 0 mean? Do you mean A is non-negative definite? –  Ricky Demer Aug 9 '10 at 19:37
    
I meant simply that all elements in A are >= 0, updated to clarify, thank you. –  SoftMemes Aug 9 '10 at 19:47
4  
I think it certainly has a solution by compactness (in other words, the set of $x_i \geq 0$ with $\sum x_i = 1$ is a compact set). You have a finite set of linear functions, the min of these functions is still continuous so there should be a minimum value. This looks vaguely like something someone in OR should immediately be able to answer. –  Karl Schwede Aug 9 '10 at 20:08
add comment

1 Answer

up vote 10 down vote accepted

This is a linear program. Put down the contraints $r \leq b_i \ \forall i$, together with all the linear constraints you have above, and maximize $r$. All the constraints are linear, so linear programming will do this. There are tons of linear programming packages (Mathematica and MATLAB have decent ones), and there should be some good introductory material on linear programming on the web that is better than anything I would write here, so I'll let you look for that.

Linear programs can in general have a lots of solutions (although they're all on one face of a polytope), or they may have no solutions. In this case, it certainly has at least one solution (see the compactness argument in the comments), but it mgiht have many.

share|improve this answer
    
This is exactly what I needed, thank you! –  SoftMemes Aug 9 '10 at 21:21
add comment

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.