On the role of semismoothness in nonsmooth numerical analysis: Theory

本論文は、 nonsmooth 問題の数値解法において、正確な部分微分や一般化ヤコビ行列が不要で、半滑らかな導関数で十分であることを示し、特にパラメータ付半滑らか* 包含に対する解写像の半滑らかな導関数と、その集合値部分の極限コ導関数や SC 導関数との関係を理論的に解明するとともに、半滑らか* 多価写像における厳密なプロ微分可能性に関する帰結を導出するものである。

要約

この論文は、数学の難しい分野である「なめらかでない問題（ nonsmooth problems）」をコンピュータで解くための新しい「道具」と「考え方」について書かれています。

専門用語を避け、日常の例え話を使って、この研究が何をしているのかを説明します。

1. 物語の舞台：「ガタガタ道」を走る車

まず、この研究が扱っている問題は、**「ガタガタ道」**を走る車のようなものです。

• なめらかな道（滑らかな関数）： 舗装された滑らかな道路。ここを走るなら、車のハンドル（微分）を少し動かすだけで、車がどう曲がるか正確に予測できます。
• ガタガタ道（なめらかでない問題）： 石ころだらけの道や、急な段差がある道。ここでは「ハンドルを少し動かすと車がどうなるか」という予測が難しくなります。数学的には「微分（変化率）」が定義できない点がたくさんあります。

この「ガタガタ道」を効率的にゴール（最適解）まで導くには、従来の「完璧な地図（正確な微分）」が手元になくてもいいのです。**「だいたいの進み具合がわかる道具（半滑らかな導関数）」**があれば十分なのです。

2. 従来のアプローチ vs 新しいアプローチ

従来の方法：「完璧な地図」を探す

これまでは、問題を解くために「クラーク一般化ヤコビ行列」という、非常に厳密で複雑な「完璧な地図」を作ろうとしていました。しかし、この地図を作るのは非常に難しく、時には不可能な場合もあります。

新しい方法：「適当なコンパス」を使う

この論文の核心は、「完璧な地図」がなくても、ある特定の性質（半滑らか性）を持った「適当なコンパス」さえあれば、目的地にたどり着けるという発見です。

• 半滑らか性（Semismoothness）： これは「道がガタガタでも、全体として進み方が一定の法則に従っている」状態を指します。
• コンパスの役割： この「コンパス」は、正確な微分値ではなく、その場その場で「だいたいこの方向に進めばいい」と教えてくれる値（擬似勾配など）です。

3. この論文の重要な発見：「影」を頼りにする

この研究の最も面白い点は、**「複雑な影（多価写像）」**を扱う新しい道具を作ったことです。

• 単一の道（単一値写像）： 一つの入力に対して、一つの答えが出る道。
• 分岐する道（多価写像）： 一つの入力に対して、複数の答え（分岐）が出てくる道。例えば、「この条件なら A にも B にも行ける」という状態です。

これまで、分岐する道（多価写像）の「半滑らか性」を調べるのは非常に難しかったです。しかし、この論文では、**「SCD（部分空間を含む）導関数」**という新しい道具を紹介しています。

【アナロジー：骨格と筋肉】

• 限界コード微分（従来の道具）： 道全体を覆う「筋肉」や「皮膚」のようなもの。非常に詳細ですが、計算が重たく、扱いにくい。
• SCD 導関数（新しい道具）： 道の「骨格」のようなもの。筋肉の細かい動きまでは捉えませんが、道がどう曲がっているかの「骨格（基本構造）」をシンプルに捉えます。

この論文は、「骨格（SCD 導関数）」さえ正しければ、その「筋肉（限界コード微分）」の性質も保証されることを証明しました。つまり、複雑な計算をせずとも、骨格を見るだけで「この道は半滑らか（解きやすい）だ」と判断できるようになったのです。

4. 具体的な応用：二段階の迷路（バイレベル問題）

この研究が実際にどう役立つかを、**「二段階の迷路」**という例で説明します。

• 問題： 上層のリーダーが「下層のフォロワー」の行動を予測しながら、自分の利益を最大化したい。
• 状況： フォロワーの行動は、複雑なルール（ガタガタ道）で決まる。リーダーは、フォロワーがどう動くか（解の写像）を正確に計算できないかもしれない。

この論文の貢献：
リーダーは、フォロワーの「完璧な動きの予測」ができなくても、フォロワーの行動ルールが「骨格（SCD 導関数）」を持っていれば、リーダー自身の最適化問題も「半滑らか」として扱えることがわかりました。

