"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 nd vector of positive numbers, sorted in ascending order
>
> Output(unknowns) x : a nd vector of nonnegative 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 xspace 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 Matlabese
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
