scipy.optimize.

minimize#

scipy.optimize.minimize(fun, x0, args=(), method=None, jac=None, hess=None, hessp=None, bounds=None, constraints=(), tol=None, callback=None, options=None)[source]#

一个或多个变量的标量函数最小化。

参数:
fun可调用对象

要最小化的目标函数

fun(x, *args) -> float

其中 x 是一个形状为 (n,) 的一维数组,args 是一个元组,包含完全指定函数所需的固定参数。

假设可调用对象具有签名 f0(x, *my_args, **my_kwargs),其中 my_argsmy_kwargs 是必需的位置参数和关键字参数。与其将 f0 作为可调用对象传递,不如将其包装为只接受 x;例如,将 fun=lambda x: f0(x, *my_args, **my_kwargs) 作为可调用对象传递,其中 my_args (元组) 和 my_kwargs (字典) 已在此函数调用前收集。

x0ndarray,形状 (n,)

初始猜测。大小为 (n,) 的实数元素数组,其中 n 是独立变量的数量。

args元组,可选

传递给目标函数及其导数(funjachess 函数)的额外参数。

method字符串或可调用对象,可选

求解器类型。应为以下之一:

如果未给出,则根据问题是否有约束或边界,选择 BFGSL-BFGS-BSLSQP 之一。

jac{可调用对象, ‘2-point’, ‘3-point’, ‘cs’, 布尔值},可选

计算梯度向量的方法。仅适用于 CG、BFGS、Newton-CG、L-BFGS-B、TNC、SLSQP、dogleg、trust-ncg、trust-krylov、trust-exact 和 trust-constr。如果它是可调用对象,它应该是一个返回梯度向量的函数

jac(x, *args) -> array_like, shape (n,)

其中 x 是一个形状为 (n,) 的数组,args 是一个包含固定参数的元组。如果 jac 是布尔值且为 True,则假定 fun 返回一个包含目标函数和梯度的元组 (f, g)。方法 ‘Newton-CG’、‘trust-ncg’、‘dogleg’、‘trust-exact’ 和 ‘trust-krylov’ 要求提供可调用对象,或 fun 返回目标和梯度。如果为 None 或 False,梯度将使用具有绝对步长的 2 点有限差分估计。或者,可以使用关键字 {‘2-point’, ‘3-point’, ‘cs’} 选择一种有限差分方案,用于以相对步长数值估计梯度。这些有限差分方案遵循任何指定的 bounds

hess{可调用对象, ‘2-point’, ‘3-point’, ‘cs’, HessianUpdateStrategy},可选

计算Hessian矩阵的方法。仅适用于 Newton-CG、dogleg、trust-ncg、trust-krylov、trust-exact 和 trust-constr。如果它是可调用对象,它应该返回 Hessian 矩阵

hess(x, *args) -> {LinearOperator, spmatrix, array}, (n, n)

其中 x 是一个 (n,) ndarray,args 是一个包含固定参数的元组。关键字 {‘2-point’, ‘3-point’, ‘cs’} 也可以用来选择一种有限差分方案来数值估计 Hessian。或者,实现 HessianUpdateStrategy 接口的对象可以用来近似 Hessian。实现此接口的可用拟牛顿方法是

并非所有选项都适用于每种方法;有关可用性,请参阅注释。

hessp可调用对象,可选

目标函数的 Hessian 乘以任意向量 p。仅适用于 Newton-CG、trust-ncg、trust-krylov、trust-constr。只需提供 hessphess 中的一个。如果提供了 hess,则 hessp 将被忽略。hessp 必须计算 Hessian 乘以任意向量

hessp(x, p, *args) ->  ndarray shape (n,)

其中 x 是一个 (n,) ndarray,p 是一个维度为 (n,) 的任意向量,args 是一个包含固定参数的元组。

bounds序列或 Bounds,可选

Nelder-Mead、L-BFGS-B、TNC、SLSQP、Powell、trust-constr、COBYLA 和 COBYQA 方法的变量边界。有两种方法可以指定边界

  1. Bounds 类的实例。

  2. x 中每个元素的 (min, max) 对序列。None 用于指定无边界。

