技術的概要：リスク回避とスパース性制御のための射影不要な関数制約最適化

1. 問題定式化

本論文は、以下の関数制約最適化問題を取り扱います：
$$\begin{aligned} f^* := \min_{x} \quad & f(x) \\ \text{s.t.} \quad & h_i(x) \le 0, \quad i = 1, \dots, m, \\ & x \in X, \end{aligned} \tag{1.1}$$
ここで、$X \subseteq \mathbb{R}^n$ は空でないコンパクトな凸集合です。関数 $h_i$ は真（proper）、下半連続、かつ凸です。目的関数 $f$ は 2 つの領域で研究されます：

1. 凸設定：$f$ は凸（非滑らかである可能性あり）。
2. 非凸設定：$f$ はリプシッツ連続な勾配を持つ微分可能関数です。

この枠組みは、リスク意識基準とスパース性制約が同時に現れる応用をモデル化します。例えば、ポートフォリオ最適化（資産制限付きの未達成リスク最小化）や強度変調放射線療法（IMRT）計画（過剰投与/過少投与の最小化とスパースなビーム選択）などが該当します。

課題：標準的な射影ベースの手法（ペナルティ法、拡張ラグランジュ法、双対法など）は、$X$ への反復的な射影を必要とし、これは計算コストが高く、解に内在するスパース構造を破壊する可能性があります。既存の射影不要な手法は、単純な制約のみを処理するか、または最適双対ラグランジュ乗数の大きさに依存する複雑さの上限を持ちます。この乗数の大きさは任意に大きくなり得ます。

2. 手法

著者らは、$X$ 上の線形最小化オラクル（LMO）への呼び出しで射影を置き換える射影不要なアルゴリズムを提案します。中核的な革新は、鞍点部分問題に対する条件付き勾配オラクル（CGO）を組み合わせたレベルセット外ループです。

2.1 凸設定：レベル条件付き勾配（LCG）

凸の場合、問題は値関数 $\phi(l) = \min_{x \in X} \max \{ f(x) - l, h_1(x), \dots, h_m(x) \}$ の根を見つけることに帰着されます。

• 外ループ：近似ニュートン法がレベル推定値 $l_k$ を更新します。正確な勾配の代わりに、内側オラクルから導出された下界 $L_k$ と近似部分勾配を使用します。
• 内ループ（CGO）：特殊な条件付き勾配オラクルが、鞍点部分問題 $\min_{x \in X} \max_{z \in Z} [f(x) - l_k] + \langle h(x), z \rangle$ を解きます。
  • オラクルは、主変数の反復点 $x_k$ と証明区間 $[L_k, U_k]$ を返します。
  • 重要なのは、双対集合 $Z$ が標準単体であるため、この手法が最適ラグランジュ乗数の大きさに依存しないことです。
  • ギャップ $U_k - L_k$ が停止則とレベルの更新を駆動します。
• 非滑らか拡張：構造化された非滑らか関数（最大構造）に対しては、CGO 枠組み内でネステロフ平滑化を採用し、同じ複雑さの次数を維持します。

2.2 非凸設定：不正確な近接点 LCG（IPP-LCG）

非凸な $f$ に対しては、近接点正則化を介して問題を一連の凸部分問題に還元します：
$$\min_{x \in X} f(x) + L_f \|x - x_{j-1}\|^2 \quad \text{s.t.} \quad h_i(x) \le 0.$$

• メカニズム：凸設定からの LCG 法を、各近接部分問題の不正確なソルバーとして使用します。
• 出力：アルゴリズムは、一連の目的関数の減少を最小化する反復点を選択します。
• 保証：スレーター条件と滑らかさの仮定の下で、この手法は $(\epsilon, \epsilon)$-近 KKT 点を計算します。

3. 主要な貢献

