非凸优化器 [英] Non convex optimizer
问题描述
我使用python2.7，需要查找多元标量函数的最大值.
I use python2.7 and need to find the maximum of a multivariate scalar function.
换句话说，我具有此功能:
In other words I have this function:
def myFun(a,b,c,d,e,f):
# complex calculation that takes about 30 seconds
return res # res is a float
此函数不是凸的.
我为每个参数a，b，c，d，e和f指定最小和最大可能值.我需要找到参数的哪种组合大致会导致myFun的最大值.我将为它提供一个不错的起点.
I specify the min and max possible value for each argument a, b, c, d, e and f. I need to find what combination of argument approximately result in the maximum value for myFun. I will feed it a decent starting point.
我曾尝试过进行蛮力网格搜索，但是鉴于我的函数需要花费多长时间进行计算，因此它不可行.
I tried doing a brute force grid search but given how long my function takes to compute, it is not viable.
我调查了scipy软件包.我特别看到了 scipy.optimize.fmin_slsqp 函数.那适合我的问题吗?或者，也许 scipy.optimize.fmin() ?
还有其他适合的功能/模块吗?
I have looked into the scipy package. I saw in particular the scipy.optimize.fmin_slsqp function. Would that be appropriate for my problem? Or maybe scipy.optimize.fmin()?
Is there any other function/module that is appropriate for this?
推荐答案
您可能想尝试CVXPY( http ://www.cvxpy.org/en/latest )，这奇怪的是CVXOPT(凸求解器)的非凸扩展名.然后，可以使用CVXOPT进行凸优化，或者使用CVXPY进行非凸优化，
You might want to try CVXPY (http://www.cvxpy.org/en/latest), which is oddly enough a non-convex extension of CVXOPT (a convex solver). Then you can do convex optimization with CVXOPT or non-convex with CVXPY, whatever suits you for the problem.
There are a bunch of non-convex solvers in python, and many of them are listed here: https://scicomp.stackexchange.com/questions/83/is-there-a-high-quality-nonlinear-programming-solver-for-python... but it seems you are actually asking about a continuous solver, which may be local or global, and can handle expensive functions.
我个人建议mystic( https://pypi.python.org/pypi/神秘).的确，我是作者，但是它已经得到了不错的资助，大约十年了，它可以解决其他软件包无法解决的高度受限的非凸问题.它还可以处理具有非线性约束的基本凸优化.另外，mystic是为大规模并行计算而构建的，因此您可以轻松地在多个级别的优化中利用并行计算.如果您有足够的资源，则mystic可以进行整体优化，您可以想像像可以进行网格搜索(可以选择点的初始分布)，而不是在网格上使用固定点，mystic使用并行启动的快速线性求解器.
Personally, I'd suggest mystic (https://pypi.python.org/pypi/mystic). True, I'm the author, but it's been decently funded for about a decade, and it can address highly-constrained non-convex problems that are pretty unsolvable with other packages. It can also handle fundamentally convex optimization with nonlinear constraints. Also, mystic is built for massively parallel computing, so you can easily leverage parallel computing in your optimizations at several levels. If you have enough resources, mystic can do an ensemble optimization, which you can imagine like being able to do a grid search (where you can pick the initial distribution of points), and instead of using fixed points on a grid, mystic uses fast linear solvers launched in parallel.
以下是mystic随附的近100个示例之一:
Here's one of the nearly 100 examples that come with mystic:
'''
Maximize: f = 2*x[0]*x[1] + 2*x[0] - x[0]**2 - 2*x[1]**2
Subject to: x[0]**3 - x[1] == 0
x[1] >= 1
'''
提出了两种解决方案(一种用于线性求解器，一种用于全局求解器):
Two solutions are presented (one for a linear solver, and one a global solver):
def objective(x):
return 2*x[0]*x[1] + 2*x[0] - x[0]**2 - 2*x[1]**2
equations = """
x0**3 - x1 == 0.0
"""
bounds = [(None, None),(1.0, None)]
# with penalty='penalty' applied, solution is:
xs = [1,1]; ys = -1.0
from mystic.symbolic import generate_conditions, generate_penalty
pf = generate_penalty(generate_conditions(equations), k=1e4)
from mystic.symbolic import generate_constraint, generate_solvers, solve
cf = generate_constraint(generate_solvers(solve(equations)))
# inverted objective, used in solving for the maximum
_objective = lambda x: -objective(x)
if __name__ == '__main__':
from mystic.solvers import diffev2, fmin_powell
from mystic.math import almostEqual
result = diffev2(_objective, x0=bounds, bounds=bounds, constraint=cf, penalty=pf, npop=40, ftol=1e-8, gtol=100, disp=False, full_output=True)
assert almostEqual(result[0], xs, rel=2e-2)
assert almostEqual(result[1], ys, rel=2e-2)
result = fmin_powell(_objective, x0=[-1.0,1.0], bounds=bounds, constraint=cf, penalty=pf, disp=False, full_output=True)
assert almostEqual(result[0], xs, rel=2e-2)
assert almostEqual(result[1], ys, rel=2e-2)
这是另一个:
"""
Fit linear and quadratic polynomial to noisy data:
y(x) ~ a + b * x --or-- y(x) ~ a + b * x + c * x**2
where:
0 >= x >= 4
y(x) = y0(x) + yn
y0(x) = 1.5 * exp(-0.2 * x) + 0.3
yn = 0.1 * Normal(0,1)
"""
有解决方案:
from numpy import polyfit, poly1d, linspace, exp
from numpy.random import normal
from mystic.math import polyeval
from mystic import reduced
# Create clean data.
x = linspace(0, 4.0, 100)
y0 = 1.5 * exp(-0.2 * x) + 0.3
# Add a bit of noise.
noise = 0.1 * normal(size=100)
y = y0 + noise
@reduced(lambda x,y: abs(x)+abs(y))
def objective(coeffs, x, y):
return polyeval(coeffs, x) - y
bounds = [(None, None), (None, None), (None, None)]
args = (x, y)
# 'solution' is:
xs = polyfit(x, y, 2)
ys = objective(xs, x, y)
if __name__ == '__main__':
from mystic.solvers import diffev2, fmin_powell
from mystic.math import almostEqual
result = diffev2(objective, args=args, x0=bounds, bounds=bounds, npop=40, ftol=1e-8, gtol=100, disp=False, full_output=True)
assert almostEqual(result[0], xs, tol=1e-1)
assert almostEqual(result[1], ys, rel=1e-1)
result = fmin_powell(objective, args=args, x0=[0.0,0.0,0.0], bounds=bounds, disp=False, full_output=True)
assert almostEqual(result[0], xs, tol=1e-1)
assert almostEqual(result[1], ys, rel=1e-1)
对于并行计算，mystic可以利用pathos和pyina(请参阅: https://github.com /uqfoundation )，您只需传递要用于并行运行的map函数的分层配置即可.很简单这可能不是解决库存问题最快的方法，但是(我认为)它是解决其他原因(由于规模或复杂性)而无法解决的问题的最佳选择.
For parallel computing, mystic can leverage pathos and pyina (see: https://github.com/uqfoundation for both), where you just pass the hierarchical configuration of map functions that you want to use to run in parallel. It's pretty easy. It may not be the fastest for a stock problem, but it is (in my opinion) the best choice for problems that you can't solve otherwise (due to size or complexity).
这篇关于非凸优化器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