constraints{Constraint, dict} 或 {Constraint, dict} 列表,可选

约束定义。仅适用于 COBYLA、COBYQA、SLSQP 和 trust-constr。

‘trust-constr’、‘cobyqa’ 和 ‘cobyla’ 的约束定义为一个对象或一个对象列表,用于指定优化问题的约束。可用约束为

COBYLA、SLSQP 的约束定义为字典列表。每个字典包含字段

type字符串

约束类型:‘eq’ 表示等式约束,‘ineq’ 表示不等式约束。

fun可调用对象

定义约束的函数。

jac可调用对象,可选

fun 的 Jacobian(仅适用于 SLSQP)。

args序列,可选

要传递给函数和 Jacobian 的额外参数。

等式约束表示约束函数结果为零,而不等式约束表示其为非负数。请注意,COBYLA 仅支持不等式约束。

tol浮点数,可选

终止容差。当指定 tol 时,所选的最小化算法会将一些相关的求解器特定容差设置为 tol。要进行详细控制,请使用求解器特定选项。

options字典,可选

求解器选项字典。除了 TNC 之外的所有方法都接受以下通用选项

maxiter整数

执行的最大迭代次数。根据方法,每次迭代可能使用多次函数评估。

对于 TNC,请使用 maxfun 而非 maxiter

disp布尔值

设置为 True 以打印收敛消息。

有关方法特定选项,请参阅 show_options

callback可调用对象,可选

每次迭代后调用的可调用对象。

除了 TNC 和 SLSQP 之外的所有方法都支持具有以下签名的可调用对象

callback(intermediate_result: OptimizeResult)

其中 intermediate_result 是一个关键字参数,包含一个 OptimizeResult 对象,其属性为 xfun,分别表示参数向量和目标函数的当前值。并非 OptimizeResult 的所有属性都可能存在。回调函数要接收 OptimizeResult 对象,参数名称必须是 intermediate_result。如果回调函数引发 StopIteration,这些方法也将终止。

除了 trust-constr 之外的所有方法(也)支持类似如下的签名

callback(xk)

其中 xk 是当前参数向量。

使用内省来确定调用上述哪个签名。

返回:
resOptimizeResult

优化结果表示为一个 OptimizeResult 对象。重要的属性包括:x 解决方案数组,success 一个布尔标志,指示优化器是否成功退出,以及 message 描述终止原因。有关其他属性的描述,请参阅 OptimizeResult

另请参阅

minimize_scalar

标量单变量函数最小化算法的接口

show_options

求解器接受的额外选项

备注

本节描述了可通过 ‘method’ 参数选择的可用求解器。默认方法是 *BFGS*。

无约束最小化

方法 CG 使用 Polak 和 Ribiere 的非线性共轭梯度算法,是 [5] 第 120-122 页描述的 Fletcher-Reeves 方法的变体。仅使用一阶导数。

方法 BFGS 使用 Broyden、Fletcher、Goldfarb 和 Shanno (BFGS) 的拟牛顿方法 [5] 第 136 页。它仅使用一阶导数。即使对于非光滑优化,BFGS 也已被证明具有良好的性能。此方法还返回 Hessian 逆的近似值,以 hess_inv 存储在 OptimizeResult 对象中。

方法 Newton-CG 使用 Newton-CG 算法 [5] 第 168 页(也称为截断牛顿法)。它使用 CG 方法计算搜索方向。另请参阅 TNC 方法,该方法用于具有类似算法的箱式约束最小化。适用于大规模问题。

方法 dogleg 使用 dog-leg 信赖域算法 [5] 进行无约束最小化。此算法需要梯度和 Hessian;此外,Hessian 必须是正定的。

方法 trust-ncg 使用牛顿共轭梯度信赖域算法 [5] 进行无约束最小化。此算法需要梯度以及 Hessian 或一个计算 Hessian 与给定向量乘积的函数。适用于大规模问题。

方法 trust-krylov 使用牛顿 GLTR 信赖域算法 [14], [15] 进行无约束最小化。此算法需要梯度以及 Hessian 或一个计算 Hessian 与给定向量乘积的函数。适用于大规模问题。对于不定问题,它通常比 trust-ncg 方法需要更少的迭代次数,推荐用于中型和大型问题。

