NAG数理最適化ソルバー選択ガイド

NAGライブラリのE04チャプターには、様々な最適化問題を解くための高性能なソルバーが用意されています。このガイドは、問題の特性に基づいて最適なNAG数理最適化ソルバーを選択するための手引きです。

ソルバー選択ガイド

問題の種類と制約条件による振り分け

以下の表は、目的関数の種類と制約条件の組み合わせに基づいて、適切なソルバーの種類や選択方法を示しています。表中の「Tree」は、より詳細なソルバー選択のためのフローチャートへの参照を示し、「e04***」は特定のソルバールーチンの詳細ドキュメント（関数マニュアル）へのリンクを表しています。

この表を使用することで、問題の特性に応じた適切なソルバーの種類（LP、QP、NLPなど）を特定できます。さらに、「Tree」や特定のルーチンを参照することで、問題に最適な具体的なソルバーを絞り込むことができます。

制約条件  目的関数	目的関数なし	線形	二次	非線形	損失関数（例：二乗和）
無制約			QP (Tree 2)	NLP (Tree 3)	DF (Tree 4)
単純な変数の範囲	LP (Tree 1)	LP (Tree 1)	QP (Tree 2)	NLP (Tree 3)	DF (Tree 4)
線形制約	LP (Tree 1)	LP (Tree 1)	QP (Tree 2)	NLP (Tree 3)	DF (Tree 4)
二次制約	QCQP (Tree 2)	QCQP (Tree 2)	QCQP (Tree 2)	NLP (Tree 3)	DF (Tree 4)
非線形制約	NLP (Tree 3)	NLP (Tree 3)	NLP (Tree 3)	NLP (Tree 3)	DF (Tree 4)
錐制約	SOCP (e04ptf)	SOCP (e04ptf)
行列不等式制約	SDP (e04svf)	SDP (e04svf)	SDP (e04svf)

フローチャートによるソルバー選択

より詳細なソルバー選択のために、以下のフローチャートを参考にしてください。

Tree 1: 線形計画問題 (LP)

1. 問題は疎（スパース）または大規模ですか？
   • はい → 推奨ソルバー: e04mtf, e04nqf, e04nkf/e04nka
   • いいえ → 推奨ソルバー: e04mff/e04mfa, e04ncf/e04nca

Tree 2: 二次計画問題 (QP) および二次制約付き二次計画問題 (QCQP)

1. 二次制約がありますか？

   • はい → 2へ
   • いいえ → 3へ

2. 問題は凸ですか？

   • はい → 推奨ソルバー: e04ptf, e04stf
   • いいえ → 推奨ソルバー: e04stf, e04srf

3. 問題は疎（スパース）または大規模ですか？

   • はい → 4へ
   • いいえ → 5へ

4. 問題は凸ですか？

   • はい → 推奨ソルバー: e04nqf, e04ptf, e04stf, e04nkf/e04nka
   • いいえ → 推奨ソルバー: e04stf, e04srf

5. 問題は凸ですか？

   • はい → 推奨ソルバー: e04ncf/e04nca
   • いいえ → 推奨ソルバー: e04nff/e04nfa

Tree 3: 非線形計画問題 (NLP)

1. 問題は疎（スパース）または大規模ですか？
   • はい → 2へ
   • いいえ → 5へ
2. 無制約または単純な変数の範囲のみの制約ですか？
   • はい → 3へ
   • いいえ → 4へ
3. 一階微分（勾配）は利用可能ですか？
   • はい → 推奨ソルバー: e04kff, e04stf, e04srf
   • いいえ → 推奨ソルバー: e04kff, e04srf
4. 一階微分（勾配）は利用可能ですか？
   • はい → 二階微分（ヘッシアン）は利用可能ですか？
     • はい → 推奨ソルバー: e04stf
     • いいえ → 推奨ソルバー: e04srf, e04stf
   • いいえ → 推奨ソルバー: e04srf
5. 線形または非線形の制約がありますか？
   • はい → 推奨ソルバー: e04uca, e04ufa, e04wdf
   • いいえ → 6へ
6. 変数は1つだけですか？
   • はい → 一階微分（勾配）は利用可能ですか？
     • はい → 推奨ソルバー: e04bbf
     • いいえ → 推奨ソルバー: e04abf
   • いいえ → 7へ
7. 目的関数に多くの不連続性がありますか？
   • はい → 推奨ソルバー: e04cbf または e05saf
   • いいえ → 8へ
8. 一階微分（勾配）は利用可能ですか？
   • はい → 二階微分（ヘッシアン）は利用可能ですか？
     • はい → 経験豊富なユーザーですか？
       • はい → 推奨ソルバー: e04lbf
       • いいえ → 推奨ソルバー: e04lyf
     • いいえ → 関数評価回数を少なくしたいですか？
       • はい → 推奨ソルバー: e04uca, e04ufa, e04wdf
       • いいえ → 経験豊富なユーザーですか？
         • はい → 推奨ソルバー: e04kdf
         • いいえ → 推奨ソルバー: e04kzf
   • いいえ → 関数評価に時間がかかる、またはノイズがありますか？
     • はい → 推奨ソルバー: e04jdf, e04jef
     • いいえ → 経験豊富なユーザーですか？
       • はい → 推奨ソルバー: e04uca, e04ufa, e04wdf
       • いいえ → 推奨ソルバー: e04jyf

Tree 4: データフィッティング（DF）および最小二乗法（LSQ）

