在python中最小化函数的最快方法是什么?
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了在python中最小化函数的最快方法是什么?,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5262字,纯文字阅读大概需要8分钟。
内容图文
所以我有以下问题要尽量减少.我有一个我需要找到的向量w,以便最小化以下功能:
import numpy as np
from scipy.optimize import minimize
matrix = np.array([[1.0, 1.5, -2.],
[0.5, 3.0, 2.5],
[1.0, 0.25, 0.75]])
def fct(x):
return x.dot(matrix).dot(x)
x0 = np.ones(3) / 3
cons = ({'type': 'eq', 'fun': lambda x: x.sum() - 1.0})
bnds = [(0, 1)] * 3
w = minimize(fct, x0, method='SLSQP', bounds=bnds, constraints=cons)['x']
我选择了方法=’SLSQP’,因为它似乎是唯一允许边界和约束的方法.我的问题是我必须在多个选择上循环我的解决方案,所以我想在这里获得一些速度.我的解决方案是使用优化器的最快的解决方案还是还有其他更快的解决方案?谢谢.
解决方法:
介绍
一般来说,最快的方法始终是最适合问题的方法.
由于scipy.minimize中的所有优化算法都非常普遍,所以会有
始终是更快的方法,从问题的特殊特征中获得性能.
这将是一个权衡,需要做多少分析和工作来获得性能.
重要的是要注意,例如SLSQP是一种能够实现的算法
解决非凸问题,在这种情况下,可以保证收敛到某些局部最优
(忽略实现中的数字问题;这总是一个可能的问题).
这种功能需要付出代价:与算法相比,SLSQP的速度更快,稳定性更低
这是专为凸问题设计的(甚至在凸问题中也是如此)
它们都是多项式可解的,线性编程和更难的更容易
作为SemidefiniteProgramming).
问题分析
如上面的评论所示,对于一些一般的不定矩阵M,这个问题
是非凸的(概率很高;我没有提供正式的证明),这意味着,
如果没有进一步的假设,就没有一般可行的方法(忽略
特殊分析,因为一些非凸问题可以在多项式时间内全局求解).
这意味着:
> scipy中的每个优化算法,最多都会保证局部最优,这可能
与全局最优相比,任意不好
假设:M是正定/负定
如果我们假设矩阵M是正定或负定,但不是不定的,这是一个凸优化问题.您似乎对此案感兴趣,这里有一些评论和方法.
这意味着:
> SLSQP保证收敛到全球最优
>您可以使用专为凸优化问题设计的求解器
>商业解决方案:Gurobi,CPLEX,Mosek
>开源解算器:ECOS,SCS
使用Python cvxpy ecos / scs的示例代码
除了用于线性编程的linprog之外,没有特殊的凸优化求解器
因此无法解决这个问题.
还有其他选择,如上所述,有很多可能的路线
使用它们.
在这里,我将介绍一个最简单的:
> cvxpy用于模型配方
>它会自动证明这个问题是凸出的!
>(模型构建和凸性推理可能代价高昂)
> ecos
>用于许多凸优化问题的通用求解器
>基于内点法
> scs
>用于许多凸优化问题的通用求解器
>基于乘法器的交替方向法(ADMM)
>支持两种不同的方法来求解线性方程:
>直接(基于分解)
>间接(基于共轭梯度)
> GPU支持这个,因为它是关于矩阵矢量产品
>与ECOS相比,一般来说解决方案不太准确,但通常要快得多
示例代码:
>使用示例:
> 1000×1000矩阵
>解决者:SCS
>间接模式
> CPU
>多线程(如果BLAS可用,则自动)
码:
import time
import numpy as np
from cvxpy import * # Convex-Opt
""" Create some random pos-def matrix """
N = 1000
matrix_ = np.random.normal(size=(N,N))
matrix = np.dot(matrix_, matrix_.T)
""" CVXPY-based Convex-Opt """
print('\ncvxpy\n')
x = Variable(N)
constraints = [x >= 0, x <= 1, sum(x) == 1]
objective = Minimize(quad_form(x, matrix))
problem = Problem(objective, constraints)
time_start = time.perf_counter()
problem.solve(solver=SCS, use_indirect=True, verbose=True) # or: solver=ECOS
time_end = time.perf_counter()
print(problem.value)
print('cvxpy (modelling) + ecos/scs (solving) used (secs): ', time_end - time_start)
示例输出:
cvxpy
----------------------------------------------------------------------------
SCS v1.2.6 - Splitting Conic Solver
(c) Brendan O'Donoghue, Stanford University, 2012-2016
----------------------------------------------------------------------------
Lin-sys: sparse-indirect, nnz in A = 1003002, CG tol ~ 1/iter^(2.00)
eps = 1.00e-03, alpha = 1.50, max_iters = 2500, normalize = 1, scale = 1.00
Variables n = 1001, constraints m = 3003
Cones: primal zero / dual free vars: 1
linear vars: 2000
soc vars: 1002, soc blks: 1
Setup time: 6.76e-02s
----------------------------------------------------------------------------
Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
0| inf inf -nan -inf -inf inf 1.32e-01
100| 1.54e-02 1.48e-04 7.63e-01 -5.31e+00 -4.28e+01 1.10e-11 1.15e+00
200| 1.53e-02 1.10e-04 7.61e-01 -3.87e+00 -3.17e+01 1.08e-11 1.95e+00
300| 1.53e-02 7.25e-05 7.55e-01 -2.47e+00 -2.08e+01 1.07e-11 2.79e+00
400| 1.53e-02 3.61e-05 7.39e-01 -1.11e+00 -1.03e+01 1.06e-11 3.61e+00
500| 7.64e-03 2.55e-04 1.09e-01 -2.01e-01 -6.32e-02 1.05e-11 4.64e+00
560| 7.71e-06 4.24e-06 8.61e-04 2.17e-01 2.16e-01 1.05e-11 5.70e+00
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 5.70e+00s
Lin-sys: avg # CG iterations: 1.71, avg solve time: 9.98e-03s
Cones: avg projection time: 3.97e-06s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 5.1560e-16, dist(y, K*) = 0.0000e+00, s'y/|s||y| = 2.4992e-17
|Ax + s - b|_2 / (1 + |b|_2) = 7.7108e-06
|A'y + c|_2 / (1 + |c|_2) = 4.2390e-06
|c'x + b'y| / (1 + |c'x| + |b'y|) = 8.6091e-04
----------------------------------------------------------------------------
c'x = 0.2169, -b'y = 0.2157
============================================================================
0.21689554805292935
cvxpy (modelling) + ecos/scs (solving) used (secs): 7.105745473999832
例如:5000×5000使用~9分钟(没有调整参数).
一些微小的额外评论:
> SCS比ECOS更快(预期)
> SCS / ECOS比天真更快(不给jacobi-matrix)SLSQP(至少每个N> = 100);更快=大N的数量级
>对于小例子,我检查了这种方法与SLSQP相比的等价性
内容总结
以上是互联网集市为您收集整理的在python中最小化函数的最快方法是什么?全部内容,希望文章能够帮你解决在python中最小化函数的最快方法是什么?所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。