方法 trust-exact 是一种用于无约束最小化的信赖域方法,其中二次子问题几乎精确求解 [13]。此算法需要梯度和 Hessian(*不*要求是正定的)。在许多情况下,它是迭代次数更少的牛顿方法,最推荐用于小型和中型问题。

边界约束最小化

方法 Nelder-Mead 使用单纯形算法 [1], [2]。此算法在许多应用中都很稳健。但是,如果数值计算的导数是可信的,通常更倾向于使用一阶和/或二阶导数信息的其他算法,因为它们具有更好的性能。

方法 L-BFGS-B 使用 L-BFGS-B 算法 [6], [7] 进行边界约束最小化。

方法 Powell 是 Powell 方法 [3], [4] 的修改版,它是一种共轭方向法。它沿着方向集(optionsinfo 中的 direc 字段)的每个向量执行顺序一维最小化,该方向集在主最小化循环的每次迭代中都会更新。该函数不需要可微分,也不会进行导数计算。如果未提供边界,则将使用无界线搜索。如果提供了边界且初始猜测在边界内,则整个最小化过程中的每次函数评估都将在边界内。如果提供了边界,初始猜测在边界之外,并且 direc 是满秩的(默认为满秩),那么第一次迭代中的某些函数评估可能在边界之外,但第一次迭代之后的所有函数评估都将在边界内。如果 direc 不是满秩的,则某些参数可能无法优化,并且不能保证解决方案在边界内。

方法 TNC 使用截断牛顿算法 [5], [8] 最小化受边界约束的变量函数。此算法使用梯度信息;它也称为牛顿共轭梯度法。它与上面描述的 *Newton-CG* 方法不同,因为它封装了 C 实现并允许为每个变量指定上限和下限。

约束最小化

方法 COBYLA 使用 PRIMA 实现 [19] 的基于线性近似的约束优化 (COBYLA) 方法 [9], [10], [11]。该算法基于目标函数和每个约束的线性近似。

方法 COBYQA 使用基于二次近似的约束优化 (COBYQA) 方法 [18]。该算法是一种基于目标函数和每个非线性约束的二次近似的无导数信赖域 SQP 方法。边界被视为不可放松的约束,即算法在整个优化过程中始终遵守它们。

方法 SLSQP 使用序贯最小二乘规划来最小化具有边界、等式和不等式约束任意组合的多元函数。该方法封装了 Dieter Kraft 最初实现的 SLSQP 优化子例程 [12]。请注意,包装器通过将边界中的无限值转换为大的浮点值来处理它们。

方法 trust-constr 是一种用于约束优化的信赖域算法。它根据问题定义在两种实现之间切换。它是 SciPy 中实现的功能最强大的约束最小化算法,最适合大规模问题。对于等式约束问题,它是 [17][5] 第 549 页中描述的 Byrd-Omojokun 信赖域 SQP 方法的实现。当也施加不等式约束时,它切换到 [16] 中描述的信赖域内点法。该内点算法反过来通过引入松弛变量并解决一系列等式约束障碍问题来处理不等式约束,障碍参数的值逐渐减小。先前描述的等式约束 SQP 方法用于解决子问题,随着迭代接近解决方案,精度水平逐渐提高。

有限差分选项

对于方法 trust-constr,梯度和 Hessian 可以使用三种有限差分方案进行近似:{‘2-point’, ‘3-point’, ‘cs’}。‘cs’ 方案可能是最精确的,但它要求函数能正确处理复数输入并在复平面上可微分。‘3-point’ 方案比 ‘2-point’ 更精确,但需要两倍的操作。如果梯度通过有限差分估计,Hessian 必须使用一种拟牛顿策略进行估计。

`hess` 关键字的方法特定选项

方法/Hess

None

可调用对象

‘2-point/’3-point’/’cs’

HUS

Newton-CG

x

(n, n) LO

x

x

dogleg

(n, n)

trust-ncg

(n, n)

x

x

trust-krylov

(n, n)

x

x

trust-exact

(n, n)

