Could you give more specific instances of your problem? Without what you hide behind the dots (...), the instance you give is trivial (b=0, m=c=1/2). You can try the Lasserre moment relaxations of polynomial optimization problems, see the survey of Monique Laurent: http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf The code for your (unfortunately trivial) example in YALMIP (a MATLAB package) would be: clear b c m sdpvar b c m constraints = ... set(b>=0)+... set(2-3*m-c>=0) +... set((2-3*m-c)^2<=b^2*(1+m^2)) +... set(4-7*m-c>=0) +... set((4-7*m-c)^2<=b^2*(1+m^2)) minobj=b relaxdeg=4 [info,sol,mom,cert]=solvemoment(constraints,minobj,[],relaxdeg) sol{1} relaxdeg=5 [info,sol,mom,cert]=solvemoment(constraints,minobj,[],relaxdeg) sol{1} For this to work you need an SDP solver like SeDuMi. Implementations of the Lasserre moment approach other than YALMIP are SOSTools, GloptiPoly and SparsePOP. I have also some slides which might be helpful: http://www.math.uni-konstanz.de/~schweigh/presentations/polopt-kirchberg.pdf