I have a max-min problem with some non-convex constraints, that I convert to approximate convex ones.
max min X_i
s.t.
convex_const
non_convex_const
I am trying to use the Successive convex approximation (SCA) after converting the non_convex_const to a new approximated convex constraint ( new_convex_const).
to handle the max-min objective, I am using an auxiliary variable as an objective and used the bisection method to find the solution of the the new convex problem in each iteration of the SCA
max t
s.t.
convex_const
new_convex_const
x_i>=t , i =1-to-N
I formulated the problem using CVX assuming two loops , one for the SCA and one inner loop for the bisection search.
The problem now that i always get infeasible solution for the inner loop
My question: is the infeasibility due to wrong idea of merging both bisection and SCA or due to infeasible initialization of the first iteration of the SCA
Thank you in advance
If your inner problem is convex, which it appears to be (because you made it so with your convex approximation), then you should use CVX, i.e., a cvx_begin … cvx_end code segment) to formulate and solve your inner problem. Bisection is needed if the problem is quasi-convex but not convex.
So I think you want a single loop which does successive convex approximation. Then more or less, inside the loop, formulate and solve the current convexified problem, then test for termination (convergence of the overall algorithm), then if the algorithm has not been terminated, update the point at which the convexification will be made the next time through the loop.
Edit: Do you know whether your original problem is feasible? Do you know whether your first convexified problem is feasible? That may depend on the point about which it is convexified.
Thank you for your reply
the original objective function is max-min (i.e. a quasi-convex form) and with the non-convex constraint (I approximated it using SCA).
To the best of my knowledge, the max-min problem is a quasi-convex which needs bisection to be solved . This is the reason why I am trying to use two loops.
Do I need the bisection after adding the auxiliary variable?
I will also check again for feasibility of the original problem and the point about which it is convexified.
Alright, so perhaps you need bisection. But you need the problem to which you are applying bisection to be feasible - that will depend on feasibility of the original (non-convexified) problem, and more to the point, the feasibility of the convexified problem(s), which depend on the manner of convexification, and in an SCP approach, the point about which the convexification occurs.