从 dual score 到 saddle certificates 的一点新进展
三月的时候，我写了一篇讲我在 network localization 这个问题里尝试做 duality，结果两条很自然的 Lagrangian dual 路线都 collapse 到了 0。
当时我的感觉大概是：好吧，dual 没有给我一个漂亮的 lower bound。
但它也没有完全死掉。
真正留下来的，是 conjugate-based DC dual 里出现的一个 projector formula。这个 formula 一开始看起来像一个副产品：它不太像能直接替代 primal objective 也不像一个能马上塞进 algorithm 里的 magic quantity。但它有一个很清楚的几何意义：它在测量 prescribed edge-length budget 和 realizable edge-difference subspace 之间的 incompatibility。
也就是说它不太像传统意义上的 dual solution，反而更像一个 structural score。
当时我对它的理解还很 static：它只依赖 instance，也就是 measurement graph 和 prescribed distances，不依赖某一个 iterate x。所以我把它理解成一个 instance-level difficulty score，一个用来描述这个 localization instance 本身有多不 compatible 的量。
最近这条线又往前走了一点。现在我更愿意这样理解它：
这个 dual score 一开始是 static 的，但它后来开始接触 stationary point geometry 了。
这件事对我来说还挺重要的，因为它说明真的可能变成理解 landscape 的一部分。
1. 上次留下来的东西：一个 instance-level structural score
我研究的 objective 是 network localization / MDS 里很经典的 nonconvex nonsmooth least squares：给定一堆边，每条边都有一个 prescribed distance delta，我们想找 node positions，使得每条边的实际距离尽量接近 delta。
这个问题难在几个地方：它 nonconvex；它 nonsmooth，因为 norm 在 0 处不可微；它有 translation invariance；而且 graph cycles 会带来 global compatibility constraints。
我一开始试图从 duality 入手。最朴素的想法是：如果能找到一个有意义的 dual lower bound，也许就可以解释 instance difficulty 甚至辅助 algorithm。
但实际推下来之后两条很自然的 plain Lagrangian dual routes 都塌掉了。它们基本只能告诉我：
F(x) >= 0。
谢谢你，真的很有用。
不过 conjugate-based DC dual 没有完全塌，它留下了一个 projector formula，大概形如：
S_dual(B, delta) = sum(delta_l^2) - 1/4 * sup over u in V of ||P u||^2.
这里 V 是 blockwise budget set，每条边的 block norm 最多是 2 delta_l，P 是投影到 Range(B) 的 orthogonal projector，Range(B) 就是所有能够由 node positions 产生的 edge-difference vectors。
这个 score 的意义是：在所有允许的 edge-budget vectors 里，最多有多少 budget 可以真正落到 realizable edge-difference subspace 里？
如果全部 budget 都可以放进去，那么 score 是 0。这对应 prescribed distances 可以被某个 configuration exactly realized。如果不能全部放进去，那么 score 就是 positive。这说明有一部分 prescribed edge-length information 和 graph 的 global compatibility constraints 冲突。
所以它不是单纯在看图有没有 cycle，而是在看：这个 graph 加上这组 distances，能不能形成一个 globally compatible 的 edge geometry。
这比“cyclic means hard, forest means easy”细一点。Forest 的确对这个 score 来说是 degenerate 的，因为没有 cycle consistency constraints，score 会变成 0。但 cyclic graph 也不一定 score positive。真正起作用的是 graph structure、delta，以及 ambient dimension 的组合。
它不是一个 topology-only quantity，而是一个 geometry-aware structural quantity。
2. Static score 之后：stationary dual witness
一开始这个 score 只看 instance，不看某一个 point x。
这当然有好处：它像一个全局诊断工具，可以在 algorithm 开始之前告诉你这个 instance 可能有多 incompatible。但也有明显限制：optimization algorithm 真正走的是 iterates，最后遇到的是 critical points / stationary points。一个完全 static 的 score 很难直接告诉我某个 stationary point 是好是坏。
所以我后来问了一个问题：能不能把这个 static dual score 和 differentiable stationary points 连起来？
结果还真的可以。
对于一个 differentiable point x，每条边 B_l x 都不等于 0。于是我可以定义一个 saturated edge-budget vector：u_l(x) 指向 B_l x 的方向，长度为 2 delta_l。
也就是说，u(x) 把每条边的 prescribed distance 变成一个方向化的 dual-side witness。每个 block 都刚好 saturate budget，所以它自然落在 V 的边界上。
我把它叫做 stationary dual witness。
最漂亮的地方是：如果 x 是 differentiable stationary point，那么有一个很干净的 projector identity：
P u(x) = 2 Bx.
直觉上说，这个 identity 把两件事连起来了：u(x) 是 prescribed distances 给出来的 saturated budget direction；Bx 是当前 configuration 真正产生的 edge differences；P 是把任何 edge-space vector 投影回 realizable subspace Range(B)。
所以 stationary condition 可以被理解成：把 saturated witness 投影回 realizable edge-space 之后，刚好得到当前 edge differences 的两倍。
这一下 dual side 就不是纯 static 了。它开始能够读到 stationary point 的 geometry。
3. Pointwise identity：stationary value 也能被 dual witness 读出来
更进一步在 differentiable stationary point 上我可以把 objective value 写成一个 primal-dual identity。
大概意思是：
F(x) = sum(delta_l^2) - 1/4 * ||P u(x)||^2.
这个式子很好玩，因为 static score 是：
S_dual(B, delta) = sum(delta_l^2) - 1/4 * sup over u in V of ||P u||^2.
两者放在一起看，就很像：static score 是在所有 budget vectors 里找最 compatible 的那个，stationary point x 则只给出一个特殊的 budget vector u(x)。
所以自然出现一个 gap：
Gap_stat(x) = F(x) - S_dual(B, delta).
它衡量的是：这个 stationary point 的 witness u(x)，距离整个 budget set 里最会投影到 Range(B) 的那个 witness 还有多远。
我现在还不想把 Gap_stat 夸成一个完整的 local optimality classifier，那就太飘了。
但它至少给了一个很清楚的解释：在同一个 instance 里，不同 differentiable stationary points 可以通过它们的 projected witness compatibility 来比较。
这就让 dual score 从一个 “instance-level number” 开始变成一个 “stationary-point comparison framework” 的底层背景。
4. OJMO local-minimum screening 的 dual translation
另一个让我觉得这条线有意义的地方，是它可以和 OJMO paper 里的 local-minimum screening condition 接上。
OJMO paper 里有一个 degree-based necessary condition，用来排除某些 differentiable stationary points 成为 local minimum 的可能。
我后来发现，这个 condition 可以被翻译成 stationary witness 的 projected retention condition。
简单说，对于每条边可以看一个 retention ratio：
rho_l(x) = 当前边长 / prescribed distance.
从 dual witness 的角度看，这也等于：
rho_l(x) = ||(P u(x))_l|| / ||u_l(x)||.
也就是说，它在问：原本 saturated 的 edge-budget block，在投影回 Range(B) 之后，还保留了多少长度？
如果一个 differentiable stationary point 真的是 local minimum，那么某些 edge 的 retention 不能太低。否则它违反 OJMO 的 necessary condition，就不是 local minimum，甚至可以被识别成 strict saddle。
这个 translation 对我来说很重要，因为它说明是在把 OJMO 的 local landscape condition 换成一个 dual-side compatibility language。
换句话说：local minimality forces the stationary witness not to lose too much mass under projection.
这句话我很喜欢。因为它把 local minimum 的必要条件说成了一个 projection geometry statement。
5. 从 first-order witness 到 second-order certificates
做到这里之后，我又回到了 Hessian。
在 differentiable point 上，Hessian 可以写成：
H(x) = 2 B^T M(x) B.
这个式子本身不是啥新鲜事。直接说 “Hessian PSD means local minimum candidate” 也不是啥新鲜事。那只是 classical second-order condition 的换皮版本。
所以真正的问题是：能不能从这个 Hessian representation 里提取一些 structural certificates，而不是每次都 brute-force 算整个 Hessian 的 eigenvalues？
这就是我最近最想推进的方向。
我现在的理解是：Hessian 的负曲率来源和 edge-level radial/transverse decomposition 有关。
对于每条边，沿着当前 edge direction 的 radial part 通常是良性的；真正可能产生 negative curvature 的，是 transverse directions，尤其是当这条边 under-retained，也就是当前边长小于 prescribed distance 的时候。
这件事从直觉上也合理：如果一条边现在太短，而 prescribed distance 更长，那么往垂直方向轻轻打开它，可能会让距离变大、objective 下降。这种负曲率不是沿边方向的，而是在 transverse direction 上。
但 full problem 里还有一个关键限制：edge perturbations 不能随便选。它们必须来自 node perturbation。也就是说，z 必须在 Range(B) 里。
这就是为什么 graph cycles 又出现了。Cycle constraints 会限制哪些 edge-space perturbations 是 realizable 的。
所以真正的问题不是：某条边有没有 negative curvature？而是：这些 edge-level negative directions 能不能在 Range(B) 的 compatibility constraints 下存活下来？
这句话几乎就是我现在对整个 second-order structure 的直觉核心。
6. Cycle-rank negative-inertia bound：负曲率能被 cycle space 藏掉多少？
在这个角度下，我推了一个我目前觉得比较有意思的 structural certificate。
设 m_minus(x) 是 under-retained edges 的数量，也就是当前边长小于 prescribed distance 的边数。每条 under-retained edge 在 transverse directions 上都可能贡献 n - 1 个 negative directions。
如果这些 directions 完全独立那负曲率就很多。但它们不完全独立因为 edge perturbation 必须来自 node perturbation，也就是必须在 Range(B) 里。Graph 的 cycle space 会吃掉一些自由度。
于是出现了一个 cycle-rank negative-inertia bound：如果 under-retained edges 太多，多到 cycle space 无法全部吸收这些 transverse negative directions，那么 reduced Hessian 必然有 negative eigenvalue。
这给了一个 strict-saddle certificate：如果 x 是 differentiable stationary point，并且 under-retained edges 的数量相对于 graph cycle rank 太大，那么 x 一定是 strict saddle。
这个 certificate 的好处是，它不是在算 full Hessian eigenvalue。它是在用 graph structure 和 edge retention pattern 直接判断 negative curvature 是否必须存在。
这点对我来说比“又写了一个二阶条件”重要得多。因为 classical second-order condition 本来就在那里，0 个人需要我重新包装一遍。
我真正想要的是：哪些 structural mechanisms force negative curvature?
Cycle-rank bound 就是其中一个机制。
7. 为什么这不是 OJMO degree test 的重复
OJMO 的 degree-based condition 很像一个 local edge/node test，因为它看某条边的 under-retention 是否相对于某个 node degree 太严重。如果太严重就能排除 local minimum。
我现在这个 cycle-rank certificate 是另一种东西。
它不一定要求某一条边特别坏。它可以检测一种 collective effect：每条边单独看也许都没有坏到触发 OJMO 的 scalar degree test；但很多 under-retained edges 加在一起，会制造太多 transverse negative directions；而 graph cycle space 没有足够维度把它们全部藏掉。
这时候 strict saddle 就被 collective structure 暴露出来了。
我感觉这个区别挺关键的，因为它说明这不是一个单边条件的 rewrite，而是另一个层级的 certificate：OJMO degree test 更 local；cycle-rank certificate 更 global / collective。
它们不是互相替代，而是从不同角度看同一个 landscape。
8. Signed Laplacian 和 cluster-cut：继续把 Hessian 压缩成结构
除了 cycle-rank bound，我还看了两个方向。
第一个是 directional signed-Laplacian reduction。
如果我只看 rank-one perturbation，也就是所有 node 都沿同一个 ambient direction a 移动，只是每个 node 的 scalar coefficient 不同，那么原本 nK 维的 Hessian quadratic form 会降成一个 K 维的 signed Laplacian。
这很漂亮，因为 signed Laplacian 已经有很多图论和 spectral graph theory 的工具，比如 effective resistance threshold。
所以某些 negative curvature certificate 可以从：“检查一个巨大 Hessian”变成：“检查某个 direction 下的 signed weighted graph 是否有 negative eigenvalue”。
第二个是 cluster-cut certificate。
它的想法是：不只看一个 node-star，也不只看全图，而是看一个 cluster 和外界的 boundary。某些 cluster-level perturbations 可以把二阶信息压缩成一个小的 boundary matrix。
这很像在问：如果我把一群节点当成一个局部结构，它和外界连接的那些边，是否已经足够制造 negative curvature？
这条线我现在还不想说已经完整，但它很自然。因为 network localization 本来就有 distributed / local 的语境。如果以后真的要做 algorithmic escape procedure，那么 certificate 最好不要永远依赖 full Hessian。
9. Negative epsilon case：从“有一条坏边”到“能不能真的逃出去”
最近老师让我更细致地看 negative epsilon case，也就是某条边当前距离小于 prescribed distance 的情况。
一开始这个 case 看起来好像很简单：epsilon < 0，所以 Hessian 里有 negative term，那不就是 saddle 吗？
但仔细看之后，这个说法太粗了。
对于单条边，确实可以选择一个 transverse direction，让这一条边的二阶贡献为负。也就是说，在 edge level，它有一个很明确的 negative-curvature mechanism。
但 full objective 不是一条边。你动两个 node，会影响所有 incident edges。别的边可能贡献正项，也可能贡献负项。更重要的是，不是每个 edge-space vector 都能由 node perturbation 产生。
所以真正要构造 escape direction，不能只说：“这条边有 negative epsilon，所以选个 perpendicular y 就好了。”
这最多是 edge-level intuition。
真正需要的是一个 local certified escape procedure：先选一个具体的 negative edge；再构造一个 node perturbation y；然后证明在 full Hessian quadratic form 里，目标边带来的 negative contribution 可以压过其他受影响边的 positive contribution；最后还要保证这个 y 不是一个只在 edge-space 里存在、但 node-space 里根本实现不了的幻想向量。
这就是我最近在做的事情：把“negative epsilon gives transverse negative curvature”从一句直觉，慢慢发展成一个可检查的 local procedure。
目前我不会说这已经是一个 global perfect escape algorithm。那太夸张了。
但至少它已经比单纯 rewrite 老师 note 里的 Hessian formula 更进一步：它开始问如何真正选择 y，如何控制 affected edges，以及如何把 edge-level negative curvature 变成 node-level descent mechanism。
10. 我现在对这条科研线的理解
这几个月做下来，我对这条 dual / Hessian / escape 线的理解变了很多。
一开始，我以为问题是：能不能找到一个有意义的 dual lower bound？
后来我发现，更好的问题可能是：dual side 能不能帮我理解 instance incompatibility 和 stationary point geometry？
再后来，问题又变成：这些结构能不能变成 saddle certificates，甚至进入 escape / restart procedure？
所以现在这条线在我脑子里大概是这样：
第一层：instance-level score。
S_dual 衡量 prescribed edge budgets 和 Range(B) 的 global compatibility。它告诉我这个 instance 本身有没有 structural incompatibility。
第二层：stationary witness。
对于 differentiable stationary point，u(x) 把 prescribed distances 变成 saturated dual witness，并且满足 P u(x) = 2 Bx。于是 static score 开始和 stationary-point geometry 连接。
第三层：local-minimum screening。
OJMO 的 degree-based necessary condition 可以翻译成 projected retention condition。Local minimum 要求 stationary witness 在 projection 之后不能丢掉太多 blockwise mass。
第四层：second-order structural certificates。
Hessian = 2 B^T M B 不是终点。真正有意思的是从这个 representation 里提取 cycle-rank、signed Laplacian、cluster-cut 这些结构性 negative-curvature mechanisms。
第五层：escape procedure。
Negative epsilon edge 提供 transverse negative curvature，但 full escape direction 需要处理 node-space realizability 和 neighboring edge contributions。这个地方目前是我最想继续推进的。
我觉得科研里这种过程其实很真实：很多时候不是一开始就拿到一个闪闪发光的大 theorem，而是先得到一个看起来有点边缘的东西，然后不停问：这个东西到底在说什么？它和已有结果的关系是什么？它只是 rewrite，还是揭示了一个新机制？它能不能变成 certificate？它能不能变成 algorithm？
这条线目前还没有结束也绝对没有到“我已经解决 network localization landscape”的程度。
但我确实觉得它已经从一个 failed dual attempt，变成了一个更成形的 framework：用 dual score 看 instance-level incompatibility，用 stationary witness 看 critical-point geometry，用 Hessian structure 提取 saddle certificates，最后尝试把这些 certificates 变成可执行的 escape logic。
这就是我 3 月之后在这条 dual optimization research 线上做的事情。
From Dual Score to Saddle Certificates: A Small New Step
This note is currently published in Chinese. It records how a dual score for network localization starts connecting to stationary witnesses, projected retention, Hessian structure, and saddle certificates.
三月的时候，我写了一篇讲我在 network localization 这个问题里尝试做 duality，结果两条很自然的 Lagrangian dual 路线都 collapse 到了 0。
当时我的感觉大概是：好吧，dual 没有给我一个漂亮的 lower bound。
但它也没有完全死掉。
真正留下来的，是 conjugate-based DC dual 里出现的一个 projector formula。这个 formula 一开始看起来像一个副产品：它不太像能直接替代 primal objective 也不像一个能马上塞进 algorithm 里的 magic quantity。但它有一个很清楚的几何意义：它在测量 prescribed edge-length budget 和 realizable edge-difference subspace 之间的 incompatibility。
也就是说它不太像传统意义上的 dual solution，反而更像一个 structural score。
当时我对它的理解还很 static：它只依赖 instance，也就是 measurement graph 和 prescribed distances，不依赖某一个 iterate x。所以我把它理解成一个 instance-level difficulty score，一个用来描述这个 localization instance 本身有多不 compatible 的量。
最近这条线又往前走了一点。现在我更愿意这样理解它：
这个 dual score 一开始是 static 的，但它后来开始接触 stationary point geometry 了。
这件事对我来说还挺重要的，因为它说明真的可能变成理解 landscape 的一部分。
1. 上次留下来的东西：一个 instance-level structural score
我研究的 objective 是 network localization / MDS 里很经典的 nonconvex nonsmooth least squares：给定一堆边，每条边都有一个 prescribed distance delta，我们想找 node positions，使得每条边的实际距离尽量接近 delta。
这个问题难在几个地方：它 nonconvex；它 nonsmooth，因为 norm 在 0 处不可微；它有 translation invariance；而且 graph cycles 会带来 global compatibility constraints。
我一开始试图从 duality 入手。最朴素的想法是：如果能找到一个有意义的 dual lower bound，也许就可以解释 instance difficulty 甚至辅助 algorithm。
但实际推下来之后两条很自然的 plain Lagrangian dual routes 都塌掉了。它们基本只能告诉我：
F(x) >= 0。
谢谢你，真的很有用。
不过 conjugate-based DC dual 没有完全塌，它留下了一个 projector formula，大概形如：
S_dual(B, delta) = sum(delta_l^2) - 1/4 * sup over u in V of ||P u||^2.
这里 V 是 blockwise budget set，每条边的 block norm 最多是 2 delta_l，P 是投影到 Range(B) 的 orthogonal projector，Range(B) 就是所有能够由 node positions 产生的 edge-difference vectors。
这个 score 的意义是：在所有允许的 edge-budget vectors 里，最多有多少 budget 可以真正落到 realizable edge-difference subspace 里？
如果全部 budget 都可以放进去，那么 score 是 0。这对应 prescribed distances 可以被某个 configuration exactly realized。如果不能全部放进去，那么 score 就是 positive。这说明有一部分 prescribed edge-length information 和 graph 的 global compatibility constraints 冲突。
所以它不是单纯在看图有没有 cycle，而是在看：这个 graph 加上这组 distances，能不能形成一个 globally compatible 的 edge geometry。
这比“cyclic means hard, forest means easy”细一点。Forest 的确对这个 score 来说是 degenerate 的，因为没有 cycle consistency constraints，score 会变成 0。但 cyclic graph 也不一定 score positive。真正起作用的是 graph structure、delta，以及 ambient dimension 的组合。
它不是一个 topology-only quantity，而是一个 geometry-aware structural quantity。
2. Static score 之后：stationary dual witness
一开始这个 score 只看 instance，不看某一个 point x。
这当然有好处：它像一个全局诊断工具，可以在 algorithm 开始之前告诉你这个 instance 可能有多 incompatible。但也有明显限制：optimization algorithm 真正走的是 iterates，最后遇到的是 critical points / stationary points。一个完全 static 的 score 很难直接告诉我某个 stationary point 是好是坏。
所以我后来问了一个问题：能不能把这个 static dual score 和 differentiable stationary points 连起来？
结果还真的可以。
对于一个 differentiable point x，每条边 B_l x 都不等于 0。于是我可以定义一个 saturated edge-budget vector：u_l(x) 指向 B_l x 的方向，长度为 2 delta_l。
也就是说，u(x) 把每条边的 prescribed distance 变成一个方向化的 dual-side witness。每个 block 都刚好 saturate budget，所以它自然落在 V 的边界上。
我把它叫做 stationary dual witness。
最漂亮的地方是：如果 x 是 differentiable stationary point，那么有一个很干净的 projector identity：
P u(x) = 2 Bx.
直觉上说，这个 identity 把两件事连起来了：u(x) 是 prescribed distances 给出来的 saturated budget direction；Bx 是当前 configuration 真正产生的 edge differences；P 是把任何 edge-space vector 投影回 realizable subspace Range(B)。
所以 stationary condition 可以被理解成：把 saturated witness 投影回 realizable edge-space 之后，刚好得到当前 edge differences 的两倍。
这一下 dual side 就不是纯 static 了。它开始能够读到 stationary point 的 geometry。
3. Pointwise identity：stationary value 也能被 dual witness 读出来
更进一步在 differentiable stationary point 上我可以把 objective value 写成一个 primal-dual identity。
大概意思是：
F(x) = sum(delta_l^2) - 1/4 * ||P u(x)||^2.
这个式子很好玩，因为 static score 是：
S_dual(B, delta) = sum(delta_l^2) - 1/4 * sup over u in V of ||P u||^2.
两者放在一起看，就很像：static score 是在所有 budget vectors 里找最 compatible 的那个，stationary point x 则只给出一个特殊的 budget vector u(x)。
所以自然出现一个 gap：
Gap_stat(x) = F(x) - S_dual(B, delta).
它衡量的是：这个 stationary point 的 witness u(x)，距离整个 budget set 里最会投影到 Range(B) 的那个 witness 还有多远。
我现在还不想把 Gap_stat 夸成一个完整的 local optimality classifier，那就太飘了。
但它至少给了一个很清楚的解释：在同一个 instance 里，不同 differentiable stationary points 可以通过它们的 projected witness compatibility 来比较。
这就让 dual score 从一个 “instance-level number” 开始变成一个 “stationary-point comparison framework” 的底层背景。
4. OJMO local-minimum screening 的 dual translation
另一个让我觉得这条线有意义的地方，是它可以和 OJMO paper 里的 local-minimum screening condition 接上。
OJMO paper 里有一个 degree-based necessary condition，用来排除某些 differentiable stationary points 成为 local minimum 的可能。
我后来发现，这个 condition 可以被翻译成 stationary witness 的 projected retention condition。
简单说，对于每条边可以看一个 retention ratio：
rho_l(x) = 当前边长 / prescribed distance.
从 dual witness 的角度看，这也等于：
rho_l(x) = ||(P u(x))_l|| / ||u_l(x)||.
也就是说，它在问：原本 saturated 的 edge-budget block，在投影回 Range(B) 之后，还保留了多少长度？
如果一个 differentiable stationary point 真的是 local minimum，那么某些 edge 的 retention 不能太低。否则它违反 OJMO 的 necessary condition，就不是 local minimum，甚至可以被识别成 strict saddle。
这个 translation 对我来说很重要，因为它说明是在把 OJMO 的 local landscape condition 换成一个 dual-side compatibility language。
换句话说：local minimality forces the stationary witness not to lose too much mass under projection.
这句话我很喜欢。因为它把 local minimum 的必要条件说成了一个 projection geometry statement。
5. 从 first-order witness 到 second-order certificates
做到这里之后，我又回到了 Hessian。
在 differentiable point 上，Hessian 可以写成：
H(x) = 2 B^T M(x) B.
这个式子本身不是啥新鲜事。直接说 “Hessian PSD means local minimum candidate” 也不是啥新鲜事。那只是 classical second-order condition 的换皮版本。
所以真正的问题是：能不能从这个 Hessian representation 里提取一些 structural certificates，而不是每次都 brute-force 算整个 Hessian 的 eigenvalues？
这就是我最近最想推进的方向。
我现在的理解是：Hessian 的负曲率来源和 edge-level radial/transverse decomposition 有关。
对于每条边，沿着当前 edge direction 的 radial part 通常是良性的；真正可能产生 negative curvature 的，是 transverse directions，尤其是当这条边 under-retained，也就是当前边长小于 prescribed distance 的时候。
这件事从直觉上也合理：如果一条边现在太短，而 prescribed distance 更长，那么往垂直方向轻轻打开它，可能会让距离变大、objective 下降。这种负曲率不是沿边方向的，而是在 transverse direction 上。
但 full problem 里还有一个关键限制：edge perturbations 不能随便选。它们必须来自 node perturbation。也就是说，z 必须在 Range(B) 里。
这就是为什么 graph cycles 又出现了。Cycle constraints 会限制哪些 edge-space perturbations 是 realizable 的。
所以真正的问题不是：某条边有没有 negative curvature？而是：这些 edge-level negative directions 能不能在 Range(B) 的 compatibility constraints 下存活下来？
这句话几乎就是我现在对整个 second-order structure 的直觉核心。
6. Cycle-rank negative-inertia bound：负曲率能被 cycle space 藏掉多少？
在这个角度下，我推了一个我目前觉得比较有意思的 structural certificate。
设 m_minus(x) 是 under-retained edges 的数量，也就是当前边长小于 prescribed distance 的边数。每条 under-retained edge 在 transverse directions 上都可能贡献 n - 1 个 negative directions。
如果这些 directions 完全独立那负曲率就很多。但它们不完全独立因为 edge perturbation 必须来自 node perturbation，也就是必须在 Range(B) 里。Graph 的 cycle space 会吃掉一些自由度。
于是出现了一个 cycle-rank negative-inertia bound：如果 under-retained edges 太多，多到 cycle space 无法全部吸收这些 transverse negative directions，那么 reduced Hessian 必然有 negative eigenvalue。
这给了一个 strict-saddle certificate：如果 x 是 differentiable stationary point，并且 under-retained edges 的数量相对于 graph cycle rank 太大，那么 x 一定是 strict saddle。
这个 certificate 的好处是，它不是在算 full Hessian eigenvalue。它是在用 graph structure 和 edge retention pattern 直接判断 negative curvature 是否必须存在。
这点对我来说比“又写了一个二阶条件”重要得多。因为 classical second-order condition 本来就在那里，0 个人需要我重新包装一遍。
我真正想要的是：哪些 structural mechanisms force negative curvature?
Cycle-rank bound 就是其中一个机制。
7. 为什么这不是 OJMO degree test 的重复
OJMO 的 degree-based condition 很像一个 local edge/node test，因为它看某条边的 under-retention 是否相对于某个 node degree 太严重。如果太严重就能排除 local minimum。
我现在这个 cycle-rank certificate 是另一种东西。
它不一定要求某一条边特别坏。它可以检测一种 collective effect：每条边单独看也许都没有坏到触发 OJMO 的 scalar degree test；但很多 under-retained edges 加在一起，会制造太多 transverse negative directions；而 graph cycle space 没有足够维度把它们全部藏掉。
这时候 strict saddle 就被 collective structure 暴露出来了。
我感觉这个区别挺关键的，因为它说明这不是一个单边条件的 rewrite，而是另一个层级的 certificate：OJMO degree test 更 local；cycle-rank certificate 更 global / collective。
它们不是互相替代，而是从不同角度看同一个 landscape。
8. Signed Laplacian 和 cluster-cut：继续把 Hessian 压缩成结构
除了 cycle-rank bound，我还看了两个方向。
第一个是 directional signed-Laplacian reduction。
如果我只看 rank-one perturbation，也就是所有 node 都沿同一个 ambient direction a 移动，只是每个 node 的 scalar coefficient 不同，那么原本 nK 维的 Hessian quadratic form 会降成一个 K 维的 signed Laplacian。
这很漂亮，因为 signed Laplacian 已经有很多图论和 spectral graph theory 的工具，比如 effective resistance threshold。
所以某些 negative curvature certificate 可以从：“检查一个巨大 Hessian”变成：“检查某个 direction 下的 signed weighted graph 是否有 negative eigenvalue”。
第二个是 cluster-cut certificate。
它的想法是：不只看一个 node-star，也不只看全图，而是看一个 cluster 和外界的 boundary。某些 cluster-level perturbations 可以把二阶信息压缩成一个小的 boundary matrix。
这很像在问：如果我把一群节点当成一个局部结构，它和外界连接的那些边，是否已经足够制造 negative curvature？
这条线我现在还不想说已经完整，但它很自然。因为 network localization 本来就有 distributed / local 的语境。如果以后真的要做 algorithmic escape procedure，那么 certificate 最好不要永远依赖 full Hessian。
9. Negative epsilon case：从“有一条坏边”到“能不能真的逃出去”
最近老师让我更细致地看 negative epsilon case，也就是某条边当前距离小于 prescribed distance 的情况。
一开始这个 case 看起来好像很简单：epsilon < 0，所以 Hessian 里有 negative term，那不就是 saddle 吗？
但仔细看之后，这个说法太粗了。
对于单条边，确实可以选择一个 transverse direction，让这一条边的二阶贡献为负。也就是说，在 edge level，它有一个很明确的 negative-curvature mechanism。
但 full objective 不是一条边。你动两个 node，会影响所有 incident edges。别的边可能贡献正项，也可能贡献负项。更重要的是，不是每个 edge-space vector 都能由 node perturbation 产生。
所以真正要构造 escape direction，不能只说：“这条边有 negative epsilon，所以选个 perpendicular y 就好了。”
这最多是 edge-level intuition。
真正需要的是一个 local certified escape procedure：先选一个具体的 negative edge；再构造一个 node perturbation y；然后证明在 full Hessian quadratic form 里，目标边带来的 negative contribution 可以压过其他受影响边的 positive contribution；最后还要保证这个 y 不是一个只在 edge-space 里存在、但 node-space 里根本实现不了的幻想向量。
这就是我最近在做的事情：把“negative epsilon gives transverse negative curvature”从一句直觉，慢慢发展成一个可检查的 local procedure。
目前我不会说这已经是一个 global perfect escape algorithm。那太夸张了。
但至少它已经比单纯 rewrite 老师 note 里的 Hessian formula 更进一步：它开始问如何真正选择 y，如何控制 affected edges，以及如何把 edge-level negative curvature 变成 node-level descent mechanism。
10. 我现在对这条科研线的理解
这几个月做下来，我对这条 dual / Hessian / escape 线的理解变了很多。
一开始，我以为问题是：能不能找到一个有意义的 dual lower bound？
后来我发现，更好的问题可能是：dual side 能不能帮我理解 instance incompatibility 和 stationary point geometry？
再后来，问题又变成：这些结构能不能变成 saddle certificates，甚至进入 escape / restart procedure？
所以现在这条线在我脑子里大概是这样：
第一层：instance-level score。
S_dual 衡量 prescribed edge budgets 和 Range(B) 的 global compatibility。它告诉我这个 instance 本身有没有 structural incompatibility。
第二层：stationary witness。
对于 differentiable stationary point，u(x) 把 prescribed distances 变成 saturated dual witness，并且满足 P u(x) = 2 Bx。于是 static score 开始和 stationary-point geometry 连接。
第三层：local-minimum screening。
OJMO 的 degree-based necessary condition 可以翻译成 projected retention condition。Local minimum 要求 stationary witness 在 projection 之后不能丢掉太多 blockwise mass。
第四层：second-order structural certificates。
Hessian = 2 B^T M B 不是终点。真正有意思的是从这个 representation 里提取 cycle-rank、signed Laplacian、cluster-cut 这些结构性 negative-curvature mechanisms。
第五层：escape procedure。
Negative epsilon edge 提供 transverse negative curvature，但 full escape direction 需要处理 node-space realizability 和 neighboring edge contributions。这个地方目前是我最想继续推进的。
我觉得科研里这种过程其实很真实：很多时候不是一开始就拿到一个闪闪发光的大 theorem，而是先得到一个看起来有点边缘的东西，然后不停问：这个东西到底在说什么？它和已有结果的关系是什么？它只是 rewrite，还是揭示了一个新机制？它能不能变成 certificate？它能不能变成 algorithm？
这条线目前还没有结束也绝对没有到“我已经解决 network localization landscape”的程度。
但我确实觉得它已经从一个 failed dual attempt，变成了一个更成形的 framework：用 dual score 看 instance-level incompatibility，用 stationary witness 看 critical-point geometry，用 Hessian structure 提取 saddle certificates，最后尝试把这些 certificates 变成可执行的 escape logic。
这就是我 3 月之后在这条 dual optimization research 线上做的事情。