つまり、**「フォロワーの動きが複雑でも、その骨格さえわかれば、リーダーは効率的に最適解を見つけられる」**というのです。

5. まとめ：なぜこれがすごいのか？

この論文は、以下のようなことを示しました。

1. 完璧でなくてもいい： 厳密な微分値がなくても、「半滑らか」という性質さえ満たせば、数値計算は成功する。
2. 骨格を見ればわかる： 複雑な分岐する道（多価写像）でも、その「骨格（SCD 導関数）」を調べるだけで、解きやすさを判断できる。
3. 組み合わせが簡単： 複数のガタガタ道をつなげて複雑な問題（二段階最適化など）を解くとき、それぞれの「コンパス」をつなげるだけで、全体も「コンパス」で解けるようになる。

一言で言うと：
「なめらかでない複雑な問題を解く際、無理やり『完璧な地図』を作ろうとせず、道の本質的な『骨格』や『だいたいの進み方』さえ掴めば、効率的にゴールにたどり着ける新しい方法論を確立した」のです。

これは、工学、経済、機械学習など、現実世界の複雑な問題をコンピュータで解く際の、非常に強力な新しい「指針」となるでしょう。

技術概要

1. 問題設定と背景

非滑らかな数値解析において、従来の手法はしばしば「正確な部分勾配（subgradient）」や「一般化ヤコビアン（generalized Jacobian）」の計算を必要とします。しかし、実際の数値アルゴリズム（特にバンドル法やセミスムース・ニュートン法）では、厳密な一般化微分が利用できなくても、特定の「セミスムース性」を満たす写像（擬似勾配やセミスムース導関数）が利用可能であれば、収束性が保証されることが知られています。

本研究は、以下の 3 つの主要な問題クラスにおけるセミスムース性の役割と、それらの相互関係を統合的に分析することを目的としています。

1. 非滑らかな最適化問題: $\min \theta(x)$ s.t. $x \in U_{ad}$。バンドル法における擬似勾配（pseudogradient）の利用。
2. 非滑らかな方程式: $G(x) = 0$。無限次元設定を含むセミスムース・ニュートン法。
3. 非滑らかな包含関係: $0 \in F(x)$。集合値写像に対する「セミスムース*（semismooth*）」法。

特に、パラメータ依存の包含関係の解写像（例：$0 \in F(x, y)$の解$y=\sigma(x)$）と、それを内包する最適化問題（例：$\min \phi(x, \sigma(x))$）の結合において、解写像のセミスムース性をどのように保証し、数値アルゴリズムに適用できるかが核心的な課題です。

2. 手法と理論的枠組み

著者は、既存の概念を拡張・統合し、以下の新しい概念と理論的枠組みを導入・分析しています。

2.1 $\Psi$-セミスムース性（$\Psi$-semismoothness）

単一値写像 $F$ に対して、一般化ヤコビアンに代わる「セミスムース導関数」としての多価写像 $\Psi$ を定義します。

• 定義: $F$ が $\Psi$-セミスムースであるとは、$\Psi$ が局所有界であり、$x \to \bar{x}$ において $\sup_{A \in \Psi(x)} \|F(x) - F(\bar{x}) - A(x-\bar{x})\| / \|x-\bar{x}\| \to 0$ が成り立つことです。
• 特徴: この定義は、点ごとの性質だけでなく、領域全体での性質を重視します。これにより、バンドル法におけるオラクル（関数値と導関数の返却）として機能します。

2.2 集合値写像に対する拡張概念

• $\Gamma$-セミスムース（$\Gamma$-semismooth）**: 従来のセミスムース*（limiting coderivative を用いた定義）を、より一般的な多価写像 $\Gamma$ に対して拡張した概念です。これにより、正確な coderivative を計算できなくても、その部分集合 $\Gamma$ に対して性質が成り立てばよいという柔軟性が生まれます。
• SCD-セミスムース（SCD-semismooth）**: 「部分空間を含む導関数（Subspace Containing Derivative: SCD）」を用いた概念です。SCD 導関数は、集合値写像に対する B-ヤコビアン（Bouligand 微分）の一般化と見なせ、limiting coderivative の「骨格」として機能します。

2.3 主要な理論的関係性の解明

