标签: quadratic-programming

我想计算一个二次形式：x' Q y在 Julia 中。
对于这种情况，计算此值的最有效方法是什么：

1. 没有假设。
2. Q是对称的。
3. x和y相同（x = y）。
4. 两者Q都是对称的并且x = y.

我知道朱莉娅有dot()。但我想知道它是否比 BLAS 调用更快。

我有一个151 × 151的矩阵A.它是一个相关矩阵,因此1主对角线上有s,主对角线上方和下方有重复值.每行/每列代表一个人.

对于给定的整数,n我将寻求通过踢出人来减小矩阵的大小,这样我留下了一个n-by-n最小化元素总和的相关矩阵.除了获得缩写矩阵之外,我还需要知道应该从原始矩阵中引导的人的行号(或者他们的列号 - 它们将是相同的数字).

作为我的起点A = tril(A),它将从相关矩阵中去除冗余的非对角线元素.

因此,如果n = 4我们上面有假想的5- by- 5矩阵,那么很明显人5应该被踢出矩阵,因为那个人正在贡献很多非常高的相关性.

同样清楚的是,人1不应该被踢出,因为那个人贡献了很多负相关,从而降低了矩阵元素的总和.

我明白这sum(A(:))将总结矩阵中的所有内容.但是,我很清楚如何搜索最小可能的答案.

我注意到一个类似的问题.找到具有最小元素和的子矩阵,它有一个强力解决方案作为接受的答案.虽然这个答案很好,但对于一个151 × 151的矩阵来说这是不切实际的.

编辑:我曾想过迭代,但我认为这不会真正最小化简化矩阵中的元素总和.下面我有一个粗体的4- by- 4相关矩阵,边缘上有行和列的总和.很明显,n = 2最优矩阵是涉及人1和4 的2乘2的单位矩阵,但根据迭代方案,我会在迭代的第一阶段踢出人1,因此算法得出一个解决方案不是最佳的.我写了一个总是产生最佳解决方案的程序,当n或k很小时它运行良好,但是当试图从151 × 151矩阵制作一个最佳的75- x- 75矩阵时,我意识到我的程序需要数十亿年终止.

我含糊地回忆说,有时这些n选择k问题可以通过动态编程方法解决,避免重新计算的东西,但我无法弄清楚如何解决这个问题,也没有谷歌搜索启发我.

如果没有其他选择,我愿意牺牲精度以获得速度,或者最好的程序需要一周以上才能生成精确的解决方案.但是,如果能够生成一个精确的解决方案,我很高兴让程序运行长达一周.

如果程序无法在合理的时间范围内优化矩阵,那么我会接受一个解释为什么n选择此特定类型的k任务无法在合理的时间范围内解决的答案.

我有一个优化问题,在目标函数2中有多个变量,使模型呈二次方.

我目前正在使用zimpl来解析模型,并使用glpk来解决它.由于它们不支持二次规划,我需要将其转换为MILP.

.第一个变量是实数,在[0,1]范围内,第二个变量是实数,范围从0到inf.这个可以没有问题是整数.

目标函数中的关键部分如下所示:

max ... + var1 * var2 + ...

我在约束中遇到了类似的问题,但它们很容易解决.

我怎样才能在目标函数中解决这类问题？

I have a reasonably simple constrained optimization problem but get different answers depending on how I do it. Let's get the import and a pretty print function out of the way first:

import numpy as np
from scipy.optimize import minimize, LinearConstraint, NonlinearConstraint, SR1

def print_res( res, label ):
    print("\n\n ***** ", label, " ***** \n")
    print(res.message)
    print("obj func value at solution", obj_func(res.x))
    print("starting values: ", x0)
    print("ending values:   ", res.x.astype(int) )
    print("% diff", (100.*(res.x-x0)/x0).astype(int) )
    print("target achieved?",target,res.x.sum())

The sample data …

我正在尝试使用CVXOPT qp求解器来计算支持向量机的拉格朗日乘子

def svm(X, Y, c):
      m = len(X)
      P = matrix(np.dot(Y, Y.T) * np.dot(X, X.T))
      q = matrix(np.ones(m) * -1)
      g1 = np.asarray(np.diag(np.ones(m) * -1))
      g2 = np.asarray(np.diag(np.ones(m)))
      G = matrix(np.append(g1, g2, axis=0))
      h = matrix(np.append(np.zeros(m), (np.ones(m) * c), axis =0))
      A = np.reshape((Y.T), (1,m))
      b = matrix([0])

      print (A).shape

      A = matrix(A)

      sol = solvers.qp(P, q, G, h, A, b)
      print sol

