在固定域中找到单个变量函数的 min/max 的算法
Algorithms to find min/max of a single variable function in fixed domain
我正在寻找一种 数值 算法来找到 全局 函数的最小值或最大值 "given interval [a, b]"，例如找到函数的最小值和最大值
f(x) = sin(x)
在域 [3*pi/4, 5*pi/4].
我知道如何使用梯度下降或梯度上升找到多变量函数的全局 min/max，但我只能在整个函数域上使用这些算法，例如当我使用 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，然后比较值，最后它returns最小值出现的x
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;
}
这里有很多功能你可能不熟悉，它们被编码在单独的文件中。你可以在 my Github repository.
看到它们
梯度ascent/descent只能找到局部最优，为了找到"global"最优你只需要运行那个过程随机多次初始化，并取你找到的最佳值。
你也可以在你的情况下做同样的事情：取随机初始点并跟随梯度，在收敛处或当你走出域时停止。
您可以通过在退出时动态限制域来加快速度。例如，假设您要在 -10 到 10 之间最大化，并选择 6 作为初始点；你 运行 梯度上升并达到 10。你现在可以从随机初始化中排除间隔 [6,10]，因为你知道你最终会达到 10 并停在那里。
但实际上我建议您使用 Bayesian optimization。它相对于梯度 ascent/descent 的优点是：
- 不需要渐变
- 专为全局优化而设计
- 允许设置参数范围
- 需要更少的函数评估
最后，必须提醒一句：这个问题无法解决在一般情况下，考虑例如在 x=3.4131242351 处等于 1 且在其他任何地方都等于 0 的函数。但是，实际上，您应该没问题。
我正在寻找一种 数值 算法来找到 全局 函数的最小值或最大值 "given interval [a, b]"，例如找到函数的最小值和最大值
f(x) = sin(x)
在域 [3*pi/4, 5*pi/4].
我知道如何使用梯度下降或梯度上升找到多变量函数的全局 min/max，但我只能在整个函数域上使用这些算法，例如当我使用 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，然后比较值，最后它returns最小值出现的x
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;
}
这里有很多功能你可能不熟悉，它们被编码在单独的文件中。你可以在 my Github repository.
看到它们梯度ascent/descent只能找到局部最优，为了找到"global"最优你只需要运行那个过程随机多次初始化，并取你找到的最佳值。
你也可以在你的情况下做同样的事情：取随机初始点并跟随梯度，在收敛处或当你走出域时停止。
您可以通过在退出时动态限制域来加快速度。例如，假设您要在 -10 到 10 之间最大化，并选择 6 作为初始点；你 运行 梯度上升并达到 10。你现在可以从随机初始化中排除间隔 [6,10]，因为你知道你最终会达到 10 并停在那里。
但实际上我建议您使用 Bayesian optimization。它相对于梯度 ascent/descent 的优点是：
- 不需要渐变
- 专为全局优化而设计
- 允许设置参数范围
- 需要更少的函数评估
最后，必须提醒一句：这个问题无法解决在一般情况下，考虑例如在 x=3.4131242351 处等于 1 且在其他任何地方都等于 0 的函数。但是，实际上，您应该没问题。