Parabolic second-order tangent sets of semialgebraic sets and applications to polynomial optimization

技术摘要：半代数集的抛物线二阶切集及其在多项式优化中的应用

问题陈述
一阶切锥虽然在变分分析和约束优化中至关重要，但无法捕捉曲率、约束的二阶激活或分支可行行为。这些特征在标准的阶一模型不足以处理的退化多项式优化问题中至关重要。本文旨在建立一个严谨且可由代数检查的框架，用于对半代数集进行二阶局部分析。具体而言，研究了抛物线二阶切集，该集合刻画了可行扩张形式 $x(t) = \bar{x} + tu + \frac{1}{2}t^2w + o(t^2)$ 中的二阶修正项 $w$，并寻求确定该几何对象何时与由约束的梯度和黑塞矩阵（Hessian）导出的代数模型相一致。

方法论
本文在基本闭半代数集 $S = \{x \in \mathbb{R}^n : g_i(x) = 0, h_j(x) \leq 0\}$ 的范畴内运行。其方法论通过以下步骤进行：

1. 定义： 作者定义了在点 $\bar{x}$ 处沿方向 $u$ 的三种二阶切集变体：

   • 外抛物线切集 ($T^{2,out}_S$)，通过序列极限定义；
   • 内抛物线切集 ($T^{2,in}_S$)，通过对序列的全称量化定义；
   • 弧生成切集 ($T^{2,arc}_S$)，通过半代数弧的存在性定义；
   • 代数二阶线性化集 ($L^2_S$)，由基于约束泰勒展开的关于 $w$ 的等式和不等式约束定义。

2. 正则性条件： 核心方法论引入了代数抛物线正则性。该条件要求在 $(\bar{x}, u)$ 处满足两个属性：

   • 方向秩稳定性： 二阶激活族（second-order active family）的梯度矩阵的秩在趋向 $\bar{x}$ 且方向为 $u$ 的可行弧上保持不变。
   • 抛物线弧可实现性： 每个形式上可容许的二阶修正 $w \in L^2_S(\bar{x}; u)$ 都能由实际的半代数弧实现。

3. 分层（Stratification）： 对于奇异集，本文利用有限 $C^2$ 半代数分层。它将奇异集的切集分解为所选分层（分支）在给定方向下趋向该点的分层切集的并集。

主要贡献与结果

• 代数特征化： 本文证明，在代数抛物线正则性条件下，外、内及弧生成抛物线切集均与代数二阶线性化集一致：
  $$T^{2,out}_S(\bar{x}; u) = T^{2,in}_S(\bar{x}; u) = T^{2,arc}_S(\bar{x}; u) = L^2_S(\bar{x}; u).$$
  这一结果将抽象的几何对象转化为涉及梯度和黑塞矩阵的有限线性与二次方程/不等式系统。

• 显式公式： 作者推导了特定类集合的精确公式：

  • 光滑超曲面： 切集由涉及定义多项式黑塞矩阵的单个线性方程定义。
  • 正则完全交集： 切集是涉及雅可比矩阵和二阶导数的线性映射的核。
  • 光滑不等式系统： 在梯度线性无关的情况下，切集是由激活约束定义的多面体集。
  • 分层集： 提供了一个公式，其中奇异集的切集是相关分层闭包的切集的并集。

• 优化应用：

  • 二阶必要条件： 若 $\bar{x}$ 是局部极小值点，则对于每个临界方向 $u$ 和每个 $w \in T^2_S(\bar{x}; u)$，二次型 $Q_f(\bar{x}; u, w) = \nabla f(\bar{x})w + u^T \nabla^2 f(\bar{x})u$ 必须是非负的。在代数抛物线正则性下，该测试简化为检查 $w \in L^2_S(\bar{x}; u)$。
  • 二次增长性： 本文提供了二次增长（即 $f(x) \geq f(\bar{x}) + c\|x-\bar{x}\|^2$）的充分条件。若对于所有单位临界方向，$Q_f$ 在代数线性化集上严格正定，则二次增长成立。
  • 拉格朗日乘子： 研究结果给出了涉及拉格朗日乘子的判据，其中目标函数的二阶项需与经过激活不等式约束曲率调整后的拉格朗日黑塞矩阵进行比较。

意义与主张
本文声称使半代数可行集的二阶构造具有代数可检查性。其意义在于弥合了变分分析（通常处理极限对象）与实代数几何（提供有限、可计算结构）之间的鸿沟。

作者强调，其方法检测到了一阶切锥会遗漏的特征：

• 曲率： 区分平坦分支与弯曲分支。
• 平坦性： 识别约束何时是“平坦”的（例如 $y \geq x^4$），使得二阶条件虽为局部极小性所必需，但对于二次增长却是不充分的。
• 分支依赖性： 处理奇异集（如尖点或接触点），其中不同的分支可能具有不同的二阶行为，从而需要分支化分析而非单一的线性化方程。
• 二次缩放失效： 强调某些情况（如尖点 $y^2 = x^3$），其中标准的抛物线缩放 $t^2$ 不足以捕捉第一个非平凡修正，从而需要更高阶或分数阶的分析。

该工作被视为对全局代数方法（如 Lasserre 的矩-SOS 层级或梯度理想方法）的局部补充，提供了可通过多项式代数计算的精确局部最优性测试。论文最后谦逊地指出，虽然解决了正则情况下的二阶问题，但对于奇异分支（如 Puiseux 指数）的高阶或分数阶类比，以及与全局证书之间的联系，仍有待进一步研究。