MATLAB：在[-1,1]中找到具有未知係數的一階多項式x，y的可行區域的有效方法

正如在標題中一樣，在MATLAB中，我需要可行區域（所有可行解的界限）的MATLAB：在[-1,1]中找到具有未知係數的一階多項式x，y的可行區域的有效方法

x_0 + x_1 e_1 + ... + x_n e_n

和

y_0 + y_1 e_1 + ... + y_n e_n

其中所有未知e_i是在區間[-1, 1]。我寧願解決方案不依賴於非標準的第三方功能。

下面是我的快速和骯髒的嘗試，但複雜性增長O（2^n），其中n是e_i的數量。有什麼想法嗎？

x0 = 3; 
x = [1; -3; 0]; 
y0 = -1; 
y = [3; -2; 4]; 

% Get all permutations of noise symbol extremities 
terms = size(x, 1); 
xx = zeros(2^terms, 1); 
yy = zeros(2^terms, 1); 
for j = 1:2^terms 
    e = double(bitget(j - 1, 1:terms))'; 
    e(e == 0) = -1; 
    xx(j) = x0 + sum(x .* e); 
    yy(j) = y0 + sum(y .* e); 
end 

k = convhull(xx, yy); 
plot(xx(k), yy(k));

來源

2017-07-06 James Turner

% First generate all possible permutations for [-1, 1] for n terms. This is similar to what you have done but uses a matlab function 
all_e = de2bi(0:(2^terms-1), terms).'; 
all_e(all_e == 0) = -1; 
% Multiply corresponding values of x and y with those of e 
xx = x0 + arrayfun(@(z) sum(x .* all_e(:, z)), 1:(2^terms)); 
yy = x0 + arrayfun(@(z) sum(y .* all_e(:, z)), 1:(2^terms));

你可以閱讀更多關於功能de2bihere

的方法來找到絕對最小值和最大範圍如下：

max_e = double(x >= 0); 
min_e = double(~max_e); 
max_e(max_e == 0) = -1; 
min_e(min_e == 0) = -1; 
absMax = x0 + sum(x .* max_e); 
absMin = x0 + sum(x .* min_e);

同樣，你可以y的做

來源

2017-07-06 16:59:39 anyanwu

謝謝ammportal。我剛剛發佈了這個版本，並且稍微加快了速度，但由於運行時複雜度仍然是O（2^n），所以我仍然遇到了大型n的問題。另外，當像這樣預先分配時，我現在也有很大的O（2^n）內存複雜度！在實踐中，n通常約爲100，所以你可以想象這導致了多少問題。例如，你是否知道任何線性優化例程，這些例程可以使事情的蠻力減少一些，並且分析性更強一些？謝謝。 –

我不確定所有值，但有一種方法可以輕鬆找到絕對最大值和最小值。我會將其添加到我的答案中。 – anyanwu

我能想到的另一個優化是不生成0係數的e_i。這會使n減少0個項的數量。 – anyanwu

MATLAB：在[-1,1]中找到具有未知係數的一階多項式x，y的可行區域的有效方法

回答

相關問題