NAG最適化コーナー: 問題に適したソルバーを選ぶ

この記事はNAG最適化コーナー シリーズの一部です。

本記事は、与えられた問題に対して適切な最適化ツールを選択するためのガイダンスを目的としています。また不適切な選択をしてしまった場合に、どのような結果があり得るのかを示したいと思います。

正しい最適化ツールを選択することは非常に難しく、そのプロセスが曖昧なものであることをNAGは認識しています。NAGのカスタマーサービスにいただくお問い合わせの中にも、これに関するお問い合わせが良くあります。このようなお問い合わせは多くの場合「ソルバーが失敗するのはなぜか」というご質問から始まり、よくよく調べてみると、間違ったソルバーが選択されているか、もしくはモデル自体の（大幅な）改善が望まれる状況であることがわかります。この記事は前者の場合に関するものです。

この記事では、正しいソルバーを選択することの重要性を示す2つの例を紹介し、重要な注意事項を述べて終わります。

異なる問題と異なるソルバー

野球帽とは異なり、最適化問題の解決に関しては、1つのサイズですべてに適用できるわけではありません。 実際、常に可能な限りぴったりのものを試しみる事をお勧めします。

たとえば、ぴったりのLPソルバーの代わりに、一般的な非線形計画法（NLP）ソルバーを使用して線形計画法（LP）を解いた場合、問題の線形性を活用するLPソルバーよりも、高価で堅牢性が低くなります。

以下では、最適化問題の根底にある構造を理解し、それを活用できるソルバーとマッチングさせることがなぜ重要なのかを説明します。

まず、最適化問題を構成する様々な部分を簡単に紹介します。問題は、変数、関数の目的、および制約から構成されます。 異なるタイプの変数、目的、制約は異なる問題クラスを定義します。 NAG's Optimization E04 Chapter Introduction では、最適化問題の様々なクラスと、使用するための推奨ソルバーについて包括的に説明しています。

コストのかかるキャリブレーション

キャリブレーション（データ・フィッティング、回帰）の問題は、通常、線形（LSQ）または非線形（NLN-LSQ）の最小二乗法で記述され、残差の二乗和を最小化することが課題となります。残差関数 $r_i\left(x\right)$ はモデルの予測とデータの間の誤差を表し、目的関数は次のように示されます。

$$f\left(x\right)=\frac{1}{2}\sum _{i=1}^m{r}_i^2\left(x\right).$$

最小二乗最適化の詳細については、最適化に関する NAGのドキュメント を参照してください。

以下に示す検証では、39の制約のないNLN-LSQ問題を解き、特化したNLN-LSQソルバーと汎用のNLPソルバーを比較しました。 中央値では、特化されたNLN-LSQソルバーは汎用NLPソルバーの1.8倍のスピードアップを実現しており、20%の問題は少なくとも5倍のスピードで解かれています。 最後の一握りの問題（32-39）で明らかになったように、出発点が他の方法よりも特定の方法を好むなどの要因により、NLPソルバーが特化型ソルバーよりも優れた結果を出すこともありますが、これは、複数のソルバーを試すことの重要性を示しています。

図1. CUTEstのNLN-LSQ問題39問を対象としたベンチマーク
NLN-LSQソルバーとNLPソルバーの性能を比較
縦棒の高さは、スピードアップを示している

NLN-LSQソルバーの最も重要な高速化要因は、ヘシアンをどのように近似するかにあります。より詳細には、問題は次のように定義されます。 $$\begin{array}{llllllll}\hfill \underset{x\in {ℝ}^n}{min}& f\left(x\right)=\frac{1}{2}\sum _{i=1}^m{r}_i{\left(x\right)}^2=\frac{1}{2}r{\left(x\right)}^{T}r\left(x\right)& \hfill & \text{nonlinear least squares objective}& \hfill & & \hfill & \end{array}$$

