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

技術要約：半代数集合の放物線型二次接集合と多項式最適化への応用

問題提起
一次接錐（first-order tangent cones）は、変分解析や制約付き最適化において基礎的なものであるが、曲率、制約の二次的な活性化、あるいは分岐ごとの実行可能挙動を捉えることはできない。これらの特徴は、標準的な一次モデルでは不十分な、退化した多項式最適化問題において極めて重要である。本論文は、半代数集合の二次的な局所解析のための、厳密かつ代数的にチェック可能な枠組みの必要性に取り組んでいる。具体的には、**放物線型二次接集合（parabolic second-order tangent set）**を調査しており、これは実行可能展開 $x(t) = \bar{x} + tu + \frac{1}{2}t^2w + o(t^2)$ における二次的な補正 $w$ を特徴付けるものである。そして、この幾何学的対象が、勾配およびヘッセ行列から導かれる代数的なモデルと一致する場合を特定することを目的としている。

手法
本論文は、基本閉半代数集合 $S = \{x \in \mathbb{R}^n : g_i(x) = 0, h_j(x) \leq 0\}$ の範疇で動作する。手法は以下のステップに従って進行する：

1. 定義： 著者らは、点 $\bar{x}$ における方向 $u$ に対する3つの二次接集合のバリエーションを定義している：

   • 外側放物線型接集合 ($T^{2,out}_S$)：逐次極限を通じて定義される。
   • 内側放物線型接集合 ($T^{2,in}_S$)：列に関する全称量化を通じて定義される。
   • 弧生成型接集合 ($T^{2,arc}_S$)：半代数的な弧の存在を通じて定義される。
   • 代数的二次線形化集合 ($L^2_S$)：制約のテイラー展開から導かれる $w$ に関する等式および不等式制約によって定義される。

2. 正則性条件： 手法の核となるのは、**代数的放物線正則性（algebraic parabolic regularity）**の導入である。この条件は、$(\bar{x}, u)$ において以下の2つの特性を要求する：

   • 方向的ランク安定性（Directional Rank Stability）： 二次的に活性な関数の勾配行列のランクが、$\bar{x}$ に方向 $u$ で接近する実行可能な弧に沿って一定であること。
   • 放物線弧実現可能性（Parabolic Arc-Realizability）： 形式的に許容されるすべての二次補正 $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).$$
  この結果は、抽象的な幾何学的対象を、勾配とヘッセ行列を含む有限の線形および二次方程式・不等式の系へと変換する。

• 明示的な公式： 著者らは特定のクラスの集合に対して正確な公式を導出している：

  • 滑らかな超曲面： 接集合は、定義多項式のヘッセ行列を含む単一の線形方程式によって定義される。
  • 正則な完全交差（Regular Complete Intersections）： 接集合は、ヤコビ行列と二階微分を含む線形写像の核（kernel）である。
  • 滑らかな不等式系： 勾配の線形独立性の下で、接集合は活性な制約によって定義される多面体集合となる。
  • 層化された集合： 特異集合の接集合は、関連する層の閉包の接集合の和集合であるという公式が提供されている。

• 最適化への応用：

  • 二次必要条件： $\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)$ をチェックすることに帰着する。
  • 二次成長（Quadratic Growth）： 二次成長（すなわち、$f(x) \geq f(\bar{x}) + c\|x-\bar{x}\|^2$）のための十分条件を提示している。すべての単位臨界方向に対して $Q_f$ が代数的線形化集合上で厳密に正であれば、二次成長が成立する。
  • ラグランジュ乗数： これらの結果は、目的関数の二次項が、活性な不等式制約の曲率に対して調整されたラグランジュのヘッセ行列と比較される、ラグランジュ乗数を含む判定基準をもたらす。

意義と主張
本論文は、半代数的な実行可能集合に対して、二次的な構成を代数的にチェック可能にすることを主張している。その意義は、変分解析（しばしば極限対象を扱う）と実代数幾何学（有限で計算可能な構造を提供する）の間の溝を埋めることにある。

著者らは、彼らのアプローチが一次接錐が見逃す特徴を検出することを強調している：

• 曲率： 平坦な実行可能枝と、曲がった実行可能枝を区別する。
• 平坦性： 制約が「平坦」である場合（例：$y \geq x^4$）を特定し、二次的な条件が局所最小性のために必要であるが、二次成長には不十分であるケースを識別する。
• 枝依存性： 異なる枝が異なる二次的挙動を持つ（尖点や接点のような）特異集合を扱い、単一の線形化方程式ではなく、枝ごとの解析を要求する。
• 二次スケーリングの失敗： 標準的な放物線スケーリング $t^2$ が、最初の非自明な補正を捉えるには不十分であり、より高次の、あるいは分数次（fractional-order）の解析を必要とするケース（例：尖点 $y^2 = x^3$）を浮き彫りにする。

本研究は、グローバルな代数的メソッド（Lasserreのモーメント-SOS階層や勾配イデアル的アプローチなど）に対する局所的な補完として提示されており、多項式代数を通じて計算可能な、精密な局所最適性テストを提供している。論文は控えめに結論づけており、正則な枝における高次または分数次の類似物（例：ピューズ指数）や、グローバルな証明（certificate）との関連性に関する問題は依然として未解決であるとしている。