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 example in YALMIP (a MATLAB package) is:

clear b c m
sdpvar b c m

x = [1 2; 3 5; 9 7; 6 8; 7 6.5; 3 5.8; 10 19; 4 6]

constraints = set(b>=0)
 
for i = 1 : size(x,1)
constraints = constraints + set(x(i,2)-x(i,1)*m-c>=0) +...
                     set((x(i,2)-x(i,1)*m-c)^2<=b^2*(1+m^2));
end

minobj=b

relaxdeg=8

[info,sol,mom,cert]=solvemoment(constraints,minobj,[],relaxdeg)

The result is that your problem should be infeasible. Maybe I did something wrong?

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

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 example in YALMIP (a MATLAB package) is:

clear b c m r
sdpvar b c m r

x = [1 2; 3 5; 9 7; 6 8; 7 6.5; 3 5.8; 10 19; 4 6]

constraints = set(b>=0) + set(r^2<=1+m^2) + set(m>=0)
for i = 1 : size(x,1)
constraints = constraints + set(0 <= x(i,2)-x(i,1)*m-c <= b*r)
end

relaxdeg=4

[info,sol,mom,cert]=solvemoment(constraints,b,[],relaxdeg)

sol{1}

This gives the following (at least numerically) optimal solution:

b = 4.7548
c = -9.9939
m = 1.8874
r = 2.1350

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

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

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 example in YALMIP (a MATLAB package) is:

clear b c m
sdpvar b c m

x = [1 2; 3 5; 9 7; 6 8; 7 6.5; 3 5.8; 10 19; 4 6]

constraints = set(b>=0)

for i = 1 : size(x,1)
constraints = constraints + set(x(i,2)-x(i,1)*m-c>=0) +...
                     set((x(i,2)-x(i,1)*m-c)^2<=b^2*(1+m^2));
end

minobj=b

relaxdeg=8

[info,sol,mom,cert]=solvemoment(constraints,minobj,[],relaxdeg)

The result is that your problem should be infeasible. Maybe I did something wrong?

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