そして、次のような勾配（第1導関数）とヘシアン（第2導関数）を持ちます。 $$\begin{array}{llll}\hfill \nabla f\left(x\right)& =J\left(x\right)r\left(x\right)& \hfill & \\ \hfill {\nabla }^{2}f\left(x\right)& =J{\left(x\right)}^{T}J\left(x\right)+\sum _{i=1}^m{r}_i\left(x\right){\nabla }^2{r}_i\left(x\right),& \hfill & \end{array}$$

ここで、 $J\left(x\right)$ は残差のヤコビアンです。ヘシアンは、転置されたヤコビアン自体（ガウス・ニュートン行列としても知られている）と、m個の残差ヘシアンの和の行列-行列積であることがわかります。問題がうまくフィットする（残差 $r_i\left(x\right)$ が小さい）場合、解に近いところでは、残差ヘシアンの和を含む後半部分、 ${\sum }_{i=1}^m{r}_i\left(x\right){\nabla }^2{r}_i\left(x\right)$ は無視できると考えられ、したがって省略されます。この最後の事実は非常に重要です（m個の個別のヘシアンの評価が非常に高価であるので）

専用LSQが一般的に高速なのは、これらの重要な事実を認識して利用しているためで、残差の1次導関数のみを用いて2次導関数をうまく近似することができます。 一方、一般的なNLPソルバーは、その利点を生かすことができません。

トレードオフ：QPを解くためにNLPを使う

汎用のNLPソルバーは、多種多様な問題クラスを解くことができますが、問題の構造を利用できないというトレードオフがあります。 そのため、これらのソルバーは、特殊なソルバーが利用できない場合にのみ使用されるべきです。 以下では、50個の凸型二次計画問題を解き、 凸型二次計画に特化したソルバー qpconvex2_sparse_solve（e04nq）と、 一般的なNLPソルバー nlp2_sparse_solve（e04vh）を使用した場合の計算コストを比較し、このようなトレードオフを説明します。 図2が示す通り QPソルバーe04nq は NLPソルバーe04vh と比べて中央値で2.3倍、28%の問題では5倍以上の高速化を実現しています。

図2. 50個の凸型QP問題のベンチマーク
QPソルバーとNLPソルバーの性能を比較
縦棒の高さは スピードアップを示している

最大のスピードアップ要因は、特化したソルバーである e04nq がQP構造に合わせて調整されており、ヘシアン（二階微分）がすべてのxに対して一定であるという事実を利用していることです。一方、一般的なソルバーである e04vh は二階微分を要求しないため、同じ情報にアクセスすることはできません。一般的に、二階微分を使用できるNLPソルバーは、反復ごとの計算コストが高くなります。（例えば、ヘシアンの因数分解や近似値の部分的な更新を、反復ごとに行う必要があります）

覚えておくと役立つ事

この記事では、基礎的な構造を持つ問題を解決するために汎用の最適化ソルバーを使用することのトレードオフを示す2つの例を紹介しました。それらの結果から、特化したソルバーの方が汎用ソルバーよりも好ましいことがわかりました。

• 適切な最適化ソルバーを選択することは大切です。問題の基本的な構造を理解するのに時間をかけ、要件に最も適したソルバーを選択することは有用です。 NAGライブラリが最適化ソルバーの豊富な選択肢を提供しているのはこのためです。
• 特化したソルバーは、たパフォーマンス（計算時間）だけでなく、ロバスト性や計算精度に関しても、より優れています。
• 適切なソルバーを選択することは、必ずしも容易なことではありませんが、NAGでは、お客様のお手伝いをさせていただく事が可能です。フレンドリーなサポートデスクや、適切な最適化ツールを選択するために簡単に探索できる決定木図などの多くのオンラインリソースをご用意しております。
• 問題に適したソルバーが2つ以上ある場合は、実験を行うことで最適なソルバーを選ぶことも可能です。このテーマについては、次回の記事でご紹介します。

次回のブログ記事では、密な問題と疎な問題を扱う予定です。

---

本記事は以下の原文（英語）を翻訳したものです。
https://www.nag.com/blog/optcorner-right-tool-job-matching-problems-solvers

さらに詳しくお知りになりたい場合はお気軽に お問い合わせ 下さい。