Я искал численный алгоритм для поиска глобального минимума или максимума функции в "заданном интервале [a, b]", например, для нахождения минимума и максимума функции
f (x) = грех (x)
в домене [3 * пи / 4, 5 * пи / 4].
Я знаю, как найти глобальные мин / макс функции с несколькими переменными, используя Gradient Descent или Gradient Ascend, но я могу использовать эти алгоритмы только во всей области функций, например, когда использую GD для функции sin ( x), он дает мне -1, что правильно для домена [0, 2 * pi], а не [3 * pi / 4, 5 * pi / 4], любая помощь?
Я дошел до этого решения (код на python 2.7, язык не важен, мои вопросы касаются алгоритмов):
import math
import random
# function
def f(x):
return math.sin(x)
# xmin-xmax interval
xmin = 3.0 * math.pi / 4.0
xmax = 5.0 * math.pi / 4.0
# find ymin-ymax
steps = 10000
ymin = f(xmin)
ymax = ymin
for i in range(steps):
x = xmin + (xmax - xmin) * float(i) / steps
y = f(x)
if y < ymin: ymin = y
if y > ymax: ymax = y
print ymin
print ymax
ответ
благодаря @BlackBear, я написал программу, которая делает то, что мне действительно нужно, эта функция ищет через интервал [a, b] с использованием алгоритма градиентного спуска, в каждом цикле она начинается с новой случайной начальной точки между a и b, затем сравнивает значения, в конце возвращает х, где происходит минимум
double gradientDescentInterval(const char *expression, double a, double b, double ete, double ere, double gamma,
unsigned int maxiter, int mode) {
/*
* Gradient descent is a first-order iterative optimization algorithm for finding the minimum of a function.
* To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of
* the gradient (or approximate gradient) of the function at the current point.
*
* This function searches minimum on an interval [a, b]
*
* ARGUMENTS:
* expressions the function expression, it must be a string array like "x^2+1"
* a starting point of interval [a, b]
* b ending point of interval [a, b]
* ete estimated true error
* ere estimated relative error
* gamma step size (also known as learning rate)
* maxiter maximum iteration threshold
* mode show process {0: no, 1: yes}
*
*/
// fix interval reverse
if (a > b) {
double temp = a;
a = b;
b = temp;
} // end of if
// check error thresholds
if (ere < 0 || ete < 0) {
printf("\nError: ete or ere argument is not valid\n");
Exit();
exit(EXIT_FAILURE);
} // end of if
// check mode
if (mode != 0 && mode != 1) {
printf("\nError: mode argument is not valid\n");
Exit();
exit(EXIT_FAILURE);
} // end of if
// check maxiter to be more than zero
if (maxiter <= 0) {
printf("Error: argument maxiter must be more than zero!\n");
Exit();
exit(EXIT_FAILURE);
} // end of maxiter check
// initializing variables
unsigned int iter = 0, innerIter = 0;
// choose an arbitrary result at midpoint between a and b to be updated later
double coefficient = (b - a), result = a + coefficient / 2;
double x, past_x, fx, fresult;
double ete_err, ere_err;
double fa = function_1_arg(expression, a);
double fb = function_1_arg(expression, b);
// set the seed for random number generator
seed();
while (iter < maxiter) {
// try maxiter times to find minimum in given interval [a, b] and return lowest result
// update fresult with new result
fresult = function_1_arg(expression, result);
// choose a random starting point
x = a + coefficient * zeroToOneUniformRandom();
// set inner iter to zero before new loop
innerIter = 0;
// go in a loop to find a minimum with random starting point
while (innerIter < maxiter) {
// calculate new x by subtracting the derivative of function at x multiplied by gamma from x
past_x = x;
x -= firstDerivative_1_arg(expression, x, DX) * gamma;
fx = function_1_arg(expression, x);
// calculate errors
ete_err = fabs(past_x - x);
ere_err = fabs(ete_err / x);
if (mode) {
printf("\nIn this iteration [#%d][#%d], x = %.5e f(x) = %.5e\n"
"and estimated true error = %.5e and estimated relative error = %.5e,\n",
iter, innerIter, x, fx, ete_err, ere_err);
} // end if(mode)
// Termination Criterion
// if new x goes beyond interval lower than a
if (x < a) {
if (mode) {
printf("\nIn this iteration the calculated x is less than a : %.5e < %f"
"so minimum of the function occurs at a\n",
x, a);
} // end if(mode)
// if fa is lower than f(result), then a is where the minimum occurs
if (fa < fresult) {
result = a;
} // end of if
break;
} // end of if
// if new x goes beyond interval bigger than b
if (x > b) {
if (mode) {
printf("\nIn this iteration the calculated x is bigger than b : %.5e > %f"
"so minimum of the function occurs at b\n",
x, b);
} // end if(mode)
// if fb is lower than f(result), then b is where the minimum occurs
if (fb < fresult) {
result = b;
} // end of if
break;
} // end of if
// if calculated error is less than estimated true error threshold
if (ete != 0 && ete_err < ete) {
if (mode) {
printf("\nIn this iteration the calculated estimated true error is less than the threshold\n"
"(estimated true error) %.5e < %.5e (threshold)\n"
"so the calculated x is the point on domain that minimum of the function happens\n",
ete_err, ete);
} // end if(mode)
// if fx is lower than f(result), then x is where the minimum occurs
if (fx < fresult) {
result = x;
} // end of if
break;
} // end of estimated true error check
// if calculated error is less than estimated relative error threshold
if (ere != 0 && ere_err < ere) {
if (mode) {
printf("\nIn this iteration the calculated estimated real error is less than the threshold\n"
"(estimated real error) %.5e < %.5e (threshold)\n"
"so the calculated x is the point on domain that minimum of the function happens\n",
ere_err, ere);
} // end if(mode)
// if fx is lower than f(result), then x is where the minimum occurs
if (fx < fresult) {
result = x;
} // end of if
break;
} // end of estimated relative error check
innerIter++;
} // end of inner while loop
iter++;
} // end of while loop
// return result
return result;
}
многие функции здесь могут показаться вам неизвестными, они закодированы в отдельных файлах. вы можете увидеть их в моем репозитории Github .