Tables for Later

results = table();                                          % table for storing results
newresults  = table();                                      % table for storing new rows to add to our results
 
rho = (3-sqrt(5))/2;                                        % approximation for the golden ratio parameter (note that phi = 1/rho-1)

Setup

This will minimize the function along the vector generated by the initial two points. We can use the equation: or to determine how many iterations n we need to reduce our uncertainty to the desired value where: is determined by our initial two points. Note: n needs to be rounded UP to meet our uncertainy threshold.

u0 = 0.01;                                                  % desired uncertainty
a0 = [0.1062 ; -0.1250]; a = a0;                            % initial location of our guess
b0 = [0.1093 ; -0.1778]; b = b0;                            % initial location of our guess
 
u = sqrt((a(2)-b(2))^2+((a(1)-b(1))^2));                    % initial uncertainty value
 
s = a + rho*(b-a);                                          % initial calculation for "lower-guess"
t = a + (1-rho)*(b-a);                                      % initial calculation for "higher-guess"
 
f1 = myfunction(s);                                         % initial function value for "lower-guess"
f2 = myfunction(t);                                         % initial function value for "higher-guess"
 
results.iter = 0;                                           % logging initial iteration to table
results.low  = a';                                          % logging initial low-range to table
results.high = b';                                          % logging initial high-range to table
results.uncertainty = u;                                    % logging initial uncertainty to table
 
 
N = ceil(log(u0/u)/log(1-rho));                             % number of iterations to run the algorithm
%N = 4;                                                      % number of iterations to run the algorithm
 

Main Loop

for n = 1:N
    newresults.iter = n;                                    % update the iteration count on our results table
    newresults.low  = a';                                   % update the low-value in case it doesn't change
    newresults.high = b';                                   % update the high-value in case it doesn't change
    
    % check to see if our lower or upper bunds need to be move in
    if f1<f2
        b = t;
        t = s;
        s = a + rho*(b-a);
        f2 = f1;
        f1 = myfunction(s);
        newresults.high = b';
    else
        a = s;
        s = t;
        t = a+(1-rho)*(b-a);
        f1 = f2;
        f2 = myfunction(t0);
        newresults.low = a';
    end
 
    u = [u sqrt((a(2)-b(2))^2+((a(1)-b(1))^2))];            % updated uncertainty value
    newresults.uncertainty = u(end);                        % logging new uncertainty to table
 
    results = [results; newresults];                        % add the new results to our table
end

Display Results

disp(results);
    iter          low                  high            uncertainty
    ____    ________________    ___________________    ___________

     0      0.1062    -0.125     0.1093     -0.1778      0.052891 
     1      0.1062    -0.125    0.10812    -0.15763      0.032688 
     2      0.1062    -0.125    0.10738    -0.14517      0.020203 
     3      0.1062    -0.125    0.10693    -0.13746      0.012486 
     4      0.1062    -0.125    0.10665     -0.1327     0.0077167 

Plot Our Results

f = figure(); f.Position = [0 0 1300 500];

subplot(1,2,1)

plot(results.uncertainty);

title('Uncertainty Reduction'); xlabel('iteration'); ylabel('uncertainty');

subplot(1,2,2)

scatter(results.low(:,1), results.low(:,2), "filled"); hold on;

scatter(results.high(:,1), results.high(:,2), "filled"); hold on;

title('Range Endpoints'); xlabel('x'); ylabel('y');

legend('low', 'high');

Function being minimized

function y = myfunction(x)
    Q = [2 1; 1 2];
    y = 0.5*x'*Q*x;
end

Housekeeping