I have found out that Mirror Prox seems to be a good First Order Method for general case constrained saddle point problems. I was also able to find some references to so called "planar methods", though I am not quite sure what are they.
Would you recommend something? Does it make may sense to use Mirror Prox (or Mirror Descent in general) for unconstrained problems?