For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T23:20:16Z http://mathoverflow.net/feeds/question/35044 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35044/for-ax-b-x-and-b-unknown-vectors-how-do-i-solve-the-x-that-maximizes-minb-i For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)? Freed 2010-08-09T19:34:36Z 2010-08-09T20:39:41Z <p>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$.</p> <p>Extra contraints on the solution are $x_i \geq 0$, and $\sum x_i = 1$.</p> <p>Is this possible to solve, and if so, how? Can it have 0 or more than one solution?</p> http://mathoverflow.net/questions/35044/for-ax-b-x-and-b-unknown-vectors-how-do-i-solve-the-x-that-maximizes-minb-i/35047#35047 Answer by Peter Shor for For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)? Peter Shor 2010-08-09T20:22:55Z 2010-08-09T20:22:55Z <p>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. </p> <p>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.</p>