这X是一个1000 X 2矩阵Y,标签数量相同.解算器抛出以下错误: $ python svm.py (1, 1000) Traceback (most …

我正在尝试执行线性回归,对于这样的模型:

Y = aX1 + bX2 + c

所以, Y ~ X1 + X2

假设我有以下响应向量:

set.seed(1)
Y <- runif(100, -1.0, 1.0)

以下预测变量矩阵:

X1 <- runif(100, 0.4, 1.0)
X2 <- sample(rep(0:1,each=50))
X <- cbind(X1, X2)

我想对系数使用以下约束:

a + c >= 0  
c >= 0

所以对b没有约束.

我知道glmc包可以用来应用约束,但是我无法确定如何将它应用于我的约束.我也知道可以使用contr.sum,例如,所有系数总和为0,但这不是我想要做的.solve.QP()似乎是另一种可能性,meq=0可以使用设置使所有系数> = 0(同样,这里不是我的目标).

注意:解决方案必须能够处理响应向量Y中的NA值,例如:

Y <- runif(100, -1.0, 1.0)
Y[c(2,5,17,56,37,56,34,78)] <- NA

我正在使用 CVXPY（版本 1.0）来解决二次程序（QP），我经常遇到这个异常：

求解器错误：求解器“xxx”失败。尝试另一个求解器。

这使我的程序非常脆弱。我尝试了不同的求解器，包括 CVXOPT、OSQP、ECOS、ECOS_BB、SCS。他们都或多或少有相同的问题。我注意到，当我使求解器的停止标准更严格（例如，降低绝对误差容限）时，我会变SolverError得更频繁，而当我使其不那么严格时，SolverError问题会减弱甚至消失。我还发现 CVXPY 抛出的方式SolverError是随机的：如果我多次运行同一个程序，有一些运行SolverError会获得最佳结果而另则会获得最佳结果。

虽然我可以通过尝试更多次并降低停止标准来避免 SolverError，但我真的很想了解异常背后的真正具体原因

求解器错误：求解器“xxx”失败。尝试另一个求解器。

这个错误并没有真正提供信息，我不知道如何提高解决问题的稳健性。其原因是否特定于求解器？是否为一组明确定义的情况抛出此异常？或者它只是一种说“由于未知原因出现问题”的方式？这些可能是什么原因？

通常我一直在使用GNU Octave来解决二次规划问题。

我解决的问题是

x = 1/2x'Qx + c'x

受制于

A*x <= b
lb <= x <= ub

哪里lb和ub是下限和上限，例如限制x

当我解决时，我的 Octave 代码看起来像这样。只需简单的一行

U = quadprog(Q, c, A, b, [], [], lb, ub);

方括号[]是空的，因为我不需要等式约束

Aeq*x = beq,

所以我的问题是：在 Python 中是否有一个易于使用的二次求解器来解决问题

x = 1/2x'Qx + c'x

受制于

A*x <= b
lb <= x <= ub

或受制于

b_lb <= A*x <= b_ub
lb <= x <= ub

我想找到argmax(x,y,z)-1/2(20x ^ 2 + 32xy + 16y ^ 2)+ 2x + 2y.

受制于:x> = 0,y> = 0,z> = 0且-x-y + z = 0.

我知道偏导数设置为0是:

-20x-16y + 2 = 0和-16x-16y + 2 = 0

所以我们可以得x = 0和y = 1/8,z = 1/8.

我如何在Swi-prolog中做到这一点？我看到有用于线性求解的库单形,但这是一个二次问题,但偏导数不是.(我有一点困惑!)

这就是我所拥有的:

:- use_module(library(simplex)).

my_constraints(S):-
 gen_state(S0),
 constraint([-20*x, -16*y] = 0, S0, S1),
 constraint([-16*x,-16*y] = 0, S1,S2),
 constraint([x] >= 0,S2,S3),
 constraint([y] >= 0,S3,S4),
 constraint([z] >= 0,S4,S5),
 constraint([-x-y+z] = 0,S5,S).

?- my_constraints(S), variable_value(S,x,Val1),variable_value(S,y,Val2).
false.

我正在将一些 MATLAB 代码翻译成 Python。有一行给我带来了一些麻烦：

[q,f_dummy,exitflag, output] = quadprog(H,f,-A,zeros(p*N,1),E,qm,[],[],q0,options);

我在 MATLAB 中查找文档，发现 quadprog 函数用于优化（特别是最小化）。

我试图在 Python 中找到一个类似的函数（使用 numpy），但似乎没有。

有没有更好的方法将这行代码翻译成 Python？或者有其他可以使用的包吗？我是否需要创建一个新函数来完成相同的任务？

感谢您的时间和帮助！