Matrix which when multiplied, gives a maximal minimum of elements of result. I'm working on an optimization problem and am stuck at this particular step.
Let $\bf{A}$ be a matrix with 4 columns and a finite number of rows, consisting of elements which are either 0 or 1.
Let $\bf{B}$ $= \left(\matrix{a\\b\\c\\d}\right)$ where $a,b,c,d$ are real numbers such that $a,b,c,d \ge 0$ and $a + b + c + d = 1$.
Find the values of $a,b,c,d$ for which the minimum element in $\bf{AB}$ is the highest (among the minimum element produced by other values of $a, b, c, d$).
Are there any known formulas or algorithms which can do this? I am currently using the genetic algorithm, but as expected, its time and space complexity is too high.
 A: This can be turned into a linear programming problem. Introduce  $m$, the minimum of elements of $AB$. Each row of $A$ gives a linear constraint: 
$$a_{i1}a+a_{i2}b+a_{i3}c+a_{i4}d\ge m$$ 
You also have the constraints on $a,b,c,d$ mentioned in the problem; these are also linear. The objective function is $f(a,b,c,d,m)=m$; to be maximized. 
By the way, you may want to first eliminate any redundant constraints (I don't know if LP solvers can  do it automatically). Only the rows of  $A$ that are minimal with respect to coordinate-wise comparison should be considered. By Sperner's theorem there are at most $\binom{4}{2}=6$ such rows.
A: I do not believe that there are any deterministic algorithms to compute this.
You would have to employ some sort of convergent numeric method which converges to the best answer each iteration, something like Newton's method. 
You could base each iteration on the minimum element of the resultant matrix, or as some other function of the multiplied matrix, and optimize each step accordingly.
