Scipy.optimize.minimize SLSQP 与线性约束失败 [英] Scipy.optimize.minimize SLSQP with linear constraints fails

问题描述

考虑以下(凸)优化问题:

最小化 0.5 * y.T * y英石.A*x - b == y

其中优化(向量)变量是 x 和 y 和 A，b 是一个矩阵和分别具有适当维度的向量.

下面的代码使用 Scipy 的 SLSQP 方法很容易找到解决方案:

将 numpy 导入为 np从 scipy.optimize 导入最小化# 问题维度:n = 10 # 用户设置的任意整数m = 2 * n# 生成参数 A, b:np.random.seed(123) # 结果的可重复性A = np.random.randn(m,n)b = np.random.randn(m)# 目标函数:定义对象(z):vy = z[n:]返回 0.5 * vy.dot(vy)# 约束函数:缺点(z):vx = z[:n]vy = z[n:]返回 A.dot(vx) - b - vy# SLSQP 的约束输入:cons = ({'type': 'eq','fun': cons})# 生成一个随机的初始估计:z0 = np.random.randn(n+m)溶胶 = 最小化(对象，x0 = z0，约束 = 缺点，方法 = 'SLSQP'，选项 ={'disp': True})

<块引用>

优化成功终止.(退出模式0)当前函数值:2.12236220865迭代次数:6功能评估:192梯度评估:6

请注意，约束函数是一个方便的数组输出"函数.

现在，代替约束的数组输出函数，原则上可以使用一组等效的标量输出"约束函数(实际上，scipy.optimize 文档仅讨论了这种类型的约束函数作为输入最小化).

这里是等价的约束集，后面是 minimize 的输出(与上面的列表相同的 A、b 和初始值):

# 这是 cons(z) 的第 i 个元素:def cons_i(z, i):vx = z[:n]vy = z[n:]返回 A[i].dot(vx) - b[i] - vy[i]# 可列出 SLSQP 的标量输出约束输入:cons_per_i = [{'type':'eq', 'fun': lambda z: cons_i(z, i)} for i in np.arange(m)]sol2 = 最小化(对象，x0 = z0，约束 = cons_per_i，方法 = 'SLSQP'，选项 ={'disp':True})

<块引用>

LSQ子问题中的奇异矩阵C(退出模式6)当前函数值:6.87999270692迭代次数:1功能评估:32梯度评估:1

显然，算法失败了(返回的目标值实际上是给定初始化的目标值)，我觉得这有点奇怪.请注意，运行 [cons_per_i[i]['f​​un'](sol.x) for i in np.arange(m)] 显示 sol.x，使用获得数组输出约束公式，按预期满足 cons_per_i 的所有标量输出约束(在数值容差范围内).

如果有人对此问题有一些解释，我将不胜感激.

解决方案

您遇到了 "后期绑定闭包"gotcha.所有对 cons_i 的调用都是在第二个参数等于 19 的情况下进行的.

解决方法是在定义约束的字典中使用 args 字典元素而不是 lambda 函数闭包:

cons_per_i = [{'type':'eq', 'fun': cons_i, 'args': (i,)} for i in np.arange(m)]

这样，最小化就起作用了:

In [417]: sol2 = minimum(obj, x0 = z0, constraint = cons_per_i, method = 'SLSQP', options={'disp': True})优化已成功终止.(退出模式0)当前函数值:2.1223622086迭代次数:6功能评估:192梯度评估:6

您还可以使用链接文章中提出的建议，即使用具有所需默认值的第二个参数的 lambda 表达式:

cons_per_i = [{'type':'eq', 'fun': lambda z, i=i: cons_i(z, i)} for i in np.arange(m)]

Consider the following (convex) optimization problem:

minimize 0.5 * y.T * y
s.t.     A*x - b == y

where the optimization (vector) variables are x and y and A, b are a matrix and vector, respectively, of appropriate dimensions.

The code below finds a solution easily using the SLSQP method from Scipy:

import numpy as np
from scipy.optimize import minimize 

# problem dimensions:
n = 10 # arbitrary integer set by user
m = 2 * n

# generate parameters A, b:
np.random.seed(123) # for reproducibility of results
A = np.random.randn(m,n)
b = np.random.randn(m)

# objective function:
def obj(z):
    vy = z[n:]
    return 0.5 * vy.dot(vy)

# constraint function:
def cons(z):
    vx = z[:n]
    vy = z[n:]
    return A.dot(vx) - b - vy

# constraints input for SLSQP:
cons = ({'type': 'eq','fun': cons})

# generate a random initial estimate:
z0 = np.random.randn(n+m)

sol = minimize(obj, x0 = z0, constraints = cons, method = 'SLSQP',  options={'disp': True})

Optimization terminated successfully.    (Exit mode 0)
            Current function value: 2.12236220865
            Iterations: 6
            Function evaluations: 192
            Gradient evaluations: 6

Note that the constraint function is a convenient 'array-output' function.

Now, instead of an array-output function for the constraint, one could in principle use an equivalent set of 'scalar-output' constraint functions (actually, the scipy.optimize documentation discusses only this type of constraint functions as input to minimize).

Here is the equivalent constraint set followed by the output of minimize (same A, b, and initial value as the above listing):

# this is the i-th element of cons(z):
def cons_i(z, i):
    vx = z[:n]
    vy = z[n:]
    return A[i].dot(vx) - b[i] - vy[i]

# listable of scalar-output constraints input for SLSQP:
cons_per_i = [{'type':'eq', 'fun': lambda z: cons_i(z, i)} for i in np.arange(m)]

sol2 = minimize(obj, x0 = z0, constraints = cons_per_i, method = 'SLSQP', options={'disp': True})

Singular matrix C in LSQ subproblem    (Exit mode 6)
            Current function value: 6.87999270692
            Iterations: 1
            Function evaluations: 32
            Gradient evaluations: 1

Evidently, the algorithm fails (the returning objective value is actually the objective value for the given initialization), which I find a bit weird. Note that running [cons_per_i[i]['fun'](sol.x) for i in np.arange(m)] shows that sol.x, obtained using the array-output constraint formulation, satisfies all scalar-output constraints of cons_per_i as expected (within numerical tolerance).

I would appreciate if anyone has some explanation for this issue.

解决方案

You've run into the "late binding closures" gotcha. All the calls to cons_i are being made with the second argument equal to 19.

A fix is to use the args dictionary element in the dictionary that defines the constraints instead of the lambda function closures:

cons_per_i = [{'type':'eq', 'fun': cons_i, 'args': (i,)} for i in np.arange(m)]

With this, the minimization works:

In [417]: sol2 = minimize(obj, x0 = z0, constraints = cons_per_i, method = 'SLSQP', options={'disp': True})
Optimization terminated successfully.    (Exit mode 0)
            Current function value: 2.1223622086
            Iterations: 6
            Function evaluations: 192
            Gradient evaluations: 6

You could also use the the suggestion made in the linked article, which is to use a lambda expression with a second argument that has the desired default value:

cons_per_i = [{'type':'eq', 'fun': lambda z, i=i: cons_i(z, i)} for i in np.arange(m)]

这篇关于Scipy.optimize.minimize SLSQP 与线性约束失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！