精读笔记

Problem Setting

这篇论文实际处理的是 equality-defined compact embedded manifold 上的 nonsmooth composite optimization：min_{x∈M} f(x)+g(A(x))。困难不在于单独的 Riemannian optimization，也不在于单独的 nonsmooth proximal step，而在于不可行迭代下如何同时保证：复合非光滑项可处理、约束违背不失控、乘子/序列有界、最终 stationarity 可从近似子问题残差推出。

以前路线的卡点很清楚：feasible methods 每步要 retraction/projection，理论简单但大规模矩阵流形代价高；augmented Lagrangian 类方法可以不可行，但子问题难且常把 multiplier boundedness 当假设；Stiefel-specific landing/SLPG/constraint-dissolving 类方法依赖特殊结构，难以直接处理 general nonlinear A 和 general h。本文想解决的关键矛盾是：如何让不可行方法获得 feasible proximal-gradient 类方法的稳定性，而不每步付出保持可行的代价。

Motivation

作者的核心观察是：不可行方法真正缺的不是“下降方向”，而是一个能被算法自身维护的 bounded neighborhood。只要迭代始终留在 M 的一个非退化邻域内，error bound 和 Jacobian full-rank 就能把 constraint violation、distance to manifold、normal correction 的效果串起来；反之，如果靠外部有界性假设，理论就不够自洽。

因此动机不是简单地“避免 retraction”，而是构造一个 feasibility safeguard，使 boundedness 成为算法设计结果。另一个缺口是 nonlinear composite A：若直接在流形上做 prox，子问题通常难；若完全转成约束优化，又会遇到非凸约束子问题。proximal-linear 化是自然折中：只线性化 A 与 h 的约束部分，让非光滑 g 保持在 prox/Moreau 可处理的形式里。

Core Idea

FSIPL 的核心思想是把一次迭代拆成“沿线性化流形优化”和“恢复可行性”两个弱耦合过程。第一步在 T_{x^k}M^k={d:∇h(x^k)d=0} 上求一个 proximal-linear 方向，处理 f+g∘A 的下降；第二步不要求直接 retract 到 M，而是先看中间点是否在安全邻域内，若在则沿 -∇(1/2||h||^2) 做 correction，若不在才投影；第三步通过 merit function 同时检查目标下降和 feasibility。

本质区别在于它不是把 manifold constraint 当作每步必须精确满足的硬约束，而是当作一个可被 safeguard 控制的动态状态。这个建模方式把 retraction 从主循环的必要操作降级为异常恢复机制。直觉上这会更 scalable，尤其在 Stiefel/oblique 这类 projection/retraction 成本明显但 h 与 ∇h 便宜的场景。理论上成立依赖 error bound：控制 ||h|| 就足以控制离流形距离，从而保持所有 Lipschitz、非退化常数有效。

Method

关键机制可以压缩为四个。

第一，proximal-linear subproblem 负责把 nonlinear composite g(A(x)) 变成 g(A(x^k)+∇A(x^k)d)。这一步保留 g 的凸 prox 结构，同时用二次项强凸化，避免直接处理原始非凸复合。其 dual 使用 Moreau envelope，inexactness 以 ||∇G_k(λ,μ)||≤Δ_k 表示，因此残差可直接进入 stationarity 与复杂度证明。

第二，direction d 被限制在 ∇h(x^k)d≈0 的 tangent-like 空间上。注意这里不是 M 的真实 tangent，而是当前 level set h(x)=h(x^k) 的线性化 tangent；这让 x^k 即使不可行也能定义“切向优化方向”。这是不可行版本能工作的关键设计。

第三，correction step 负责把 y^k=x^k+ηd^k 的 constraint violation 压回安全区。若 ||h(y^k)||≤θ/κ，用 gradient step on N(x)=1/2||h(x)||^2；若超出则 Proj_M(y^k)。前者是便宜的 normal correction，后者是 safety fallback。

第四，line search 用 Φ_α=F+α||h|| 接受点，并显式扣除 d、v、h(y) 的下降项，同时补偿 inexactness Δ_k 和非单调项 ρ_k。它的作用不是普通调步长，而是把 feasibility safeguard 与 descent proof 绑定起来，确保 x^k 始终在 M_θ 内。

Key Insight / Why It Works

最核心的有效性来自“可行性控制被算法内生化”。Assumption 1 给了两个支点：dist(x,M)≤κ||h(x)|| 让 constraint violation 成为距离控制器；∇h∇h^T 在 M_{2θ} 上一致正定让 normal correction 有统一收缩能力。只要 line search 确保点不离开 M_θ，所有局部常数都变成全局有效常数，后续 boundedness、multiplier boundedness、subsequence convergence 都顺了。

第二个关键是 dual residual Δ_k 的角色被设计得很干净。它同时度量 ∇h d 的偏差和 ∇A d-v 的偏差，使得 d、v、λ、μ 都能被统一界住。stationarity residual 不是事后硬凑，而是直接从近似 KKT 系统得到：d→0、v→0、h→0 后，极限点满足 KKT。

