論文要約：非線形最適化問題における変数集約（Variable Aggregation）

本論文は、線形および混合整数計画問題では広く研究されてきた「変数集約（Variable Aggregation）」を、**非線形計画問題（NLP）**のプリソル（事前処理）アルゴリズムとして体系化し、その効果を実証的に評価した研究です。著者らは、変数集約が非線形最適化の収束信頼性を向上させ、計算時間を短縮する可能性を示しましたが、一方でヘッセ行列の評価がボトルネックとなるリスクも指摘しています。

以下に、問題定義、手法、主要な貢献、結果、および意義について詳細にまとめます。

---

1. 問題定義と背景

非線形最適化問題において、等式制約 $y = f(x, \dots)$ によって定義される変数 $y$ を、他の制約式や目的関数に代入して変数を削減する手法を「変数集約」と呼びます。これにより、問題の次元が減少し、**縮小空間定式化（Reduced-space formulation）**が得られます。

• 現状の課題:
  • AMPL や Pyomo などのモデリング言語や、Knitro などのソルバーには変数集約の機能が存在するが、その実装基準や非線形問題への影響（収束性、計算時間、数値的安定性）は十分に研究・文書化されていない。
  • 既存の手法は、変数を最大限削減する「積極的（Aggressive）」なアプローチと、問題構造を維持する「保守的（Conservative）」なアプローチのいずれかに偏っている傾向がある。
  • 変数集約が必ずしも計算効率を向上させるわけではなく、場合によってはヘッセ行列の評価コストが増大したり、収束性が悪化したりする可能性がある。

2. 提案手法と方法論

著者らは、変数集約をグラフ理論（二部グラフ）を用いて形式化し、以下の 6 つの異なる集約戦略を提案・比較しました。

2.1 数学的基礎

• 暗黙関数定理の適用: 等式制約のヤコビアンが非特異である変数部分集合を特定し、それらを消去します。
• 厳密な条件: 変数と制約の対応関係が「厳密な下三角行列」の形（Lemma 1）をとる場合、反復解法なしに明示的に変数を消去できることが保証されます。
• グラフ理論: 変数と制約の関係を二部グラフとして表現し、最大マッチングやブロック三角化アルゴリズムを用いて、消去可能な変数集合を特定します。

2.2 提案された 6 つの集約戦略

1. 近似最大集約（Approximate Maximum Aggregation）:

   • GR (Greedy): 貪欲法を用いて、線形かつ未使用の変数を順次消去する。
   • LM (Linear Matching): 線形部分の二部グラフで最大マッチングを求め、その中で下三角部分行列を構成できる最大集合を特定する（NP 完全問題に対するヒューリスティック）。
   • 特徴: 最も多くの変数を削減するが、残りの制約の密度や非線形性を著しく増加させる可能性がある。

2. 構造保存型集約（Structure-Preserving Aggregation）:

   • LD1 (Linear Degree-1): 定数で固定される変数（$y=c$）のみを再帰的に消去。
   • ECD2 (Equal Coefficient Degree-2): 係数の絶対値が等しい 2 変数線形制約（$y = x + c$）のみを使用。ヤコビ行列の値を維持する。
   • LD2 (Linear Degree-2): 2 変数の線形制約（$y = ax + b$）のみを使用。線形性を維持する。
   • D2 (Degree-2): 最大 2 変数の制約（線形・非線形問わず）を使用。
   • 特徴: 残る制約の密度や変数の数を急激に増やさず、問題の構造を維持する。

3. 主要な貢献

1. 非線形最適化における変数集約の形式化: 明示的な集約が有効であるための十分条件（厳密な下三角性）を提示し、チェック可能なアルゴリズムを構築した。
2. 新規アルゴリズムの開発: 最大変数削減を目指す近似アルゴリズム（LM 法など）を提案し、その理論的上下界を導出した。
3. 包括的な実証評価: 4 つの異なる非線形最適化ベンチマーク問題（蒸留塔、移動床反応器、パイプライン網、AC 最適電力潮流）を用い、121 種類のパラメータ設定で収束信頼性を評価した。
4. トレードオフの明確化: 「変数の削減による収束信頼性の向上」と「ヘッセ行列評価コストの増大による計算時間の悪化」というトレードオフを実データで示した。

4. 実験結果

4 つのテストケース（DIST, MB, OPF, PIPE）に対して IPOPT ソルバーを用いて評価を行いました。

4.1 構造的特性

• 変数削減率: 近似最大集約（LM, GR）はモデルの変数の 70〜90% を削減しましたが、構造保存型（LD1, D2 など）は 60% 未満に留まりました。
• 密度と非線形性: 近似最大集約は、残る制約あたりの非ゼロ要素数（密度）と非線形項の数を大幅に増加させました。一方、構造保存型は密度をほぼ一定に保ちました。

4.2 計算時間（Runtime）

• KKT 行列の分解: 変数が減少するため、KKT 行列の分解時間は短縮される傾向にあります。
• ヘッセ行列評価: 近似最大集約では、消去された変数の式が複雑に代入されるため、ヘッセ行列の評価コストが劇的に増加し、計算時間のボトルネックとなりました（例：パイプライン問題では全計算時間の 75% を占める）。
• 総合解時間: 問題によって結果は異なります。
  • 蒸留塔やパイプライン問題では、適切な集約により解時間が短縮されました。
  • 電力潮流（OPF）問題では、不等式制約の増加や反復回数の増加により、集約により解時間が悪化しました。

4.3 収束信頼性（Convergence Reliability）

• 全体的な傾向: 変数集約を適用したモデルは、元のモデルよりも収束信頼性が向上しました（パラメータスイープにおいて、収束するインスタンスの割合が増加）。
• ベスト戦略: 変数を多く削減する「D2（Degree-2）」、「GR（Greedy）」、「LM（Linear Matching）」の 3 つが最も高い収束率（元のモデルより 13〜15% 向上）を示しました。
• メカニズム: 集約により、ソルバーの反復経路が元の問題の可行領域に近づくようになり、KKT 行列の条件数が改善されたことが推測されます。

5. 結論と意義

• 変数集約の有用性: 非線形最適化において、変数集約は収束信頼性を高める強力なプリソル手法であることが実証されました。
• 戦略の選択:
  • 変数を極力削減する「近似最大アプローチ」は収束性を向上させますが、ヘッセ行列評価のコスト増大というリスクがあります。
  • 構造を維持する「構造保存アプローチ」は計算コストの増大を防ぎますが、収束性の向上幅は限定的です。
  • 推奨: 著者らは、構造維持と変数削減のバランスが取れる**「Degree-2 集約（D2）」**を、一般的なプリソルオプションとして推奨しています。
• 今後の展望:
  • ソルバーのグローバル収束手法（線探索やトラストリージョン）と集約戦略の相互作用に関する理論的解析が必要。
  • 非線形ソルバーの収束信頼性を 100% 保証できないような困難な問題セットの構築と、そのためのプリソル手法の開発が期待されます。

本論文は、非線形最適化ソルバーのプリソル段階における変数集約の役割を初めて体系的に解明し、実用的なガイドラインを提供した点で重要な貢献を果たしています。