trust-constr

x

(n, n) LO sp

x

x

其中 LO=LinearOperator,sp=稀疏矩阵,HUS=HessianUpdateStrategy

自定义最小化器

传递自定义最小化方法可能很有用,例如在使用此方法的前端(如 scipy.optimize.basinhopping)或不同的库时。您可以简单地将可调用对象作为 method 参数传递。

该可调用对象将以 method(fun, x0, args, **kwargs, **options) 的形式调用,其中 kwargs 对应于传递给 minimize 的任何其他参数(例如 callbackhess 等),除了 options 字典,它的内容也会作为 method 参数逐对传递。此外,如果 jac 以布尔类型传递,jacfun 会被修改,使得 fun 只返回函数值,并且 jac 转换为返回 Jacobian 的函数。该方法应返回一个 OptimizeResult 对象。

提供的 method 可调用对象必须能够接受(并可能忽略)任意参数;minimize 接受的参数集在未来版本中可能会扩展,届时这些参数将传递给该方法。您可以在 scipy.optimize 教程中找到一个示例。

参考文献

[1]

Nelder, J A, and R Mead. 1965. 函数最小化的单纯形法. The Computer Journal 7: 308-13.

[2]

Wright M H. 1996. 直接搜索方法:曾遭鄙弃,今受推崇,收录于 Numerical Analysis 1995: Proceedings of the 1995 Dundee Biennial Conference in Numerical Analysis (编者 D F Griffiths 和 G A Watson). Addison Wesley Longman, Harlow, UK. 191-208.

[3]

Powell, M J D. 1964. 一种不计算导数寻找多元函数最小值的高效方法. The Computer Journal 7: 155-162.

[4]

Press W, S A Teukolsky, W T Vetterling 和 B P Flannery. 数值秘籍 (任何版本), Cambridge University Press.

[5] (1,2,3,4,5,6,7,8)

Nocedal, J, and S J Wright. 2006. 数值优化. Springer New York.

[6]

Byrd, R H and P Lu and J. Nocedal. 1995. 一种用于边界约束优化的有限内存算法. SIAM Journal on Scientific and Statistical Computing 16 (5): 1190-1208.

[7]

Zhu, C and R H Byrd and J Nocedal. 1997. L-BFGS-B: 算法 778: L-BFGS-B, 用于大规模边界约束优化的 FORTRAN 例程. ACM Transactions on Mathematical Software 23 (4): 550-560.

[8]

Nash, S G. 通过 Lanczos 方法进行牛顿型最小化. 1984. SIAM Journal of Numerical Analysis 21: 770-778.

[9]

Powell, M J D. 一种通过线性插值对目标函数和约束函数建模的直接搜索优化方法. 1994. Advances in Optimization and Numerical Analysis, eds. S. Gomez 和 J-P Hennart, Kluwer Academic (Dordrecht), 51-67.

[10]

Powell M J D. 用于优化计算的直接搜索算法. 1998. Acta Numerica 7: 287-336.

[11]

Powell M J D. 无导数优化算法综述. 2007. 剑桥大学技术报告 DAMTP 2007/NA03

[12]

Kraft, D. 序贯二次规划软件包. 1988. 技术报告 DFVLR-FB 88-28, DLR German Aerospace Center – Institute for Flight Mechanics, Koln, Germany.

[13]

Conn, A. R., Gould, N. I., and Toint, P. L. 信赖域方法. 2000. Siam. pp. 169-200.

[14]

F. Lenders, C. Kirches, A. Potschka: “trlib: 一种用于迭代求解信赖域问题的无向量 GLTR 方法实现”, arXiv:1611.04718

[15]

N. Gould, S. Lucidi, M. Roma, P. Toint: “使用 Lanczos 方法求解信赖域子问题”, SIAM J. Optim., 9(2), 504–525, (1999).

[16]

Byrd, Richard H., Mary E. Hribar, and Jorge Nocedal. 1999. 一种用于大规模非线性规划的内点算法. SIAM Journal on Optimization 9.4: 877-900.

[17]

Lalee, Marucha, Jorge Nocedal, and Todd Plantenga. 1998. 关于大规模等式约束优化算法的实现. SIAM Journal on Optimization 8.3: 682-706.

