X的最小化函数
X的最小化函数
提问于 2016-09-20 01:37:53
我有一个函数需要最小化，
其中x1，y1，x2，y2，v2，v1都是给我的。我必须找到这个函数对于任意x的全局最小值。
我计算出函数的全局最小值将是关于x的，在min(x1，x2)和max(x1，x2)之间，并且在范围之间的函数应该是U型曲线。因此，以low=min(x1，x2)和high=max(x1，x2)为例，我进行了二进制搜索，其中我采用了效率参数e=0.000001，并在二进制搜索中给出了以下条件
如果(f(mid+e)< f(mid)) high=mid-e；否则low=mid+e；
但是，我没有得到正确的结果。我正在寻找一个6-7小数位的准确性。任何代码/伪代码形式的帮助都将不胜感激。
回答 1
Stack Overflow用户
发布于 2016-09-20 04:17:22
这个问题看起来是非凸的，这通常是一个问题，因为非凸优化是非常困难的。特别是与对高精度解决方案的渴望相结合。一般来说，这是不可行的(找到任何全局最小值)，但对于如此小的问题，有机会(但准确性可能仍然是一个问题)。
下面的代码(python + scipy + pyomo + couenne)只是一些可能的方法的演示。当然，最好的方法将使用函数的一些特征。
- scipy：开源通用科学函数library
- pyomo：开源线性/非线性数学规划library
- couenne：开源全局MINLP求解器
一般的想法是：
- 使用经过充分测试的标量最小化算法(如brent's algorithm )来解决您的问题
- 这对您来说可能就足够了(但在大多数languages
中无法获得全局解决方案
- 与使用求解器couenne
- 的非凸/非线性MINLP方法进行比较查看couenne的文档，以了解什么将发生MINLP
- 只是为了好玩:使用couenne的解决方案并尝试改进它，并使用上面的标量最小化方法(这一次:更保守/安全的方法
golden和bounded；brentq使用一些重技巧来加快收敛速度)，couenne的全局最小值作为界(并通过一些小的常量eps)
扩大
代码
from __future__ import division
from scipy.optimize import minimize_scalar, brute
import math
""" Constants """
x1 =3
x2 = 1
y1 = 0.5
y2 = 3
v1 = 2
v2 = 2
""" Scipy-based 1d-minimization using brentq (local-optimal) """
def f(x):
return math.sqrt(x**2 - 2*x1*x + x1**2 + y1**2) / v1 + \
math.sqrt(x**2 - 2*x2*x + x2**2 + y2**2) / v2
res = minimize_scalar(f)
print('Brentq: ', res.x)
""" Pyomo + Couenne based minimization (global-optimal) """
from pyomo.environ import *
from pyomo.opt import SolverFactory
model = ConcreteModel()
model.x = Var()
model.obj = Objective(expr=sqrt(model.x**2 - 2*x1*model.x + x1**2 + y1**2) / v1 + \
sqrt(model.x**2 - 2*x2*model.x + x2**2 + y2**2) / v2, sense=minimize)
opt = SolverFactory('couenne')
results = opt.solve(model)
print('Couenne: ', model.x.value)
""" Reopt 1d-minimization ("golden" + "bounded") with obtained bounds by couenne """
eps = 0.001
res = minimize_scalar(f, method='bounded', bounds=(model.x.value - eps, model.x.value + eps),
options={'xatol': 1e-9, 'maxiter': 1000})
print('Couenne reopt (bounded): ', res.x)
res = minimize_scalar(f, method='golden', bounds=(model.x.value - eps, model.x.value + eps),
options={'xtol': 1e-9})
print('Couenne reopt (golden): ', res.x)输出
Brentq:
2.71428567406
f(x)
2.01556443707
Couenne:
2.71428571429
f(x)
2.01556443707
Couenne reopt (bounded):
2.71428573487
f(x)
2.01556443707
Couenne reopt (golden):
2.71428570645
f(x)
2.01556443707这些优化器的性能可能在很大程度上取决于所选的问题常量。你必须决定走哪条路线。我不知道您使用的是哪种语言，也不知道哪些库可用。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39579015
复制相关文章
相似问题
腾讯云开发者