1. 凸関数制約に対する LCG：

   • レベル条件付き勾配（LCG）法を提案します。
   • $\epsilon$-最適かつ $\epsilon$-実行可能解を得るための反復複雑さを $O(\epsilon^{-2} \log(\epsilon^{-1}))$ で達成します。
   • 意義：この複雑さの上限は、最適双対ラグランジュ乗数の大きさに依存しません。これは、以前の射影不要な研究（例：Lan ら、2021）における制限でした。

2. 滑らかな非凸目的関数に対する IPP-LCG：

   • 不正確な近接点 LCG（IPP-LCG）法を開発します。
   • LCG を用いて一連の凸部分問題を解き、すべての内側解を射影不要に保ちます。
   • $(\epsilon, \epsilon)$-近 KKT 点を計算するための反復複雑さを $O(\epsilon^{-3} \log(\epsilon^{-1}))$ で達成します。

3. 証明メカニズム：

   • CGO は、レベルセットの更新と停止則を駆動する明示的な下界と上界の証明（$L_k, U_k$）を返します。これにより、正確な鞍点解を必要としません。

4. 数値結果

著者らは、2 つの応用分野で手法を評価しました：

4.1 ポートフォリオ選択

• 設定：ステップリスク目的関数（CVaR による凸化または平滑化された非凸代理関数）とスパース性制約（資産数の制限）を備えたリスク回避型ポートフォリオ最適化。
• ベースライン：固定された 5 秒間のウォールクロック予算の下で、CoexDurCG（射影不要）、FISTA、PGD、および各種スパース指向ヒューリスティック（Greedy+Refit、IRL1 など）と比較しました。
• 知見：
  • 凸モデル：LCG は 6 つのデータセットのうち 5 つで、スパース性目標を厳密に満たしながら、最良の実行可能アウト-of-sample ステップリスクを達成しました。
  • 非凸モデル：IPP-LCG は 6 つのデータセットのうち 4 つで、最良の実行可能ステップリスクを達成しました。
  • トレードオフ：これらの手法は精度とスパース性のトレードオフを成功裏に navigated し、同じ時間予算内で実行可能なリスク削減において、射影ベースのベースラインを上回る場合が多かったです。

4.2 強度変調放射線療法（IMRT）

• 設定：グループスパース性制約（ビーム角度の数を制限）と臨床的な線量体積制約を備えた治療計画。
• 知見：
  • 凸：LCG は、類似の実行時間で CoexDurCG に対して制約満足度を向上させました。
  • 非凸：「ウォームスタート」戦略がテストされました。これは、スパースな凸 LCG 計画で非凸 IPP-LCG 微細化を初期化するものです。
  • 結果：ウォームスタートされた IPP-LCG は、コールドスタートの IPP-LCG と比較して、最大制約違反を大幅に削減しました（0.8438 から 0.1675 へ）。同時に、臨床的にスパースな治療構造（7 つの角度、20 のアパーチャ）を維持しました。コールドスタートの非凸最適化は、深刻な標的過少投与により臨床的に実行可能な計画を見つけることに失敗しました。

5. 意義と主張

本論文は、双対乗数の大きさに依存することなく、一般的な関数制約への射影不要手法の拡張を主な貢献としています。レベルセット外ループとコンパクトな鞍点オラクルを組み合わせることで、著者らは条件付き勾配法のスパース表現の利点（極点の凸結合としての反復点）を維持しつつ、複雑な非線形制約を処理しています。

数値結果は以下を示唆しています：

1. LCG は凸なリスク - スパース性問題に対して効果的であり、既存の射影不要および射影ベースの手法と競合するか、それ以上の性能を提供します。
2. IPP-LCG は、ランダムな開始点からの単独ソルバーとしてではなく、高品質なスパースな凸解で初期化された場合の微細化メカニズムとして最も効果的です。

著者らは、これらの手法が、射影が高価であり、スパースな構造表現が望ましい大規模な応用に特に適していると結論付けています。今後の研究の方向性としては、軽量な非凸スキームの開発、スレーター型仮定の緩和、および暗黙的な実行可能集合に対するアプリケーション固有の LMO の設計が含まれます。