对解析形式不可用的一维昂贵函数的带界约束的纯整数量优化

计算科学 优化 matlab 约束优化 非线性规划 最小二乘
2021-12-15 18:30:41

我有一个计算量大的目标函数,它的分析形式不可用。目标函数的唯一输入参数是一个整数变量。目标是计算最小化目标函数的整数变量。

xsol=argminxϵ[xmin,xmax]f(x)
在哪里x整数f(x)返回一个标量值。

(目标函数是通过求解复杂的非线性耦合偏微分方程系统来计算的)。目标是希望使用某种形式的数据驱动的黑盒优化,它可以解决数值x无需使用耗时/缓慢的 for 循环,因为界限非常大。需要一个到合适求解器的 MATLAB 接口。

2个回答

@Stellos 已经给出了正确的答案,但让我试着用一点直觉来支持它:

想想你的功能f(x)作为一个对任何实值参数都有意义的函数x. 然后,如果该函数恰好是以下形式f(x)=sin(1000x),你会在每个整数点之间有很多最大值和最小值,本质上,哪个数值恰好最小化f(x)归结为机会:整数恰好与高频正弦函数的最小值对齐。换句话说,只是因为你知道f(15)f(17)什么都不告诉你f(16),因此是找到哪个整数的唯一方法x最小化f(x)是尝试所有。

另一方面,想象一下你知道f(x)只是在比整数之间的距离大得多的长度尺度上缓慢变化。那么如果你知道f(16)f(17)f(16)1,您可以运行基于导数的搜索来找到函数的最小值。

同样,如果您知道该函数只会缓慢变化,则可以使用二等分搜索之类的方法来查找位置f(x)0,并且最小值很可能是所有这些临界点的相邻整数之一。

更好的是,如果你知道你的函数是凸函数或凹函数,那么你就会知道只有一个最小值或最大值,再加上可能位于区间端点的函数,你可以再次通过平分。

换句话说,建立目标函数的此类定性属性通常非常有价值,因为它允许您选择更有效的算法,而不是您对自己的目标一无所知。f(x).

没有任何关于f(),找到最大值的唯一选择是通过蛮力,即评估f对于所有整数。现在,如果这实际上是不可能的,你唯一的希望就是确定f和/或其最大值,这将允许通过较少的评估获得最大值f. 例如,如果定义有意义f超过R(实数集)和f也是连续的,您可以执行优化R[xmin,xmax](原则上,这更有效)以缩小您应该寻找最佳值的整数范围。