algorithm - 使用小矩阵在巨大的凸矩阵中实现全局最小值

Question

我有一个函数 J(x,y,z) 可以给出这些坐标的结果。这个函数是凸的。我需要的是找到这个巨大矩阵的最小值。起初我试图遍历所有这些，计算然后用 min 函数搜索，但这需要太长时间......

所以我决定利用凸性。

取一组随机(暂时)坐标，这将是我的 3x3x3 小矩阵的中心，找到局部最小值并将其作为下一个矩阵的中心。这将一直持续到我们达到全局最小值。

另一个问题是函数不是完全凸的，所以也会出现这个问题

所以我在想一个控制措施，当它找到一个假的最小值时，增加搜索范围以确保它。你会如何建议我去做呢？这种方法好吗？还是我应该看看其他东西？

这是我自己开始的，但我对 Matlab 还很陌生，我不确定如何继续。

clear all
clc
min=100;

%the initial size of the search matrix 2*level +1
level=1;
i=input('Enter the starting coordinate for i (X) : ');
j=input('Enter the starting coordinate for j (Y) : ');
k=input('Enter the starting coordinate for k (Z) : ');

for m=i-level:i+level
    for n=j-level:j+level
        for p=k-level:k+level
            A(m,n,p)=J(m,n,p);
            if A(m,n,p)<min
                min=A(m,n,p);
            end
        end
    end
end
display(min, 'Minim');

[r,c,d] = ind2sub(size(A),find(A ==min));

display(r,'X');
display(c,'Y');
display(d,'Z');

感谢任何指导、改进和建设性批评。提前致谢。

Answer 1

试试 fminsearch，因为它相当通用且易于使用。如果您可以匿名指定您的函数，这将特别容易。例如:

aFunc = @(x)100*(x(2)-x(1)^2)^2+(1-x(1))^2

然后使用 fminsearch:

[x,fval] = fminsearch( aFunc, [-1.2, 1]);

如果您的 3 维函数 J(x,y,z) 可以匿名描述或描述为常规函数，那么您可以尝试 fminsearch。输入采用向量，因此您需要将函数编写为 J(X)，其中 X 是长度为 3 的向量，因此 x=X(1), y=X(2), z=X(3)

fminseach 可能会失败，尤其是当起点不在解决方案附近时。改进初始起点通常更好。例如，下面的代码对起始向量周围的一个补丁进行采样，通常会提高找到全局最小值的机会。

% deltaR is used to refine the start vector with scatter min search over
% region defined by a path of [-deltaR+starVec(i):dx:deltaR+startVec(i)] on
% a side.
% Determine dx using maxIter.
maxIter = 1e4;
dx = max( ( 2*deltaR+1)^2/maxIter, 1/8);
dim = length( startVec);
[x,y] = meshgrid( [-deltaR:dx:deltaR]);

xV = zeros( length(x(:)), dim);

% Alternate patches as sequential x-y grids.
for ii = 1:2:dim
    xV(:, ii) = startVec(ii) + x(:);
end
for ii = 2:2:dim
    xV(:, ii) = startVec(ii) + y(:);
end

% Find the scatter min index to update startVec.
for ii = 1: length( xV) 
    nS(ii)=aFunc( xV(ii,:));
end
[fSmin, iw] = min( nS);
startVec = xV( iw,:);
fSmin = fSmin
startVec = startVec

[x,fval] = fminsearch( aFunc, startVec);

You can run a 2 dimensional test case f(x,y)=z on AlgorithmHub .该应用程序在 Octave 中运行上述代码。您也可以从该网站编辑内联函数(甚至可能尝试您的问题)。