Global minimum in a huge convex matrix by using small matrices

Question

I have a function J(x,y,z) that gives me the result of those coordinates. This function is convex. What is needed from me is to find the minimum value of this huge matrix. At first I tried to loop through all of them, calculate then search with min function, but that takes too long ...

so I decided to take advantage of the convexity. Visual example

Take a random(for now) set of coordinates, that will be the center of my small 3x3x3 matrice, find the local minimum and make it the center for the next matrice. This will continue until we reach the global minimum.

Another issue is that the function is not perfectly convex, so this problem can appear as well

fake and real min

so I'm thinking of a control measure, when it finds a fake minimum, increase the search range to make sure of it. How would you advise me to go with it? Is this approach good? Or should I look into something else?

This is something I started myself but I am fairly new to Matlab and I am not sure how to continue.

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');

Any guidance, improvement and constructive criticism are appreciated. Thanks in advance.

Have you tried using MATLAB's optimization toolbox to find the minimum... fminunc or fmincon? Have you tried other algorithms like Gradient Descent, Conjugate Gradient? What can and can't you do here? Minor Note: The first image you provided is from Andrew Ng's Coursera Machine Learning course. — rayryeng
I'm pretty sure by "fake global minimum" you mean "local minimum". — Andras Deak
Finding global extrema is a problem encompassing entire fields of mathematics and computer science. As such, it is probably too broad for this site. The linked article provides some good places to start from though. — MooseBoys
@rayryeng Indeed , the image is from his course, it's just how I see it in my head. Should have probably attach the source. As I mentioned, I'm fairly new to Matlab, should probably research a bit more before getting into the code itself — Mike
Also, don't call your variable min, that will override the built-in min() function. Use of i and j is also discouraged due to the imaginary unit. — Andras Deak

mixxen mixxen · Accepted Answer · 2016-02-23T11:15:43

Try fminsearch because it is fairly general and easy to use. This is especially easy if you can specify your function anonymously. For example:

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

then using fminsearch:

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

If your 3-dimensional function, J(x,y,z), can be described anonymously or as regular function, then you can try fminsearch. The input takes a vector so you would need to write your function as J(X) where X is a vector of length 3 so x=X(1), y=X(2), z=X(3)

fminseach can fail especially if the starting point is not near the solution. It is often better to refine the initial starting point. For example, the code below samples a patch around the starting vector and generally improves the chances of finding the global minimum.

% 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. The app is running the above code in Octave. You can edit the in-line function (possibly even try your problem) from this web-site as well.

Global minimum in a huge convex matrix by using small matrices

1 Answers