这是这个问题的后续问题。

考虑以下标准形式的 SDP：

$$\begin{align} &\min_{X\in S^n, X>0} \operatorname{tr}(AX)\\ &\mbox{subject to}\; \operatorname{tr}(B_iX)\leq b_i, i=1,\dots,m\\ \end{align}$$

这里，$A\in S^n,B_i \in S^n$，$b_i\in \mathbb{R}$和$m=O(n)$。

在一般情况下，谁能解释这个问题的预期存储复杂性？

我的理解是，像 SCS 这样的一阶求解器将仅使用梯度信息形成一个$n^2$大小的线性系统，因此存储复杂度将为$O(n^4)$，它反映了梯度矩阵的大小，即$n^2\times n^2$。

这种理解正确吗？我的困惑是关于双重问题的可能性较小。CVX会自动处理吗？例如，如果$n=1000$和$m=1000$，似乎上面提到的原始形式会形成较小的问题。

---

约翰回答后编辑：我目前正在使用 CVX。我尝试了一个类似于您给出的示例。在上面的帖子中使用符号，我使用的是。。如果我以上述格式提交我的问题，我会得到以下输出：$n=100,m=10$$X\in S^n$

---

调用 SCS 1.1.7：5050 个变量，10 个等式约束

Lin-sys: sparse-indirect, nnz in A = 50500, CG tol ~ 1/iter^(2.00) eps = 1.35e-06, alpha = 1.50, max_iters = 10000, normalize = 1, scale = 1.00 变量 n = 10 ，约束 m = 5050 锥体：sd vars：5050，sd blks：1 建立时间：3.02e-03s

---

现在，如果我通过形成这个对偶来提交我的问题，我会收到消息说 CVX 将解决我对偶的对偶（即原始问题），并且我得到与上面完全相同数量的约束和变量。

所以我的问题是 CVX 是否真的解决了你所描述的方式？ 考虑到上述变量，预期的空间复杂度是多少？