[18]

Ragonneau, T. M. *基于模型的无导数优化方法和软件*. 博士论文,香港理工大学应用数学系,中国香港,2022。URL: https://theses.lib.polyu.edu.hk/handle/200/12294

[19]

Zhang, Z. “PRIMA:Powell 方法的现代化和改进参考实现”, https://www.libprima.net, DOI:10.5281/zenodo.8052654

示例

让我们考虑最小化 Rosenbrock 函数的问题。该函数(及其相应的导数)在 rosen(分别为 rosen_derrosen_hess)中由 scipy.optimize 实现。

>>> from scipy.optimize import minimize, rosen, rosen_der

*Nelder-Mead* 方法的一个简单应用是

>>> x0 = [1.3, 0.7, 0.8, 1.9, 1.2]
>>> res = minimize(rosen, x0, method='Nelder-Mead', tol=1e-6)
>>> res.x
array([ 1.,  1.,  1.,  1.,  1.])

现在使用 *BFGS* 算法,利用一阶导数和一些选项

>>> res = minimize(rosen, x0, method='BFGS', jac=rosen_der,
...                options={'gtol': 1e-6, 'disp': True})
Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 26
         Function evaluations: 31
         Gradient evaluations: 31
>>> res.x
array([ 1.,  1.,  1.,  1.,  1.])
>>> print(res.message)
Optimization terminated successfully.
>>> res.hess_inv
array([
    [ 0.00749589,  0.01255155,  0.02396251,  0.04750988,  0.09495377],  # may vary
    [ 0.01255155,  0.02510441,  0.04794055,  0.09502834,  0.18996269],
    [ 0.02396251,  0.04794055,  0.09631614,  0.19092151,  0.38165151],
    [ 0.04750988,  0.09502834,  0.19092151,  0.38341252,  0.7664427 ],
    [ 0.09495377,  0.18996269,  0.38165151,  0.7664427,   1.53713523]
])

接下来,考虑一个具有多个约束的最小化问题(即来自 [5] 的示例 16.4)。目标函数是

>>> fun = lambda x: (x[0] - 1)**2 + (x[1] - 2.5)**2

有三个约束定义为

>>> cons = ({'type': 'ineq', 'fun': lambda x:  x[0] - 2 * x[1] + 2},
...         {'type': 'ineq', 'fun': lambda x: -x[0] - 2 * x[1] + 6},
...         {'type': 'ineq', 'fun': lambda x: -x[0] + 2 * x[1] + 2})

并且变量必须是正数,因此有以下边界

>>> bnds = ((0, None), (0, None))

优化问题使用 SLSQP 方法解决,如下所示

>>> res = minimize(fun, (2, 0), method='SLSQP', bounds=bnds, constraints=cons)

它应该收敛到理论解 [1.4 ,1.7]。*SLSQP* 还返回用于问题解决方案的乘子。当问题约束是线性的时,这些乘子可以被视为 Karush-Kuhn-Tucker (KKT) 乘子,它们是 Lagrange 乘子在不等式约束优化问题中的推广 ([20])。

请注意,在解处,第一个约束是活跃的。让我们在解处评估函数

>>> cons[0]['fun'](res.x)
np.float64(1.4901224698604665e-09)

此外,请注意,在最优性处存在一个非零乘子

>>> res.multipliers
array([0.8, 0. , 0. ])

这可以理解为目标函数最优值对第一个约束变化的局部敏感度。如果我们把约束收紧少量 eps

>>> eps = 0.01
>>> cons[0]['fun'] = lambda x: x[0] - 2 * x[1] + 2 - eps

我们期望目标函数的最优值大约增加 eps * res.multipliers[0]

>>> eps * res.multipliers[0]  # Expected change in f0
np.float64(0.008000000027153205)
>>> f0 = res.fun  # Keep track of the previous optimal value
>>> res = minimize(fun, (2, 0), method='SLSQP', bounds=bnds, constraints=cons)
>>> f1 = res.fun  # New optimal value
>>> f1 - f0
np.float64(0.008019998807885509)