第 45B 章 共正矩阵与共正规划¶
前置：正定矩阵 (Ch16) · 完全正矩阵 (Ch45A) · 凸优化 (Ch25)
本章脉络：从全局正性到局部正性 \(\to\) 共正矩阵 (Copositive Matrices) 的定义 \(\to\) 共正锥 \(\mathcal{C}_n\) 与完全正锥 \(\mathcal{CP}_n\) 的对偶关系 \(\to\) 判定共正性的计算难度 \(\to\) 共正规划 (Copositive Programming) 的数学形式 \(\to\) 核心定理：对组合优化问题的精确松弛（如稳定数、Hamilton 回路） \(\to\) 应用：计算生物学中的构象搜索、运筹学中的非凸二次规划
延伸：共正矩阵是完全正矩阵的“对偶灵魂”；它将正定性的判据限制在非负象限内，从而捕捉了离散组合问题的连续极值特征，是解决传统 NP-难问题的最前沿连续化工具
如果说完全正矩阵要求的是一种“内部的非负构造”，那么共正矩阵（Copositive Matrices）要求的则是一种“外部的非负作用”。它只要求二次型在非负向量上为正，而不必在整个空间为正。这种看似放宽的条件，却因为“象限限制”引入了极高的非凸性和组合复杂性。本章将介绍这一作为完全正矩阵对偶存在的关键结构，及其在破解组合优化难题中的核心作用。
45B.1 定义与对偶性¶
定义 45B.1 (共正矩阵)
对称矩阵 \(A \in S_n\) 称为 共正矩阵（Copositive），如果对于所有非负向量 \(\mathbf{x} \ge 0\)，均有： $\(\mathbf{x}^T A \mathbf{x} \ge 0\)$ 所有 \(n \阶\) 共正矩阵构成的集合记为 \(\mathcal{C}_n\)。
定理 45B.1 (对偶关系)
共正锥 \(\mathcal{C}_n\) 与完全正锥 \(\mathcal{CP}_n\) 是互为对偶锥： $\(\mathcal{C}_n = (\mathcal{CP}_n)^*\)$ 这意味着判定一个矩阵是否完全正，等价于判定一个线性泛函在共正锥上是否非负。
45B.2 判定难度与结构¶
判定的挑战
与正定矩阵不同，目前不存在类似于顺序主子式的简单多项式时间算法来判定共正性。该问题已被证明是 co-NP 完备 的。
典型共正矩阵
- 非负矩阵：若 \(A \ge 0\)，显然是共正的。
- 正定矩阵：若 \(A \succeq 0\)，显然是共正的。
- 和矩阵：\(A = P + N\)，其中 \(P \succeq 0, N \ge 0\)。这类矩阵称为“标准共正矩阵”。
45B.3 共正规划 (Copositive Programming)¶
定义 45B.2 (共正程序)
共正规划是指在一组线性约束下，优化一个在线性空间内且属于共正锥（或其对偶锥）的矩阵变量。 价值：它可以将许多 NP-难的离散优化问题（如独立集、图着色）表示为凸优化问题（尽管是在一个难处理的锥上）。
练习题¶
1. [基础] 判定 \(\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}\) 是否为共正矩阵。
参考答案
验证步骤： 1. 计算二次型：\(f(x, y) = x^2 - 2xy + y^2 = (x-y)^2\)。 2. 对于任何实数 \((x, y)\)， \((x-y)^2 \ge 0\)。 3. 特别地，对于非负的 \(x, y\)，结论显然成立。 结论：该矩阵不仅是共正的，还是正定的。
2. [对比] 判定 \(A = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}\) 是否为共正矩阵。
参考答案
计算： 1. \(f(x, y) = x^2 + 4xy + y^2\)。 2. 由于 \(x, y \ge 0\)，三项均为非负。 3. 对于非零非负向量， \(f(x, y) > 0\)。 结论：是共正矩阵。 注意：它的行列式为 \(-3 < 0\)，故它不是正定的。这体现了共正矩阵比正定矩阵更宽泛。
3. [反例] 举出一个不是共正矩阵的对称阵。
参考答案
例子： \(A = \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}\)。 证明：取 \(\mathbf{x} = (1, 0)^T \ge 0\)。计算 \(\mathbf{x}^T A \mathbf{x} = -1 < 0\)。 违反了非负向量作用的定义。
4. [性质] 证明：若 \(A\) 是共正的，其对角元必须非负。
参考答案
证明： 1. 取标准基向量 \(\mathbf{e}_i \ge 0\)。 2. \(\mathbf{e}_i^T A \mathbf{e}_i = a_{ii}\)。 3. 由共正性定义，该值必须 \(\ge 0\)。
5. [组合] 两个共正矩阵之和还是共正矩阵吗？
参考答案
是的。 理由：\(x^T (A+B) x = x^T Ax + x^T Bx\)。若每一项在非负象限内都非负，其和也必非负。这证明了共正矩阵集合构成一个凸锥。
6. [对偶] 为什么完全正矩阵（CP）的对偶是共正矩阵（Copositive）？
参考答案
代数解释： 1. CP 矩阵是 \(BB^T\) 的和，每一项是 \(\mathbf{b}\mathbf{b}^T\)（其中 \(\mathbf{b} \ge 0\)）。 2. 根据对偶锥定义，\(A\) 在对偶锥内当且仅当 \(\langle A, X \rangle \ge 0\) 对所有 \(X \in \mathcal{CP}\)。 3. \(\langle A, \mathbf{b}\mathbf{b}^T \rangle = \operatorname{tr}(A \mathbf{b}\mathbf{b}^T) = \mathbf{b}^T A \mathbf{b}\)。 4. 这要求 \(\mathbf{b}^T A \mathbf{b} \ge 0\) 对所有 \(\mathbf{b} \ge 0\) 成立，这正是共正性的定义。
7. [应用] 什么是图 \(G\) 的“共正表示”？
参考答案
任何一个图 \(G\) 的最大独立集（或稳定数）\(\alpha(G)\) 可以通过共正矩阵的线性规划精确表达。这证明了共正理论在捕捉图的局部不连通性方面的强大威力。
8. [计算] 如何判定一个 \(2 \times 2\) 对称阵是否共正？
参考答案
判据： 对于 \(\begin{pmatrix} a & b \\ b & c \end{pmatrix}\)，它是共正的当且仅当： \(a \ge 0, c \ge 0\) 且 (\(b \ge 0\) 或 \(b \ge -\sqrt{ac}\))。 这意味着只要对角元为正且非对角元不要负得“太离谱”，它就是共正的。
9. [稳定性] 在种群动力学中，共正矩阵有何应用？
参考答案
在研究物种竞争模型（Lotka-Volterra 方程）时，平衡点的全局稳定性通常依赖于交互矩阵在正象限内的表现。若交互矩阵是共正的，则可以保证物种数量（始终非负）不会无限制增长或崩溃。
10. [极限] 为什么共正规划被称为“虽然凸但依然难（Hard Convex）”的问题？
参考答案
深层矛盾： 1. 共正规划的约束集是凸的，目标函数也是线性的，因此理论上是凸优化。 2. 但这个凸集的“边界”极其复杂（是 co-NP 完备的），无法用简单的多项式不等式刻画。 3. 这说明凸性并不总是意味着计算简便，某些代数结构的内在组合性质会隐藏在凸性的外壳之下。
本章小结¶
共正矩阵是正性理论在约束空间下的深度延拓：
- 象限的智慧：它证明了通过将关注点从全空间缩小到非负象限，我们可以捕捉到正定矩阵无法描述的局部稳定性与组合特征。
- 对偶的和谐：共正锥与完全正锥的对偶关系构成了凸分析中最高度对称的架构之一，为从不同角度攻击同一个数学难题提供了可能。
- 优化的新范式：共正规划的出现模糊了连续优化与离散组合的界限，尽管其判定具有挑战性，但它为解决 NP-难问题提供了一个统一且精确的代数解析路径。