Optimization Simple search

I got a quick question, lets say I have an array of numbers for example [ 9 3 2 7 1 8 ] and I want to find the minimum value ie: for this example it would be 1.

How could I implement an optimization search like this??

[Paulo Silva]

min([ 9 3 2 7 1 8 ])

Optimization?!

Answer 1

[Matt Tearle]

Can you explain what you want beyond min(x)?

Answer 2

[John]

I know I can use [value index] = min(array) however I am wanting to write my own loop for this.

I just want the loop to output the minimum value in the array, that is it.

[Matt Tearle]

Why do you want to write your own? Is there something to your application that min can't handle? If it's efficiency, you're not going to be able to beat the built-in min function.

[Paulo Silva]

looks like homework or something similar, I know you love logical indexing but please don't hate the loops :)

[Matt Tearle]

I'm not hatin' on the loops. It's just the difference between a built-in function and a user-defined function. You'll end up basically writing the same function as the built-in version, with none of the optimization benefit.

[Paulo Silva]

that's a good reason to make the loop are compare the performance of it versus the MATLAB functions, might be the best way to learn, also some teachers won't be happy if they ask for a loop and get something else.

[Matt Tearle]

That's why I'd really like to know *why* John wants to avoid built-ins. If it's "because the teacher said so", well fine, can't argue with that. But if it's something else like "I can write my own stripped down, lean, mean, min-finding machine that will speed up my code", then it's important to know that it can't be done. (Well, not easily :))

[Matt Fig]

It wasn't that hard! It only took me about 30 seconds to write code faster than MIN for vector x...

>> x = rand(1,100000);

>> tic,[mn,I] = min(x);toc

Elapsed time is 0.008383 seconds.

>> tic,[mn,I] = min(x);toc

Elapsed time is 0.009373 seconds.

>> tic,[mn,I] = min(x);toc

Elapsed time is 0.008827 seconds.

>> tic,[mn,I] = min(x);toc

Elapsed time is 0.008746 seconds.

>>

>> tic,[mn2,I2] = mymin(x);toc

Elapsed time is 0.004359 seconds.

>> tic,[mn2,I2] = mymin(x);toc

Elapsed time is 0.004483 seconds.

>> tic,[mn2,I2] = mymin(x);toc

Elapsed time is 0.004266 seconds.

>> tic,[mn2,I2] = mymin(x);toc

Elapsed time is 0.004549 seconds.

>>

>> isequal(mn,mn2)

ans =

1

>> isequal(I,I2)

ans =

1

[Paulo Silva]

That's very fast code but John insists on the bubble sort!!! ahahah :)

[Paulo Silva]

I tested my code and Johns with

n=100000

m=randi([1 10],n,2); %x and y array

The timings are 0.002s for my code and 231.954s for Johns code, the test values aren't similar to yours but it does provide one idea on how inefficient is the bubble sort method.

[Matt Tearle]

@Matt Fig: show your code! I can't beat the built-in. What version are you running? And I assume you have multiple cores (and can make use of implicit multithreading)? Mine's only dual-core anyway. Oh and, not surprisingly, I'm using R2011a.

[Matt Fig]

@Matt Tearle: Actually the code is similar to code posted by Paulo Silva. Was I surprised that it is faster than the built-in? Heck yes! But it is on my machine, as shown above. I later even added some feature checking ([] and nan) and it is still faster, though only by 8% instead of nearly 200% as before. I am using a dual core Centrino at 2.33 Ghz on 2007b.

One curiosity I did notice is that MIN with only one output is twice as fast as with two outputs... interesting. Here is the code, but notice not the code I used yesterday. The NaN and [] handling weren't there.

function [mn,I] = mymin(x)

% Find the min for vector x.

% Author: Matt Fig

if isempty(x)

mn = [];

I = [];

return

end

idx = isnan(x);

if idx

mn = nan;

I = 1;

return

else

x(idx) = inf;

end

mn = x(1);

I = 1;

for ii = 2:length(x)

if x(ii)< mn

mn = x(ii);

I = ii;

end

end

[Matt Fig]

I just noticed that my function incorrectly handles NaN's if the input has only NaN and Inf - the index is always 1. This must be part of the reason why MIN is so much slower with two outputs... It is doing some gymnastics when NaN's are encountered.

[Matt Tearle]

Interesting! Thanks for the info. I did idly wonder if the number of outputs was making the difference, but couldn't see any reason why. Your explanation makes sense.

Answer 3

[Paulo Silva]

m=[9 3 2 7 1 8 ]
%another way to find minimum value, using unique
u=unique(m);
u(1)
%another way to find minimum value, using sort
s=sort(m);
s(1)
%another way to find minimum value, a loop this time
MinVal=m(1);
for lo=1:numel(m)
    if m(lo)<MinVal
        MinVal=m(lo);
    end
end

MinVal

[Andrei Bobrov]

or more loops for

k = sum(abs(m));

for jj = 1:numel(m)

k = min(k,m(jj));

end

Answer 4

[Walter Roberson]

If you use one of the optimizers that do not require continuous derivatives, then for any x value, take K = floor(x); if that is out of the range 1:length(m) return +infinity, and otherwise return m(K)

The optimization routine should then find the minimum value, and floor() of the x value it returns will be the index of that value.

Answer 5

[John]

