如何构建 SOCP 问题并使用 cvxpy 和 cvxpylayers 求解

Question

我正在尝试使用 cvxpy 解决 SOCP 问题并将其集成到 cvxpylayers。我在看 this SOCP problem (problem 11) (here 是 scihub link 以防你无法访问），这里是问题的一个片段（注意 min (p-t) 来自 问题 4 在上面的 link 中使用 表达式 8:

转到 ---> 编辑 2

旧

我看过 this 示例，但仍然卡住了，无法解决问题。这是我尝试的示例代码：

import cvxpy as cp
import numpy as np

N = 5

Q_sqrt = cp.Parameter((N, N))
x = cp.Variable(N)

z = []
zero = []
for n in range(N):
    z.append((Q_sqrt @ x)[n])
    zero.append(cp.Constant(0))
    
p = cp.sqrt(cp.sum_squares(Q_sqrt @ x)/N) # based on expression 8
t = cp.sqrt(cp.min(x * (Q_sqrt @ x)))     # based on expression 8

objective = cp.Minimize(p - t)            # based on expression 8

constraint_soc1 = [cp.SOC(z[n], (Q_sqrt @ x)[n]) for n in range(N)]
constraint_soc2 = [cp.SOC(cp.quad_over_lin(t, z[n]), x[n]) for n in range(N)]
constraint_soc3 = [cp.SOC(z[n], zero[n]) for n in range(N)]
constraint_soc4 = [cp.SOC(x[n], zero[n]) for n in range(N)]

constraint_other = [cp.sum_squares(Q_sqrt @ x) <= N * (p ** 2),
                    cp.sum(x) == 1, p >= 0, t >= 0]

constraint_all = constraint_other + constraint_soc1 + constraint_soc2 + constraint_soc3 + constraint_soc4

matrix = np.random.random((N, N))
Q_sqrt.value = matrix.T @ matrix # to make positive definite

prob = cp.Problem(objective, constraint_all)

prob.solve()
print("status:", prob.status)
print("optimal value", prob.value)

请注意，我使用 cp.sum_squares(Q_sqrt @ x) 语法来确保它不仅符合 DCP，而且符合 DPP（参考 Section 4.1）。

首先，我注意到 objective 的 p = cp.sqrt(cp.sum_squares(Q_sqrt @ x)/N) 部分（表达式 8 的第一项）不是 DCP，并且不确定如何修复它。

此外，我被告知需要使用 cp.quad_over_lin 重新制定此 x.T @ Q @ x <= N * p**2 约束条件，但是，如前所述，我要求它遵循 DPP 规则（对于 cvxpylayers），因为好吧，因此我不确定如何更改 cp.sum_squares(Q_sqrt @ x) <= N * (p ** 2) 以遵循 cp.quad_over_lin.

最后，我确信我的代码的其他部分也有错误的实现。非常感谢任何对此问题的帮助！

编辑 1：请注意，最终解决方案不必调用 cvxpylayers，而只需符合 DPP，以便它可以与 [=13] 集成=]之后。

__________________________________________________________________________

新

编辑 2：我现在意识到这可能是一个多变量问题，以最小化 p - t 给定变量 x,z,p,t。我不知道为什么我没有早点想到这一点。

鉴于上面的代码片段问题，我最近的尝试如下：

import cvxpy as cp
import numpy as np

N = 5

Q_sqrt = cp.Parameter((N, N))
Q = cp.Parameter((N, N))

x = cp.Variable(N)
z = cp.Variable(N)
p = cp.Variable()
t = cp.Variable()

objective = cp.Minimize(p - t)

constraint_soc = [z == Q @ x, x.value * z >= t ** 2, z >= 0, x >= 0]

constraint_other = [cp.quad_over_lin(Q_sqrt @ x, N) <= p ** 2, cp.sum(x) == 1, p >= 0, t >= 0]

constraint_all = constraint_other + constraint_soc

matrix = np.random.random((N, N))
a_matrix = matrix.T @ matrix
Q.value = a_matrix
Q_sqrt.value = np.sqrt(a_matrix)

prob = cp.Problem(objective, constraint_all)

prob.solve(verbose=True)
print("status:", prob.status)
print("optimal value", prob.value)

但是，我仍然收到错误消息：

DCPError: Problem does not follow DCP rules. Specifically: The following constraints are not DCP: quad_over_lin(param7788 @ var7790, 5.0) <= power(var7792, 2.0) , because the following subexpressions are not: |-- quad_over_lin(param7788 @ var7790, 5.0) <= power(var7792, 2.0)

对于此 x.T @ Q @ x <= N * p**2 约束（我的尝试：cp.quad_over_lin(Q_sqrt @ x, N) <= p ** 2）。

除此之外问题也是SOCP，所以我在constraint_soc中的约束可能是错误的，但我不知道如何loop/assign 基于 this.

的变量

编辑 3：在 ErlingMOSEK 对约束的建议之后，我将约束从 cp.quad_over_lin(Q_sqrt @ x, N) <= p ** 2 更改为cp.quad_over_lin(Q_sqrt @ x, p) <= N * p 现在可以运行了，但是，

出现新错误

Solver 'ECOS' failed. Try another solver, or solve with verbose=True for more information.

我认为是由于问题 SOCP（我的第二个问题），我不确定如何仅基于 this 示例构建 SOCP。

EDIT 4：使用 EDIT 2/3 和 Erling 的答案以及 Erling 建议的不同求解器，问题就解决了。请注意，我改用 XPRESS 求解器。

Answer 1

你应该改变

x.T @Q @x <= N * p**2

至

(x.T @Q @x)/p <= N * p

假设 p>=0。

顺便说一句，如果您想了解更多有关如何将其制定为 SOCP 的信息，请参阅 the Mosek modelling cookbok。

如何构建 SOCP 问题并使用 cvxpy 和 cvxpylayers 求解

How to construct a SOCP problem and solve using cvxpy and cvxpylayers

portfolio

convex-optimization

cvxopt

cvxpy