Consider a maximin problem with $\lambda=[\lambda_1,\lambda_2,…,\lambda_n]$
$$\max_{\lambda}\min_{i\in\{1,2,3,…,M\}}{f_i(\lambda)}$$
subject to $\lambda$ is any vector locating in a standard probability simplex, that is $\sum_{i=1}^{n}\lambda_i=1$ and $\lambda_i\geq0, \forall i\in\{1,2,…,k\}$. Note that each function $f_i()$ is a linear function with the input $\lambda$ and positive output.
I know that this problem can be converted into the following:
$$\max z$$
subject to
$$z\leq f_i(\lambda)\ \forall i\in\{1,2,3,…,M\}$$
$$\lambda\ \text{is any probability vector}$$
My problem is, in the above constraint set, the upper bound of the $z$ may change with different $\lambda$. So, how can I solve this problem by simplex method or some typical algorithm and analyze the time complexity?
Most of the problems using the simplex method just considered the objective function and the constraint set are account for the same variables, e.g.,
$$\max{2x_1+x_2+3x_3}$$
subject to
$$ x_1+x_2\leq 3 $$
$$ x_2+x_3\leq 10 $$
$$ x_1+x_3\leq 20 $$
$$x_1,x_2,x_3\geq0$$
Note that there are just the variables $x_1,x_2,x_3$ in both the objective function and the constraint set. However, there is an extra $\lambda$ in our problem.
Edit:
I know that the python package Gekko provides a solver but I am wondering how the problem is solved (what's the algorithm Gekko uses) because I have to analyze the time complexity.
Edit: I have an idea as follows,
Can we just view that there are $M+1$ inequalities (we have $M$ $"z\leq f_i(\lambda)"$ and one $\sum_{i=1}^{n}\lambda_i\leq1$) and there are $1+n$ variables ($z$ and $\lambda_1,…,\lambda_n$) in this maximization problem? Hence, one can use the simplex method to solve it with time complexity $\Theta((M+n+2)^{1+n})$?
Best Answer
(1) My problem is, in the above constraint set, the upper bound of the z may change with different λ. I think you have an issue with the rhs not being constant. Note that we can write $$z - f_i(\lambda) \le 0$$
(2) analyze the time complexity Complexity theory says very little about the performance of a given LP solver on a given problem of a given size. In practice that means: try it out with your problem and different data sets.