I have been looking at everything suggested and researched other options is a bubble sort an efficient way to sort an array as well? I am trying to stay away from built in matlab functions

[Walter Roberson]

Bubble sort is one of the _least_ efficient deterministic sorts, at least for sufficiently large arrays. For very small arrays it can be faster than some of the alternatives.

[John]

So if I have an array of about 10,000 values, what type of method would you suggest, preferably not using a built in matlab function.

[Matt Tearle]

I thought you just wanted the minimum value -- sorting the entire array just to get the minimum seems highly suboptimal. And, again, can you *please* explain why you want to avoid built-in functions? I'm sure there *are* good reasons, but very often people think they have a good reason that turns out to be false (eg efficiency, deployability, etc).

[John]

I do just need the minimum value but I was just familiar with a bubble sort to sort all the values and output the first value of the array, I have implemented a bubble sort which seems to be running quickly in the array of numbers I have, the reason I did not want to use a matlab function was just out of curiosity, I knew I could have sorted the values using [value index]=min(array), and then you guys gave me great alternatives, however I have a new question/problem. I have an array of y values with an array of x values. I want to sort the y values to find the minimum y value of the array, but the number I am really looking for is the x value that corresponds with the minimum y value. So i have tried building a matrix of [x y] and sorting it but it sorts both sets (which is obvious, How could I do what I just explained, (if you cannot understand I can clarify it better)

[Paulo Silva]

m=randi([1 10],5,2) %x and y array

MinVal=m(1,2);

MinValRow=1;

for lo=1:size(m,1)

if m(lo,2)<MinVal

MinVal=m(lo,2);

MinValRow=lo;

end

end

MinValy=MinVal

MinValx=m(MinValRow,1)

MinValRow

[John]

Thanks a lot!

Answer 6

[John]

I am trying to implement this form of a bubble sort, doing what I explained above but matlab is giving me an error because y is not defined in my function, but I do not understand why.

function y= bubble(x,y) 
  n = length(x); 
  for k = 1:n-1 
    for j = 1:n-k 
     if(x(j)> x(j+1)) 
      temp = x(j); 
      x(j) = x(j+1); 
      x(j+1) = temp; 

       temp = y(j);
       y(j) = y(j+1);
       y(j+1) = temp;

       end % if 
      end % for 
    end % for 
    y = x;

[Paulo Silva]

even after being warned about the inefficiency of that method you insist on using it!

Your function does work fine:

m=randi([1 10],10,2) %x and y array

y=bubble(m(:,1),m(:,2))

y(1) %min value

Answer 7

[Paulo Silva]

John code:

function y= bubble(x,y) 
  n = length(x); 
  for k = 1:n-1 
    for j = 1:n-k 
     if(x(j)> x(j+1)) 
      temp = x(j); 
      x(j) = x(j+1); 
      x(j+1) = temp; 
       temp = y(j);
       y(j) = y(j+1);
       y(j+1) = temp;
       end % if 
      end % for 
    end % for 
    y = x;

my code:

MinVal=m(1,2); 
MinValRow=1; 
for lo=1:size(m,1) 
 if m(lo,2)<MinVal 
 MinVal=m(lo,2); 
 MinValRow=lo; 
 end 
end

Test with

n=1:2000
m=randi([1 10],n,2); %x and y array

You can see the time of code execution rising very fast with the bubble sort method, while with my code the time remains almost constant, better codes do exist and I bet that Matt Fig has better code :)

Answer 8

[John]

I understand your method is more efficient, and i do not believe my bubble sort is working either because I have:

sort=bubble(y1,x1)

To get real specific of what i want I am going to add some code below. Maybe you will see what is going on.

f=@(Isp) (alpha*g*T*Isp)./(2*(1-(((Isp-5000).^2)/(5000^2)))) + Mo*(1-exp(-dV./(Isp*g)));

Analytical_Derivative=@(Isp)  2943./100000./(2-1./12500000*(Isp-5000).^2)-2943./100000.*Isp./(2-1/12500000.*(Isp-5000).^2).^2.*(-1./6250000.*Isp+1./1250)-70000000000/981./Isp.^2.*exp(-1400000/981./Isp);

dydx=@(Isp,y) 2943./100000./(2-1./12500000*(Isp-5000).^2)-2943./100000.*Isp./(2-1/12500000.*(Isp-5000).^2).^2.*(-1./6250000.*Isp+1./1250)-70000000000/981./Isp.^2.*exp(-1400000/981./Isp);

[x1 y1]=eulode(dydx, [1 9700],50000,10);

The eulode is just a program I have written for Euler's method to approximate an integral.

The thing is it is outputting a directory of x-values, as well as y-values. The reason I want to sort the values it that at the point where my y-value is minimum I want to know my x-cordinate, I am trying to do it without a matlab built in function. I am just having the problem of my x values not sorting with each corresponding y value. I know the bubble sore is inefficient but it gets the job done for what I need. Please any suggestion on how to edit my bubble sort code to allow each x value to sort with its corresponding y value, NOT BOTH.

[Walter Roberson]

If you just need to find the minimum, why bother sorting???

[John]

You are right, I just thought the easiest way without using a built in function would be sort it then output the first value.

[Walter Roberson]

No, just a single pass through finding the minimum is *much* easier than sorting.

[John]

Ok, I'm gonna try to come up with something that will just find a min value then.