1. 損失関数が二乗和以外、または正則化が必要ですか？
   • はい → 推奨ソルバー: e04gnf
   • いいえ → 2へ
2. 目的関数が線形関数の二乗和で、非線形制約がありませんか？
   • はい → 線形制約がありますか？
     • はい → 推奨ソルバー: e04ncf/e04nca
     • いいえ → 単純な変数の範囲がありますか？
       • はい → 推奨ソルバー: e04pcf, e04ncf/e04nca
       • いいえ → 推奨ソルバー: F04、F07、F08チャプター、または e04pcf, e04ncf/e04nca
   • いいえ → 3へ
3. 線形または非線形の制約がありますか？
   • はい → 推奨ソルバー: e04usf/e04usa
   • いいえ → 4へ
4. 単純な変数の範囲がありますか？
   • はい → 一階微分（ヤコビアン）は利用可能ですか？
     • はい → 推奨ソルバー: e04ggf, e04usf/e04usa
     • いいえ → 推奨ソルバー: e04fff, e04fgf
   • いいえ → 一階微分（ヤコビアン）は利用可能ですか？
     • はい → 二階微分（ヘッシアン）は利用可能ですか？
       • はい → 経験豊富なユーザーですか？
         • はい → 推奨ソルバー: e04ggf, e04hef
         • いいえ → 推奨ソルバー: e04ggf, e04hyf
       • いいえ → 関数評価回数を少なくしたいですか？
         • はい → 推奨ソルバー: e04ggf
         • いいえ → 経験豊富なユーザーですか？
           • はい → 推奨ソルバー: e04gdf, e04ggf
           • いいえ → 推奨ソルバー: e04ggf, e04gzf
     • いいえ → 推奨ソルバー: e04fff, e04fgf, e04fcf

ソルバーの詳細説明

線形計画問題 (LP)

• e04mtf: スパースな大規模問題向けの内点法ソルバー。高速で安定した解法を提供します。
• e04nqf / e04nkf/e04nka: スパースな大規模問題向けのアクティブセット法/単体法ソルバー。e04nqfは最新のアルゴリズムを使用しており、通常はe04nkf/e04nkaより高速です。
• e04mff/e04mfa: 密な小規模問題向けのアクティブセット法/単体法ソルバー。
• e04ncf/e04nca: 密な小規模問題向けのアクティブセット法ソルバー。二次計画問題も解くことができます。

二次計画問題 (QP) および二次制約付き二次計画問題 (QCQP)

• e04ptf: 凸なQCQPやSOCP問題向けの内点法ソルバー。大規模問題に適しています。
• e04stf: 非凸な問題にも対応可能な内点法ソルバー。大規模な非線形計画問題にも使用できます。
• e04srf: 非凸な問題向けのアクティブセット法ソルバー。中規模から大規模の問題に適しています。
• e04nqf / e04nkf/e04nka: スパースな凸QP問題向けのアクティブセット法ソルバー。
• e04ncf/e04nca: 密な凸QP問題向けのアクティブセット法ソルバー。
• e04nff/e04nfa: 密な非凸QP問題向けのアクティブセット法ソルバー。

非線形計画問題 (NLP)

• e04stf: スパースな大規模問題向けの内点法ソルバー。一階および二階微分が利用可能な場合に最も効果的です。
• e04srf: スパースな大規模問題向けのアクティブセット法ソルバー。一階微分が利用可能な場合に推奨されます。
• e04kff: 単純な変数の範囲のみの制約を持つ問題向けの一階微分を用いたアクティブセット法ソルバー。
• e04uca, e04ufa, e04wdf: 密な問題向けのアクティブセット法ソルバー。一階微分が利用可能な場合に推奨されます。
• e04jdf, e04jef: 微分不要なソルバー。関数評価が高価またはノイズがある場合に適しています。
• e04cbf, e05saf: 目的関数に多くの不連続性がある場合に適したソルバー。

データフィッティング（DF）および最小二乗法（LSQ）

• e04gnf: 任意の損失関数や正則化を含むデータフィッティング問題向けのソルバー。機械学習モデルの学習などに適しています。

• e04ncf/e04nca, e04pcf: 線形最小二乗問題で線形制約や単純な変数の範囲がある場合に適したソルバー。

• e04usf/e04usa: 線形または非線形の制約を持つ非線形最小二乗問題向けのソルバー。柔軟性が高く、様々な問題に対応できます。

• e04ggf: 単純な変数の範囲があり、一階微分が利用可能な場合に推奨されるソルバー。効率的な信頼領域法を使用しています。

• e04fff, e04fgf: 単純な変数の範囲があり、一階微分が利用できない場合に適した微分不要のソルバー。

• e04fcf: 無制約の非線形最小二乗問題向けの微分不要ソルバー。

おわりに

NAGの数理最適化ソルバーは、幅広い最適化問題に対応する強力なツールです。このガイドを通じて、あなたの問題に最適なソルバーを選択し、効率的に解を得るための手助けとなれば幸いです。

問題の特性を十分に理解し、適切なソルバーを選択することで、より効率的かつ正確な結果を得ることができます。また、必要に応じて複数のソルバーを試してみることも有効な戦略です。

最適化は時として複雑で難しい課題となりますが、NAGのソルバーとこのガイドを活用することで、より効果的に問題に取り組むことができるでしょう。さらなる質問や支援が必要な場合は、NAGのサポートリソースを活用してください。

数理最適化の世界での成功を心よりお祈りしています。