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

问题描述

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

Consider the following (convex) optimization problem:

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

其中优化(向量)变量分别是x，y和A，b分别是适当尺寸的矩阵和向量.

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

下面的代码使用Scipy的SLSQP方法轻松找到解决方案:

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.

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

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).

这是等效约束集，后跟minimize的输出(与上面的清单相同的A，b和初始值):

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

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

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.

推荐答案

您已经遇到了 gotcha .所有对cons_i的调用都是在第二个参数等于19的情况下进行的.

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.

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

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

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

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屋！