Optimal arrangement of a small vector within a lager vector

1 次查看（过去 30 天）
Charles
Charles 2011-6-5
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更早的评论
Image Analyst
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
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
Teja Muppirala 2011-6-6
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;
0 1 2 3 2 1 0 0 0 0 0;
0 0 1 2 3 2 1 0 0 0 0;
0 0 0 1 2 3 2 1 0 0 0;
0 0 0 0 1 2 3 2 1 0 0;
0 0 0 0 0 1 2 3 2 1 0;
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更早的评论
Ivan van der Kroon
Ivan van der Kroon 2011-6-7
How large is b and are there any restrictions on the weights, e.g. nonnegative?

请先登录，再进行评论。

Ivan van der Kroon
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];
  6 个评论
显示 4更早的评论
Ivan van der Kroon
Ivan van der Kroon 2011-6-6
Another solution to the triviality will be to constrain Sum(w)=W for some predefined constant W.
Charles
Charles 2011-6-6
Hi, thanks for your post. 'w' can only positive. I will go thru your posts.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Surrogate Optimization 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by