精读笔记
Problem Setting
论文实际处理的是 smooth derivative-free optimization over polyhedral convex constraints 中 direct search 的 polling-set 几何基础。问题不是如何写一个 direct-search loop，而是：在约束边界附近，什么样的有限 polling set 足以同时保证 feasible polling、下降检测和 O(ε^{-2}) 复杂度。
传统 unconstrained direct search 依赖 PSS/cosine measure；linearly constrained direct search 依赖 approximate tangent cone generators。后者的核心问题是过度局部切向化：它保证不会走出可行域，但只看 tangent cone，忽略了 B(x,α)∩Ω 的真实局部形状。尤其当 x 离边界很近但还没到边界时，能向边界方向走一小步，这类方向不在 tangent-cone-only 理论里，却在实践中非常有用。
关键矛盾是：为了理论收敛，polling directions 要尊重约束；为了实际效率，它们又不能只沿切向探索。已有理论能解释前者，解释不了后者。
Motivation
已有路线缺的是一个能度量“局部可行区域覆盖质量”的 polling-set 概念。cosine measure 是全空间角度条件；approximate tangent cone 是 cone-level 条件；二者都不是对 B(x,α)∩Ω 的直接刻画。
作者观察到 model-based DFO 已经有类似语言：Λ-poisedness 不问插值点是否形成某个 cone，而问局部区域中的点能否被稳定表示，从而控制模型误差。direct search 中 polling set 也可以被看成一种只使用函数值比较的局部几何 discretization，因此自然应有对应的“poisedness-like”条件。
真正的缺口是 constrained direct search 缺少一个与 convex-constrained model-based DFO 对齐的质量度量。论文的动机不是单纯改进 polling heuristic，而是重写 direct-search 复杂度证明所需的几何假设。
Core Idea
核心思想是把 polling set 从“方向集合”改成“局部可行位移的有界非负字典”。给定 x 和 α，D 是 Λ-PSS 如果任意 feasible local displacement v，即 x+v∈Ω 且 ||v||≤α，都能写成 v=Σ c_i d_i，c_i≥0，并且 Σc_i≤Λ。这里 Λ 扮演传统 cosine measure 中 κ^{-1} 的角色，但它是尺度相关、约束相关、局部区域相关的。
这个建模方式改变了 direct search 的 inductive bias：不再只要求存在一个和负梯度成锐角的方向，而是要求 polling set 以受控系数覆盖整个局部可行 ball。于是 tangent cone 外的方向不再是 optional engineering trick，而是覆盖 B(x,α)∩Ω 的必要组成部分。尤其是靠近边界时，负 tangent directions 或按 slack 缩放的方向捕捉了“可以往边界内侧/法向小幅移动”的局部结构。
和 prior 的本质区别：prior 在 cone 上工作，本文在 truncated feasible neighborhood 上工作。这个差别很重要，因为 direct search 的 sufficient decrease 实际发生在有限步长 α 上，而不是 infinitesimal cone 上。
Method
1. Λ-PSS 定义：解决 polling-set quality 与局部可行几何脱节的问题。它要求 finite directions 对 B(x,α)∩Ω 做非负覆盖，并用 Λ 控制表示稳定性。核心变化是允许方向长度随 slack 缩小，不再要求统一下界。
2. Algorithm 2 的尺度重写：polling direction d 已经是实际位移，而不是 α times unit direction。这个看似小改动很关键，因为边界附近某些有用方向只能走很短；传统 norm-bounded-below 假设会排除它们。
3. Complexity proof：unsuccessful iteration 给出对所有 d∈D 的一阶下界；把 stationarity-descent vector v* 用 Λ-PSS 分解后，得到 π(x) ≤ O(αΛ)。因此若 α < O(π/Λ)，iteration 必 successful。于是 α 不会在 π>ε 时无限变小，得到 O(Λ^2 ε^{-2}) iterations。
4. Bound constraints 构造：每个坐标正负方向按到上下界的 slack 截断。它解决的是传统 tangent-only 方法在接近边界时无法直接走到边界的问题。代价是 Λ 最坏从 √n 增到 n。
5. General linear constraints 构造：在线性独立 nearly-active constraints 下，用 tangent cone generators、其负向可行缩放、以及 active normals null-space 的正负基方向组合。它解决的是 tangent cone 不张满局部可行 ball 的问题；核心代价是 Λ 依赖 active-normal matrix 的 condition number。
6. Degenerate case practical recipe：用 double description 找 cone generators，再递归补 span。这是工程上合理的 fallback，但理论上没有闭合，是论文最明显的断点。
Key Insight / Why It Works
最重要的 insight 是：direct search 的确定性复杂度并不真正需要 polling directions 有统一长度下界，也不真正需要 classical cosine measure；它需要的是“下降位移可以由 polling displacements 以有界非负系数组合表示”。这是更贴近 sufficient-decrease proof 的条件。
证明为什么成立非常干净：若所有 poll points 都失败，则每个 d 的一阶下降都不够好；如果真实 stationarity direction v* 可以由这些 d 以 Σc_i≤Λ 表示，那么 v* 上的一阶下降也不可能太大，于是 π(x) 被 αΛ 控制。这说明 Λ-PSS 是直接嵌入 complexity argument 的最小几何对象之一。
最核心贡献是 constrained Λ-PSS 这个重新表述，而不是某个具体 cone-generator implementation。构造部分重要，但更像是在 polyhedral case 证明该定义非空且可操作。实验增益也大概率来自这个新 bias：polling set 覆盖 finite-step feasible neighborhood，而非只覆盖 tangent approximation。
哪些可能只是辅助：Algorithm 2 本身基本是 direct search 标准框架的尺度重写；sufficient decrease 和 step-size proof 也沿用经典套路。数值部分中 full Λ-PSS 优于 tangent+normal，可能部分来自 polling order / added directions / larger test-time compute，而不仅是 Λ-PSS 质量本身；文中没有完全隔离这些因素。不过由于 objective evaluation budget 下仍更好，说明额外方向不是纯粹 brute-force，确实改善了 search geometry。
这不是 scaling paper，也不是 data/retrieval 问题；本质是 better geometric inductive bias。它把有限步长约束几何纳入 polling-set quality，而不是靠 infinitesimal tangent cone 替代真实可行邻域。
Relation To Prior Work
最接近的是三条线：classical direct search 的 PSS/cosine measure；linearly constrained generating set search 的 approximate tangent cone；model-based DFO 的 Λ-poisedness。
与 PSS 的关系：unconstrained 情况下 Λ-PSS 和 cosine measure 基本等价到常数因子，但 Λ-PSS 是尺度化版本，能容纳小 norm directions。这个不是完全新数学对象，而是把 PSS 的角度条件改写成 bounded positive representation。
与 constrained generating set search 的关系：prior 要求 polling set 生成 approximate tangent cone；本文要求覆盖 B(x,α)∩Ω。前者是 cone-level local differential geometry，后者是 finite-step feasible geometry。因此本文能解释为什么实践中加入法向/反向方向有效，而 classical theory 解释不了。
与 model-based DFO 的关系：本文明显借用了 Λ-poisedness 的表示稳定性思想，但没有构造模型，也不使用插值误差。实质创新在于把 poisedness-like coefficient control 移植到 direct-search polling，并证明它足以驱动 worst-case complexity。
看似新的部分中，复杂度证明属于经典 direct search proof schema 的重组；真正新增的信息是 constrained Λ-PSS 定义及其对 cone 外方向必要性的理论化。
Dataset / Evaluation
评估使用 CUTEst 中 bound-constrained 和 general linear inequality constrained problems，维度整体偏低，预算按 200(n+1) evaluations。它覆盖了标准 DFO benchmark 的一部分，但不是高维工业 black-box，也没有噪声、昂贵仿真或非线性凸约束场景。
实验设计主要比较三类 polling：tangent-only、tangent+normal heuristic、full Λ-PSS。这个对照能直接检验核心 claim：cone 外方向是否有用，以及 Λ-PSS 是否比已有 heuristic 更好。结果支持这个 claim，尤其在线性不等式约束中 full Λ-PSS 的优势更明显；bound constraints 下 full Λ-PSS 与 normal heuristic 接近，说明该场景中新构造的额外信息有限。
不足是 evaluation 没有充分分解增益来源：full Λ-PSS 可能有更多候选方向，虽然预算控制了 objective evaluations，但 opportunistic polling 顺序、direction ordering、cone-generation细节都会影响表现。退化 active-set 情况只通过估计 Λ 的分布展示，大多数时候可行，但 outliers 明显；这更像 sanity check，不是理论验证。
Limitation
最大理论限制是 nearly-active constraints 线性独立假设。现实线性约束中退化 active set 很常见，尤其是冗余约束、多面体顶点、高维工程约束。论文在这类情况下没有 guaranteed Λ-PSS construction，只给了 practical recursive/double-description recipe；这意味着核心理论没有覆盖最麻烦的 polyhedral geometry。
第二个限制是 Λ 的常数可能很差。一般线性约束下 Λ 依赖 qκ(A)，病态 active normals 会直接放大 complexity bound。表面上得到 O(n^2 ε^{-2}) iterations / O(n^3 ε^{-2}) evaluations，但隐藏常数可能支配一切。这个上限在数值优化中不是小问题。
第三，scalability 仍不清楚。构造 tangent cone generators 对一般多面体可能组合爆炸；double description 在高维/多约束下不是便宜操作。论文最后建议 probabilistic 或 reduced-space polling，事实上说明当前 deterministic Λ-PSS 构造的高维可用性有限。
第四，所谓 general convex-constrained direct search 理论在定义层面成立，但有限 polling set 可实现性基本依赖 polyhedral structure。对 smooth convex constraints，除非引入近似、投影或随机化，否则这个框架还没有真正落地。
最后，实验增益归因不完全清楚：可能主要来自增加了 boundary-reaching / reverse-tangent directions，而不是完整 Λ-PSS 理论常数本身。文中未充分说明不同 direction subset、polling order 和 cardinality 对性能的独立影响。
Takeaway
- 1. direct search 的 constrained polling quality 应该定义在 finite-step feasible neighborhood 上，而不是只定义在 tangent cone 上；这是本文最值得迁移的思想。
- 2. Λ-PSS 给了一个统一语言，把 PSS、cosine measure、model-based poisedness 和 constrained polling 几何放到同一框架里；这比具体构造更重要。
- 3. cone 外方向不是 heuristic decoration，而是覆盖 B(x,α)∩Ω 的结构性需求。
- 以后设计 constrained DFO polling set 时，应优先考虑局部可行集合的 representation，而非只考虑 tangent feasibility。
一句话总结
这篇论文把 constrained direct search 的 polling-set 理论从 tangent-cone generation 推进到 local feasible-neighborhood representation，用 Λ-PSS 解释并规范化 cone 外 polling directions，是一次几何质量度量层面的实质重构。