An augmented Lagrangian algorithm for constrained nonlinear least-squares

巨大で、ぐにゃぐにゃと揺れるテントを設営するのに最適な場所を見つけようとしているところを想像してみてください。あなたはテントを特定の形（「最小二乗法」の部分、つまり、理想的な形とテントの支柱との間の隙間を最小限にしたいという意味）に合わせたいと考えていますが、厳しいルールもあります。テントは囲いのある庭の中にいなければならず、特定の支柱は特定の木や岩に触れていなければなりません（これらが「制約」です）。

これは、ピエール・ボリー、ファビアン・バスティン、そしてステファン・デラシェリが取り組んだ問題そのものです。彼らは、このトリッキーな「制約付き非線形最小二乗法」のパズルを解くために、TRAULLS（Trust Region Augmented nonLinear Least-squares Solver）と呼ばれる新しいアルゴリズムを構築しました。

彼らの手法がどのように機能するかを、イメージしやすい物語として分解して説明します。

二部構成の戦略：ペナルティボックスとフェンス

従来の多くの手法は、形の計算とフェンスのルールを同時に解決しようとします。それは、まるで綱渡りをしながらジャグリングをしようとするようなものです。著者たちのアプローチはよりスマートです。彼らは仕事を二つの層に分けました。

1. フェンス（線形制約）： 庭の境界や木に関するルールは「線形」です。これらは硬くて変えられないフェンスのようなものです。アルゴリズムは、壁に沿って決してはみ出すことなく滑る方法を知っているロボットのように、これらを直接処理します。
2. ペナルティボックス（非線形制約）： トリッキーなのは、テントの「ぐにゃぐにゃした」形状です。もしテントが理想的な形と一致しない場合、アルゴリズムはそれを単に無視するのではなく、テントを「ペナルティボックス」に入れます。テントが正しい形でないたびに、アルゴリズムはスコアに巨大な「罰金」を加算します。これは**拡張ラグランジュ関数（Augmented Lagrangian）**と呼ばれます。

アルゴリズムは「ホット＆コールド（熱いか冷たいか）」のゲームをプレイします。フェンスの中で最適な場所を見つけようとしつつ、罰金を最小限に抑えようとします。もしテントがまだぐにゃぐにゃしている（罰金が高すぎる）場合、アルゴリズムは次のラウンドに向けて罰金のサイズを大きくし、テントを正しい形へと強制的に収束させます。

「ステップ」のダンス：コーシーと部分空間

アルゴリズムがより良い場所へと一歩踏み出すと決めたとき、それは単に推測するわけではありません。二段階のダンスを踏みます。

• コーシー・ステップ（Cauchy Step）： まず、素早く慎重に下り坂へのステップを踏みます。これは、傾斜を見て、最も急だと感じられる方向に安全な一歩を踏み出すようなものです。これにより、アルゴリズムが立ち往生したり、逆方向に進んだりしないことが保証されます。
• 部分空間の最小化（Subspace Minimization）： その安全なステップの後、さらに深く探索します。現在触れているルールによって定義された特定の「トンネル」（部分空間）を探求します。彼らは**射影共役勾配法（Projected Conjugate Gradient）**という特別なツールを使用して、そのトンネル内での最良の地点へとズームインします。

秘伝のソース：構造化されたヘッセ行列

ここからが、この論文の非常に巧妙な部分です。どちらの方向が「下」なのかを知るために、アルゴリズムは地形の地図、すなわち**ヘッセ行列（Hessian）**を必要とします。

• 古いやり方： 一部の手法は、地面が平らであると仮定した大まかな地図（ガウス・ニュートン法）を使用します。これは速いですが、地面がデコボコしている場合には間違ったものになります。
• 「フル」なやり方： 他の手法は、デコボコした地面全体を完璧に描き出そうとします。これは正確ですが、変数が多すぎるとメモリや時間を使い果たしてコンピュータをクラッシュさせてしまいます。

著者たちの革新は、**構造化準ニュートン（Structured Quasi-Newton）**更新です。想像してみてください、あなたは地面のスケッチを持っています。毎回全体を描き直すのではなく、特殊なルール（SR1更新）を用いて、変化した部分だけを更新します。これは、問題特有の「二乗和」の性質を尊重したものです。

• 彼らは「ハイブリッド」戦略をテストしました。地面が平らに見える場合は、速いスケッチを使用します。地面がデコボコしている場合は、詳細な更新に切り替えます。
• 結果： 79種類の異なる問題（2から1000の変数）を用いたテストにおいて、このハイブリッドSR1アプローチは最も堅牢でした。それは単に動作しただけでなく、標準的なスケッチよりも「デコボコした」問題をうまく扱い、他の複雑な手法よりも信頼性が高いことが示されました。

彼らが発見したこと（そして発見できなかったこと）

著者たちは、自らのアルゴリズムを（M4プロセッサを搭載したMac mini上で）実行し、有名な2つのソルバー、IPOPTおよびPercivalと比較しました。

• スピード： 純粋な時間の面では、彼らの新しいソルバー（TRAULLS）はIPOPTに次いで僅差の2位でした。簡単な問題ではIPOPTの方がわずかに速かったのですが、問題が難しくなるにつれて、その差は縮まりました。
• 効率性： 残差評価（テントの形をチェックすること）の節約においては、IPOPTがチャンピオンでした。これは、IPOPTがすべてのステップで正確で重厚な数学を使用するためです。しかし、TRAULLSはPercival（別の拡張ラグランジュ法ソルバー）よりもはるかに優れており、多くの指標においてIPOPTに匹敵する性能を示しました。
• 勝者： この論文は、この特定のタイプの問題に対しては、ハイブリッドSR1更新を使用することが全体として最良の戦略であることを示唆しています。それは、スピードと正確さの完璧なバランスを実現しています。

彼らが否定したもの

論文では、大規模な問題に対して「フル」のヘッセ行列（完璧な地図）を使用することに対して明確に反対しています。彼らは、完全な二次項を計算するには時間とストレージが取られすぎ、変数の多い問題においては実用的ではないことを示しました。また、単純な「ガウス・ニュートン」のスケッチ（デコボコを無視するもの）は、テントが理想的な形から遠い場合には、それ単体では不十分であることも示しました。

彼らの自信の根拠

著者たちは、自らの結果に非常に自信を持っていますが、言葉遣いは慎重です。

• 彼らは、標準的な仮定の下で、自分たちの手法が最終的に解を見つけること（大域的収束）を数学的に証明しました。
• 彼らは、79の具体的な問題インスタンスを用いた数値実験を通じて、パフォーマンスを測定しました。
• 彼らは、自分たちのメソッドが宇宙で最も速いソルバーであると主張しているわけではありません。変数の数が膨大な（極めて大規模な）問題においては、構造化された地図であっても密な行列を保存する必要があるため、限界に突き当たることを認めています。そのような巨大なケースには「限定メモリ（limited-memory）」版が必要になるだろうと示唆していますが、彼らはまだそれを構築していません。

要約すると、TRAULLSは、ルールを伴う複雑なフィッティング問題を解決するための、新しく巧妙な方法です。困難なルールを扱うために「ペナルティボックス」を使用し、地形をナビゲートするために「スマートなスケッチ」を使用しており、シミュレーションにおいて、これらの数学的パズルを解くための強力で信頼できる有力候補であることを証明しています。