Golden Section Search algorithm, golden number why is 0.381

조회 수: 20 (최근 30일)
Emil Bucur
Emil Bucur 2020년 5월 29일
댓글: Emil Bucur 2020년 5월 29일
Hi guys, i don't understand why in tha code bellow (which works just fine) i don't understand why tau (the golden number) is 0.381.. ? I mean everywhere i look the golden number is 1.618 and if i change the constant value from 0.381 in 1.618 the code doesn't find the minimum of the function anymore. Any help is welcome. Kind regards
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MATLAB code golden.m
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% a -> lower bound of the design variable
% b -> upper bound of the design variable
% alpha -> midpoint of a and b
% falpha1 -> function value at x = alpha1
% falpha2 -> function value at x = alpha2
% epsilon -> constant used to terminate the algorithm
% abs -> absolute of a number, MATLAB function
% tau -> 2-golden number
%
clear all
clc
a = 40;
b = 90;
epsilon = 0.00001;
tau = 0.381967;
alpha1 = a*(1-tau) + b*tau;
alpha2 = a*tau + b*(1-tau);
falpha1 = func(alpha1);
falpha2 = func(alpha2);
fprintf(' a b \n')
fprintf('-------------------------\n')
for i = 1:100
fprintf(' %7.3f %8.3f \n',a,b)
if falpha1 > falpha2
a = alpha1;
alpha1 = alpha2;
falpha1 = falpha2;
alpha2 = tau*a + (1-tau)*b;
falpha2 = func(alpha2);
else
b = alpha2;
alpha2 = alpha1;
falpha2 = falpha1;
alpha1 = tau*b + (1-tau)*a;
falpha1 = func(alpha1);
end
if abs(func(alpha1)-func(alpha2)) < epsilon
break;
end
end
fprintf('-------------------------\n')
fprintf('x* = %7.3f Minimum = %8.3f\n',alpha1,func(alpha1))
fprintf('Number of function calls = %3d\n',2+i)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MATLAB code func.m
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% objective function to be coded here
% different test functions
%
function fx = func(x)
fx = 204165.5/(330-2*x) + 10400/(x-20);
% fx = 3*x^4+(x-1)^2;
% fx = -4*x*sin(x);
% fx = 2*(x-3)^2+exp(0.5*x*x);
%fx = 3*(x)^2+12/(x^3)-5;
% fx = 2*x*x+16/x;
%
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

채택된 답변

John D'Errico
John D'Errico 2020년 5월 29일
편집: John D'Errico 2020년 5월 29일
I think you need to spend some time in class listening, lol. Or, maybe your instructor did not explain this. It is very possible your instructor just glossed over these points. I do accept that as possible too. A teacher has only so much time to spend in class, and some things just seem obvious to a teacher, so they assume it will be just as obvious to the student. So let me do my best to motivate where 0.381966011250105... came from, and how the golden ratio gets into this algorithm.
We have tau to 6 digits as:
tau = 0.381967; % really 0.381966011250105...
How is tau used? In places always like this
alpha2 = a*tau + b*(1-tau);
That is, tau is always used to form a convex linear combination between two end points. You can find more about that term at this link:
But consider what it would mean if tau were 0. What would we see? In that case, alpha2 would always result as b. This would always select the point b, because the coefficient of a is zero.
Likewise, were tau the number 1, we always get the other end point at a, because then the coefficient of b would be zero.
How about tau = 1/2? Then the combination gives us EXACTLY the midpoint between the two, since we then have
alpha2 = a*tau + b*(1-tau) = (a + b)/2
when tau is 1/2. One feature of the search, if we had used tau=1/2, is the search would now reduce to the bisection method.
What you need to recognize is that for various values of tau, we would get SOME point between a and b ONLY when tau is a number between zero and 1. For numbers larger than 1, or smaller than 0, alpha is no longer inside the interval [a,b]. I know, you don't believe me. So TRY IT!
a = 0;
b = 1;
tau = 1.61803398874989;
a*tau + b*(1-tau)
ans =
-0.618033988749895
So if I use tau as 1.618, I do indeed get some value that is no longer even inside the original interval. In fact, this is a basic property of that convex combination we mentioned above. We need to use a number strictly between 0 and 1 in that formula.
So how does the name of the phrase golden section search arise?
I'll write phi as the golden number you know and love:
phi = (sqrt(5) + 1)/2
phi =
1.61803398874989
phi has some neat properties as a number. If you form the inverse, you will see what results is the fractional part of the original number.
1/phi
ans =
0.618033988749895
So if we form
1 + 1/phi
ans =
1.61803398874989
we get phi back all over again!
Anyway, it is this golden ratio that is so nice, and seems to turn up all over the place, in art, in spirals from nature, etc. phi even arises as the limit of the ratio of two consecutive Fibonacci numbers. It falls out of all sorts of things. Have you heard enough about phi as the golden ratio now? Getting just a bit sick of it?
What value of tau were you given to use? We were given tau as:
tau = 0.381966011250105
In the convex combination thing, effectively this splits the interval [0,1] into two segments, of relative length tau and 1-tau. What is the ratio of the lengths of those segments? TRY IT! Aw, come on, guess. I bet it will take onliy one guess at this point.
(1-tau)/tau
ans =
1.61803398874989
Indeed, the value of tau you were given to use is the exact number that causes the two pieces formed by the convex combination of the endpoints of the interval [a,b] to have a relative ratio that just happens to be the golden ratio. We just cannot escape that number, can we? Do anything, and it pops up again. In the back of my head, I can just hear Ahnuld saying the phrase "I'll be back..."
In fact, we can compute the exact value of tau as
tau = 1-1/phi
tau =
0.381966011250105
To recoup all of this, the idea is the golden section search splits the interval [a,b] into two pieces based on a convex linear combination. Those two pieces of the interval, thus of relative lengths tau and 1-tau, themselves have the property that the ratio of their lengths is the golden ratio that you know and love.
In fact, either way we take that ratio, we still seem to get phi back. And it matters not which way we form that ratio.
(1 - tau)/tau
ans =
1.61803398874989
tau/(1 - tau)
ans =
0.618033988749895
I could get into more depth about how this choice of tau is in some way a good one, but I've spent now much time in an attempt to motivate the concept of a convex linear combination, and where the name golden section search comes from. If you want a derivation, it might be just as useful to read what is already written about the search:
  댓글 수: 1
Emil Bucur
Emil Bucur 2020년 5월 29일
wow, thanks a lot, now these things make more sense to me. You are the best

댓글을 달려면 로그인하십시오.

추가 답변 (1개)

Are Mjaavatten
Are Mjaavatten 2020년 5월 29일
편집: Are Mjaavatten 2020년 5월 29일
Let a and b be the end points of the current range. In golden ratio search we choose a new point c such that the ratio of the two lengths and is given by the golden ratio . Denote by r. Then and . It follows that , which is your tau.

카테고리

Help CenterFile Exchange에서 Historical Contests에 대해 자세히 알아보기

태그

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by