function [t,i] = stepsize(x, dx)
% calling sequence: [t,i] = stepsize(x, dx)
% ratio test for LP
% given vectors x and dx, with x >= 0 (all components),
% compute max { t: x - t dx >= 0} (all components)
% here t is a real nonnegative scalar, possibly infinity,
% and i is returned as an index achieving the max
% Written by M. Overton for class Feb 2, 1998.
% Warning: may not be fully debugged.
% check x and dx have same length
n = length(x);
if n ~= length(dx),
error('x and dx must have same length')
end
% check that x >= 0
if min(x) < 0,
error('x has a negative component')
end
% if dx(i) <= 0 we don't care about it
% (because then (x - t dx)_i >= 0 for all t >=0)
% so consider only the dx(i) which are > 0
for i = 1:n,
if dx(i) > 0,
ratio(i) = x(i)/dx(i);
else
ratio(i) = inf; % infinity
end;
end;
[t,i] = min(ratio); % t could be infinity, then LP is unbounded