Optimize vector position and values to form another vector.

Hi, I am stuck with a problem which I do not know how to proceed. I have 2 vectors:

 a = [1 2 3 2 1];
 b = zeros(1, 11);

I want to find the best placement (maximum 3 or 4) and weighting of vector 'a' inside vector 'b' so that the values of vector b have the least standard deviation possible.

A possible solution could be:

 b(1:5) = a * 2;
 b(4:8) = a * 1.5;
 b(6:10) = a * 1.5;
 b(9: 11) = a * 2;

However, if it were that simple to figure, I wouldn't need help :-). Please, leave a suggestion as to how this could be tackled. Thank you.

[Sean de Wolski]

This looks like a fun problem.

[Charles]

That is why you should give it a try :-)

[Fangjun Jiang]

Don't rush. Try to solve it on paper. If the linear constant (2 or 1.5 in your example) is zero. You got the solution! The position where a is put in b does not matter based on your example. You need to refine your problem.

[Charles]

Hi, thanks for ur suggestion. However, maybe I should have made it clearer that the vector b should have all its values > 0.

[Fangjun Jiang]

Again, you need to refine or clarify your problem. What do you mean 3 or 4 placement? Does it mean a has to be placed in b 3 or 4 times? How about the overlap? What is the constraint about it? In your example, b(11)=0. Reading all your comments, I am kind of lost.

[Charles]

Hi, there will be overlaps with the placements. This concept is captured in the example that I gave as there is overlap between the first and second (1:5 and 4:8) placement, and between the second and third placement (4:8 & 6:10). As for b(11) being equal to 0, that was an initial omission which I have corrected. I hope it is clearer.

Answer 1

[Andrew Fowler]

You could set up your problem in a couple of ways. The easiest would be by brute force using nested loops, though it may not be the best:

a = [1 2 3 2 1]
b = zeros(1,11)

% Make a guess that you know is too high for the standard deviation
devb = 50

% There's only 7 places that a can go into b, so we make 
% a for loop that has 7 increments.

    for i = 1:7
      b(i:i+4) = a; % You dimensions have to match.  See what I did?

% The syntax here is inital_value:increment:final_value, 
% and you get a vector that goes from initital_value 
% to final_value by steps of increment.
    for j = 1:0.1:2  
      c = b*j; % This is weighting as you presented it in your question, 
               % but I think it might not be right.

        % if the values that have been run through the loops give 
        % you a lower deviation value than the others, this statement 
        % will overwrite the previous value of deviationb with the current 
        % value, and save the values of i and j so you know what your  
        % solution was.

        if std(c) < deviationb
          deviationb = std(c);
          solutioni = i
          solutionj = j
        end
      end
    end

This code worked when I ran it, but I think you need to take another look at your problem.

[Charles]

Thanks for your comment. I am not sure I really understand your code very well. I did try to run it but it does not run, even after several trials and adjustments. Could u try running ur version?

[Andrew Fowler]

Hey there, sorry, I made a mistake. The c(i:i+5) should be c(i:i+4). I'm editing the code and adding more comments so you can see what I did.

[Sean de Wolski]

It's a good idea to use inf when you need a big value; devb = inf;

[Charles]

Hi Andrew, thanks for your suggestion. H/v, the example doesn't work because :

1. All the values of b must be non-zero.

2. Maximum placement points is 3 or 4.

3. Each placement point has its own weight.

Thanks.

Answer 2

[Sean de Wolski]

For the above example and any other permutation defined by it the best case scenario is all four weights to equal zero and the positions equal to whatever. That is, your 'b' vector is not completely full b(11) is still zero. As long 'b' can have non-a values, then there's no reason to have non-zero values since this WILL be the minimum standard deviation.

Assuming, you want to constrain all 'b' to not also be in 'a' it should be possible to set it up for fmincon, as an optimization problem of six variables: two positions and four weights, the positions constrained to integers in the middle so that the middle is covered. The boundaries are fixed since you would NEED one position to be 1, and the other to be length(b)-length(a)+1.

Just a few ideas hopefully someone can build on.

[Charles]

Yea, all values of 'b' should be non-zero. Also, the number of positions and weightings are the same. Thanks foe ur comment.