• G-セミスムース性との同値性: 単一値写像が $\Psi$-セミスムースであることと、Gowda による G-セミスムース性であることは同値であり、かつほとんど至る所（a.e.）で厳密微分可能であることを示しました。
• グラフ・リプシッツ写像（Graphically Lipschitzian mappings）: 座標変換後にリプシッツ連続な単一値写像のグラフと一致する集合値写像に対して、SCD-セミスムース* であることと、変換後の写像が G-セミスムースであることが同値であることを証明しました。
• 厳密プロト微分可能性（Strict proto-differentiability）: グラフ・リプシッツ写像が SCD-セミスムース* である場合、ほとんど至る所で厳密プロト微分可能となり、その SC 導関数が単一値集合（単一の部分空間）となることが示されました。

3. 主要な結果

3.1 解写像のセミスムース性

パラメータ付き包含関係 $0 \in F(x, y)$の解写像$\sigma(x)$ について、以下の結果を得ました。

• 一般化された解写像: 適切な資格条件（qualification condition）の下で、$F$ がセミスムース* であるならば、その解写像 $\sigma$ もセミスムース* であり、さらに連続な局所化（localization）や選択（selection）に対しては、$\Psi$-セミスムース性を持つことを証明しました。
• SCD 写像の場合の簡素化: $F$ が SCD 写像である場合、解写像 $\sigma$ のセミスムース性を保証するための条件が大幅に簡素化されます。具体的には、$F$ の SCD 導関数 $S^*F$ から直接、$\sigma$ のセミスムース導関数 $\Psi$ を構成できます（$\Psi(x) = \{-X_{L^*}^T \mid L^* \in S^*F(x, \sigma(x), 0)\}$）。

3.2 連鎖律（Chain Rule）の適用

セミスムース導関数は、一般化微分計算の包含関係（inclusion）ではなく、再びセミスムース導関数を生成する連鎖律を満たします。これにより、複雑な合成関数（例：$\theta(x) = \phi(x, \sigma(x))$）のセミスムース性を、構成要素の導関数から系統的に構築することが可能になりました。

3.3 数値アルゴリズムへの応用（ImP 手法の拡張）

Implicit Programming (ImP) 手法（解写像を陽に消去して reduced problem を解く手法）について、従来の「解写像が単一値かつリプシッツ連続である」という強い仮定を緩和しました。

• 解写像が単一値でない場合でも、連続な選択（continuous selection）が存在し、それが SCD-セミスムース* であるならば、バンドル法（BT アルゴリズムなど）に適用可能な「セミスムース導関数」を構成できることを示しました。
• これにより、従来の ImP 手法の適用範囲を超えた問題（非滑らかな 2 段階最適化問題や均衡制約付き数学計画問題など）に対して、数値的に安定した解法を提供できます。

4. 数値例

学術的な例（非滑らかな 2 段階最適化問題）を用いて、提案された理論の妥当性を検証しました。

• 下位レベルの問題が非滑らかな関数の最小化であり、その解写像が単一値でない場合でも、連続な選択 $\sigma(x)$ を選び、SCD 導関数に基づいてセミスムース導関数を構成しました。
• 構成されたオラクルを用いて BT アルゴリズムを適用した結果、初期点から収束し、局所最適解（C-定常点）に到達することが確認されました。これは、厳密な Clarke 部分勾配を計算できなくても、セミスムース導関数で代用できることを示しています。

5. 意義と貢献

1. 理論的統合: 最適化、方程式、包含関係という異なる分野で用いられてきた「セミスムース性」の概念を、$\Psi$-セミスムース性や $\Gamma$-SCD-セミスムース* といった統一的な枠組みで整理し、相互関係を明確にしました。
2. 数値計算への直接的な寄与: 厳密な一般化微分（Clarke 部分微分など）の計算が困難または不可能な場合でも、SCD 導関数などの代用導関数を用いることで、バンドル法やニュートン法の収束性を保証する理論的根拠を提供しました。
3. ImP 手法の拡張: 解写像が単一値でないような広範な問題クラス（MPEC や 2 段階最適化など）に対して、Implicit Programming 手法を適用可能にするための新しいアルゴリズム的アプローチを提案しました。
4. 実用性: 理論的な結果が、実際の数値実験（MATLAB による BT アルゴリズムの実装）で有効であることを示し、実用的な最適化ソルバーの開発への道筋をつけました。

結論として、本論文は非滑らかな数値解析において、セミスムース性の概念を単なる収束条件から、より構造的で計算可能な「導関数」の体系へと発展させ、複雑な非滑らか問題に対する効率的な数値解法の基盤を確立した重要な業績です。