Solving a maxmin problem using the bisection method


(Rasoul Nik) #1

Hi.
I am trying to solve a max-min problem (power allocation):
max_x min_k F(x,k)
x>=0
This can be written as:
max_{x,t} t
F(x,k)>=t for all k
If F(x,k)=A(x,k)/B(x,k), then one can fix t (solve several problems) and solve the following feasibility problem:
max_x (0)
A(x,k)>t*B(x,k)
If this feasibility problem is convex then one should obtain a good approximation for the original problem by solving a sequence of convex feasibility problems.
I have implemented this approach in CVX without any error, but the final solution is not optimum. Is there any theoretical concern about this approach or there are some mistakes in my simulation.
Thanks in advance.