MATLAB Central Newsreader - solve dot(x,y)<=z for x

solve dot(x,y)<=z for x

Oriole — Mon, 19 Jan 2009 16:22:01 -0500

Hello, Happy new year.

I would appreciate your advice...

Problem: solve dot(x,y)<=z for x, list all solutions

Input (knowns): z: a positive real number (scalar)
                         y: a n-d vector of positive numbers, sorted in ascending order

Output(unknowns) x : a n-d vector of non-negative integers

Basic idea of my solution: I lexicographically list out the candidates for solutions, while checking the condition "dot(x,y)<=z".

For example, z = 3.8, y =[1.213, 2.142, 3.112],

my code would be

y=[1.213, 2.142, 3.112];
z =3.8;
n= length(y); % dimension of input vector y
x= zeros(1,n); % solution vector x
X = []; % matrix storing all solution vectors x
flag =1;
while flag ==1
    X = [X; x];
    flag =0;
    for j= n:-1:1
        if dot (x (1:j), y(1:j))+ y(j) <= z
            x(j+1:n) =0;
            x(j) = x(j)+1;
            flag = 1;
            break
        end
    end
end
X % display the solution

It works quite fast, for moderate n and z. But since I tend to always use less efficient approach, I would like to hear your opinions about it.

Re: solve dot(x,y)<=z for x

Gene — Mon, 19 Jan 2009 17:49:03 -0500

"Oriole " <oriole_ni@hotmail.com> wrote in message <gl29b9$6tb$1@fred.mathworks.com>...
> Hello, Happy new year.
>
> I would appreciate your advice...
>
> Problem: solve dot(x,y)<=z for x, list all solutions
>
> Input (knowns): z: a positive real number (scalar)
> y: a n-d vector of positive numbers, sorted in ascending order
>
> Output(unknowns) x : a n-d vector of non-negative integers
>
> Basic idea of my solution: I lexicographically list out the candidates for solutions, while checking the condition "dot(x,y)<=z".
>
> For example, z = 3.8, y =[1.213, 2.142, 3.112],
>
> my code would be
>
> y=[1.213, 2.142, 3.112];

Oriole:

I'm not sure I fully understand your problem, but the inequality dot(x, y) <= z will have infinitely many solutions. Matlab provides some tools for characterizing the the set of solutions.

First, consider the problem dot(x, y) = 0. Geometrically, this is a plane through the origin; all points on it are orthogonal (perpendicular) to the y vector (assumed nonzero).
> z =3.8;
> n= length(y); % dimension of input vector y
> x= zeros(1,n); % solution vector x
> X = []; % matrix storing all solution vectors x
> flag =1;
> while flag ==1
> X = [X; x];
> flag =0;
> for j= n:-1:1
> if dot (x (1:j), y(1:j))+ y(j) <= z
> x(j+1:n) =0;
> x(j) = x(j)+1;
> flag = 1;
> break
> end
> end
> end
> X % display the solution
>
> It works quite fast, for moderate n and z. But since I tend to always use less efficient approach, I would like to hear your opinions about it.

Oriole:

I'm not sure I fully understand your problem, but the inequality dot(x, y) <= z will have infinitely many solutions. Matlab provides some tools for characterizing the set of solutions.

First, consider the problem dot(x, y) = 0. For nonzero y this is a plane through the origin; it is the set of vectors orthogonal to the vector y. If you think of the row vector y as the representation of a linear map from the x-space to the scalars then we want the null space of the map. Matlab provides the 'null' function. For the y vector in your posting
>> xx = null(y)

xx =

   -0.5398 -0.7843
    0.7768 -0.3243
   -0.3243 0.5289

Any vector formed as linear combination of these two columns will lead to a vector 'x' with dot(x, y) = 0.

To any such vector add beta*y where the scalar beta is <= z/dot(y,y). In Matlab-ese

x = xx(:,1)*alpha_1 + xx(:,2)*alpha_2 + beta*y

It may be helpful to draw a picture in two dimensions.

I hope this helps

e.m.cliff

Gene

Oriole — Mon, 19 Jan 2009 18:50:18 -0500

Thank you Gene,
The solution "x" is supposed to be a vector of integers and being non-negative, so there should be finite nunber of solutions....
Oriole

Re: Gene

Bruno Luong — Mon, 19 Jan 2009 20:05:04 -0500

function x=solvedot(z, y, head)

n = length(y);
x = (0:floor(z/y(1))).';
if n>1
    % recursive call
    z = z-y(1).*x;
    y = y(2:end);
    x = cell2mat(arrayfun(@(z,x) solvedot(z, y, x), z, x, ...
                 'UniformOutput', false));
end

if nargin>=3 % add a head column
    x = [head+zeros(size(x,1),1) x];
end

end % solvedot

% Command line
x=solvedot(3.8, [1.213, 2.142, 3.112])

% Bruno

% Bruno

Re: Gene

Matt Fig — Mon, 19 Jan 2009 20:40:18 -0500

I don't necessarily think this is more efficient, but here is a vectorized approach.

function X = solvedott(z,y)
lngth = length(y);
X = repmat({0:max(floor(z./y(y~=0)))},1,lngth) ;
[X{1:lngth}] = ndgrid(X{:});
X = fliplr(reshape(cat(lngth+1,X{:}),[],lngth)) ;
Y = y(ones(1,size(X,1)),1:lngth);
X = X(sum(X.*Y,2)<=z,:);

_UYfQ*QdS``0}YdvU_Q\o]W\_dve=]_oeoSRooQQ_UX[U^_oXRIQoXoi5Q^

Re: Gene

Bruno Luong — Mon, 19 Jan 2009 21:04:02 -0500

% Brute force
function X=solvedottt(z, y)
n=length(y);
p = cellfun(@(c) (0:c), num2cell(z./y), 'UniformOutput', false);
[p{:}] = ndgrid(p{:});
X=cat(n+1,p{:});
X=reshape(X,[],n);
Xy=X*y(:);
X(Xy>z,:)=[];
end

% Bruno

Bruno, Matt

Oriole — Mon, 19 Jan 2009 22:34:01 -0500

Thank you very much, Bruno and Matt, I will try on your suggestions. Matt, I asked you a question in a old post of mine, would you please have a look at it.

find vector r<=p (p: a given vector)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238871