英文:
Optimisation of a system of inequality relations
问题
I have a coding problem, which I have managed to reduce to the following form:
Given the constant values min, max, a and b, find a value x such that:
min <= |x+a| <= max- |x| >= min
- |x + a - b| is minimized
min, max, a, b and x are all floats.
I'm not aware of any algorithmic methods which treat problems like this one. The fact that all of the variables are floats makes iterating over all possible values impossible. Many thanks for any advice.
英文:
I have a coding problem, which I have managed to reduce to the following form:
Given the constant values min, max, a and b, find a value x such that:
min <= |x+a| <= max|x| >= min|x + a - b|is minimized
min, max, a, b and x are all floats.
I'm not aware of any algorithmic methods which treat problems like this one. The fact that all of the variables are floats makes iterating over all possible values impossible. Many thanks for any advice.
答案1
得分: 3
以下是已翻译的部分：
这个问题中的所有函数都是分段线性的，因此解（如果存在）出现在某个区间的端点处。
x 的感兴趣的端点是 min-a, min+a, -min-a, -min+a, min, -min 和 b-a。我们必须保留那些满足约束条件的端点，即
|min-a|>=min, |min+a|>=min, |-min-a|>=min, |-min+a|>=min,
min<=|-min+a|<=max, min<=|min+a|<=max
和 min<=|b|<=max, |b-a|>min。
然后，对于所有可接受的点，计算目标值并保留最小值。
这可能不是最有效的方法（尽管对于这样一个小问题，效率并不是真正的问题），但它是系统化的，并可以转化为算法。
英文:
All functions in this problem are piecewise linear, hence the solution, if it exists, occurs at an endpoint of some interval.
The endpoints of interest of x are min-a, min+a, -min-a, -min+a, min, -min and b-a. We must keep those that verify the constraints, namely
|min-a|>=min, |min+a|>=min, |-min-a|>=min, |-min+a|>=min,
min<=|-min+a|<=max, min<=|min+a|<=max
and min<=|b|<=max, |b-a|>min.
Then for all points that are admissible, compute the objective and keep the smallest value.
This may not be the most efficient method (though for such a small problem efficiency is not really an issue), but it is systematic and can be turned to an algorithm.
答案2
得分: 1
迭代浮点数不可行但：
您可以避免迭代，观察到线性函数如 f(x)=x-a+b 在区间 x 在 [c,d] 总是在 c 或 d 处达到最大值和最小值（如果区间是开放的，则最大值可能是 +/- 无穷大）。
您的问题可以通过以这种方式迭代少量区间来解决。大致概述如下。
观察到2.意味着 x 在 [min, +infinity] 或 [-infinity, -min] 中。
条件1.有点困难，但它仍然可以表达为区间的总和： x 在 [max(-a,min-a), max-a] 或 [max-a, min(min-a,-a)] 中 - 如果我没有在扩展绝对值时出错的话。（注意 min()，max() 函数的重载）。
因此1.和2.是区间的总和，它们的交集也是区间的总和。
现在，您的目标函数不是完全线性的，但足够接近。它在 [a-b,+infinity] 上是线性的，其中采用 f(x)=x-a+b 的形式，在 [-infinity, a-b] 上采用 f(x)=-x+a-b 的形式。因此，要找到其在区间 [c,d] 上的最大值，您需要考虑将 [c,d] 与上述任一区间相交产生的最多两个区间。
英文:
Iterating over floats is infeasible but:
You can avoid the iteration by observing that a linear function like f(x)=x-a+b taken over an interval x in [c,d] always reaches its maximum and minimum at either c or d (the maximum might be +/- infinity if the interval is open).
Your problem can be transformed into iterating over a small number of intervals in this way. A rough outline below.
Observe that 2. means x is in either [min, +infinity] or [-infinity, -min].
Condition 1. is a bit harder but it can still be expressed as a sum of intervals: x is in either [max(-a,min-a), max-a] or [max-a, min(min-a,-a)] - that is if I didn't make a mistake expanding the absolute values. (Note the overload of min(), max() functions).
So 1. and 2. are sums of intervals, so their intersection is also a sum of intervals.
Now your target function isn't exactly linear, but it is close enough. It is linear on [a-b,+infinity] where it takes the form of f(x)=x-a+b and on [-infinity, a-b] where it takes the form f(x)=-x+a-b. So to find its maximum over an interval [c,d] you need to consider at most two intervals produced by intersecting [c,d] with either of the above intervals.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论