第三，论文真正有新意的理论部分是 KL 辅助函数 P，而不是 merit function 本身。Φ_α 足够做 subsequential convergence 和 complexity，但不适合 relative-error KL 证明，因为其 subgradient 不直接匹配 proximal-linear 子问题的近似最优性。P 用 z 表示 shifted composite argument，用 υ^3=h(x)、s^3=A(x)-z 吸收 feasibility 与 composite mismatch；cubic encoding 让额外 normal components 是高阶小量。这是一个很典型的“为了让 KL 证明闭合而重构 Lyapunov state”的技巧，值得迁移。

哪些可能只是辅助：nonmonotone ρ_k、具体 backtracking 比例、BB-like t_k 实现更多是 engineering。实验中的速度增益大概率主要来自少做 projection/retraction，而不是 proximal-linear 模型本身有更强的优化路径。所谓 generality 主要是理论建模层面的 generality，数值上尚未充分证明。

Relation To Prior Work

技术谱系上，它位于 Riemannian proximal-linear / manifold proximal gradient 与 infeasible SQP/landing methods 的交界。和 feasible manifold proximal-linear 方法相比，本质差异是允许 x^k∉M，并用 h 的 error bound + correction step 替代每步 retraction。和 augmented Lagrangian 相比，它不把非线性约束放进难解非凸子问题，而是每步只解强凸线性化 composite subproblem；乘子也不是外部罚函数迭代的主变量，而是 dual proximal-linear residual 的产物。

和 Stiefel-specific infeasible 方法相比，FSIPL 的实质新增是：把“不可行但安全”的思想从 Stiefel 的结构化约束推广到一般 global defining function h，并允许 nonlinear A。看似新的部分中，merit line search、normal correction、prox-linear、KL framework 都是已有思想；真正的组合创新在于：这些组件被组织成一个能自证 boundedness 的 infeasible nonsmooth composite manifold scheme。

它并不是提出了更快的一阶复杂度，O(ε^{-2}) 与现有一阶方法同阶；贡献是把这个复杂度搬到了“不可行 + inexact + nonlinear composite + general equality-defined manifold”的 setting 下。

Dataset / Evaluation

实验覆盖 SPCA 和 SSC。SPCA 是 A=I 的 Stiefel nonsmooth benchmark；SSC 用 A(X)=XX^T，能测试 nonlinear composite 的一部分 claim。比较对象分别是 ARPG/SLPG 和 minimax reformulation-based methods。结果显示 FSIPL 在相近目标值下 CPU 时间更少，projection 次数很少，这与其核心 claim——避免每步 retraction/projection——是相符的。

但 evaluation 的支撑范围有限。两个任务都在 Stiefel 上，虽然理论声称适用于更一般 embedded submanifolds，但没有 oblique 以外、更复杂 h、非矩阵流形或真实大规模应用的验证。SSC 的比较对象走 minimax reformulation，是否是最强 baseline 不完全清楚。实验没有充分拆分 inner dual solve、line search、projection fallback、correction step 各自成本，因此增益归因不够清晰。总体上实验验证了“在典型 Stiefel 稀疏问题上有效且 projection 少”，但不足以证明 general manifold setting 下的系统性优势。

Limitation

最重要的限制是前提强。全局 defining function 与全局 error bound dist≤κ||h|| 并不总是自然可得；紧致性也排除了许多实际问题。g 被假设 Lipschitz，这对很多 extended-valued convex regularizer 或约束型 nonsmooth 项不适用。理论中的 uniform eigenvalue bound 在 M_{2θ} 内成立，但实际算法参数 θ、κ、C1、C2 的可得性与保守性会影响可用性。

scalability 的上限不只由是否 retraction 决定，还由 dual problem 求解决定。若 p 或 m 很大，或 prox_g / Moreau envelope 不便宜，FSIPL 的优势可能消失。论文没有给出 inner complexity，因此 O(ε^{-2}) 是 outer iteration 复杂度，不等价于总计算复杂度。

KL 全序列收敛部分的条件更像理论闭合而非 practical recipe：需要特定 Δ_k 策略、η=1 条件、辅助 P 的 KL 性质。虽然 semialgebraic 情况下合理，但构造复杂，且不说明收敛速率。另一个现实问题是 projection fallback 被说成只会有限发生，但早期是否频繁、在困难 h 上是否昂贵，文中未充分说明。

实验层面，增益来源不清：可能主要来自 Stiefel 上避免频繁 retraction/projection和实现细节，而非方法在 general nonlinear equality manifold 上有普遍优势。

Takeaway

• 1. 对不可行 manifold optimization，关键不是完全避免 projection，而是设计一个可证明的 safety envelope：让 boundedness 从算法机制中产生，而不是作为假设写进 theorem。
• 2. nonlinear composite nonsmooth manifold problem 可以通过 proximal-linear + dual Moreau residual 组织得很干净；v 作为 shifted composite discrepancy 是分析 stationarity 的关键状态变量。
• 3. full-sequence KL 证明中，直接用 merit function 未必合适；应围绕算法真实下降结构构造扩展 Lyapunov function。
• 本文的 P 函数是可迁移的证明 insight。

一句话总结

这篇论文把 Stiefel 上的 infeasible-but-safe 思路推进到一般非光滑复合流形优化，用 proximal-linear 方向、feasibility safeguard 和扩展 KL Lyapunov 构成一个理论自洽的不可行一阶框架，真正贡献在于可行性控制的内生化而非更优复杂度。