Optimal arrangement of a small vector within a lager vector

1 次查看（过去 30 天）

Charles 2011-6-5

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/8815-optimal-arrangement-of-a-small-vector-within-a-lager-vector

Hi all,this is about the 3rd time I am posting this question as I do not have an answer yet. I simplified the original problem.

I have 2 vectors:

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

I want to find the best placements, 'p' (maximum 3 or 4x) and weightings, 'w', of vector 'a' inside vector 'b' so that the values of vector 'b' have the least standard deviation. All elements of 'b' must be non-zero.

As an example, a possible conceptual solution could be:

 b(p1)  = b(p1) + a * w1;  %w1 = 3;   p1 = 1:5;
 b(p2)  = b(p2  + a * w2;  %w2 = 2;   p2 = 4:8;
 b(p3)  = b(p3) + a * w3;  %w3 = 2;   p3 = 6:10;
 b(p4)  = b(p4) + a * w4;  %w4 = 3;   p4 = 9:11;

My problem is how to find the actual values of w1:w4 and p1:p4. Your help and suggestions will be very much appreciated.

4 个评论
显示 2更早的评论隐藏 2更早的评论

Image Analyst 2011-6-5

I'm with Wolfgang. I can't see how the placement of a within b affects the standard deviation. Just run this code and you'll see:

a=[1 2 3 2 1];

b = zeros(1,11);

b(1:5) = a % Start at element 1

std1 = std(b)

b = zeros(1,11);

b(5:9) = a % start at element 5

std1 = std(b)

It's 1.078719779941187 for both cases. I invite you to give an example of where the placement affects the std dev.

And if the weighting can't be 0 then let it be "eps." That will minimize the std dev.

Charles 2011-6-6

The original post had something missing. Here is an example

a =[1 2 3 2 1];

b = zeros(1,11);

b(1:5) = b(1:5) + a;

b(4:8) = b(4:8) + a * 1.5;

b(6:10) = b(6:10) + a * 2;

b(7 : 11) = b(7 : 11) + a * 2;

std(b)

c = zeros(1,11);

c(1:5) = c(1:5) + a;

c(3:7) = c(4:8) + a * 1.3;

c(6:10) = c(6:10) + a ;

c(7 : 11) = c(7 : 11) + a * 3;

std(c)

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

Teja Muppirala 2011-6-6

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/8815-optimal-arrangement-of-a-small-vector-within-a-lager-vector#answer_12213

在 MATLAB Online 中打开

Your problem can be expressed as an overdetermined system:

Given A and b where

A = [ 1 2 3 2 1 0 0 0 0 0 0; 
1 2 3 2 1 0 0 0 0 0;
0 1 2 3 2 1 0 0 0 0;
0 0 1 2 3 2 1 0 0 0;
0 0 0 1 2 3 2 1 0 0;
0 0 0 0 1 2 3 2 1 0;
0 0 0 0 0 1 2 3 2 1]
b =  [1 1 1 1 1 1 1 1 1 1 1];

Find an x (with size 1 by 7) with a maximum of 4 nonzero entries such that

norm(x*A - b) is minimized.

This can be done quite simply using plain old matrix division.

Step 0. Generate A and b.

A = [1 2 3 2 1 0 0 0 0 0 0];
A = gallery('circul', A);
A = A(1:7,:)
b = ones(1,11);

Step 1. Generate all unique combinations of 4 columns from 6 possible columns.

P = perms(1:7);
P = unique(sort(P(:,1:4),2),'rows');

Step 2. For each of those possible column combinations, use the pseudoinverse to find the optimal x, and the associated error for each case.

for n = 1:size(P,1)
  A4 = A(P(n,:),:);
  x{n} =  b/A4;
  err(n) = norm(x{n}*A4 - b);
end

Step 3. Find the combination that yielded the minimum error

[val, loc] = min(err);
x{loc} %<--- optimal weights
P(loc,:) %<--- optimal positions
plot(x{loc} * A(P(loc,:),:))

6 个评论
显示 4更早的评论隐藏 4更早的评论

Ivan van der Kroon 2011-6-7

How large is b and are there any restrictions on the weights, e.g. nonnegative?

Charles 2011-6-7

b is about 600 elements and the weights are non-negative.

请先登录，再进行评论。

Ivan van der Kroon 2011-6-5

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/8815-optimal-arrangement-of-a-small-vector-within-a-lager-vector#answer_12164

在 MATLAB Online 中打开

Allow me to define:

N=length(b);
M=length(a);
Q=3;%number if placements
p0=ones(Q,1);%starting vector for placements
w0=ones(Q,1);%starting vector for weigths

I reduced the p's to a single interger value such that you only need to give the first placement. For example

n=0:M-1;
b(n+p(j)) = b(n+p(j)) + a;

Now note that the entries of p are integers and must be within [1,2,...,N-M+1] otherwise the indices are out of bounds.

Now the problem is that I don't know how to specify that p should be these values in a standard optimization problem. If you can find this out (maybe just with ‘round’ if it is only of length 3 or 4, because it won’t cost you that much), I would suggest to use the optimization toolbox with the vector to look for is x=[p;w];