2 最適化問題の分類

すべての最適化問題に対して効率的な単一のソルバーは存在しません。そのため、問題と特定のニーズにできるだけ合致したソルバーを選択することが重要です。もちろん、汎用性の高いソルバーを適用することも選択肢の一つですが、その場合、基礎となるアルゴリズムによっては、パフォーマンスが低下することがあります。

最適化問題を特定のカテゴリーに分類するためのさまざまな基準があります。主な基準は以下の通りです：

• 目的関数の種類
• 制約の種類
• 問題のサイズ
• データの滑らかさと利用可能な導関数情報

各基準について以下で説明し、最適化問題のクラスを特定するために必要な情報を提供します。セクション5ではアルゴリズムの基本的な特性を紹介します。

2.1 目的関数の種類

最適化問題において、目的関数の種類は問題の性質を大きく左右します。特に、目的関数に特定の構造が存在する場合、ソルバーはその特性を活用することで、より効率的に解を導き出すことができます。以下では、代表的な目的関数の種類とその特徴について説明します。

例えば、二乗和目的関数に特化したソルバーは、同じ問題を一般的な非線形目的関数として扱う場合と比較して、より優れたパフォーマンスを発揮します。このため、代表的な目的関数の種類とその特徴を理解することは、効率的な問題解決において重要な役割を果たします。

目的関数が存在しない最適化問題は、定数目的関数、つまり$f(x)=0$を持つ問題と同じように扱えます。これは一般的に実行可能点問題と呼ばれます。この問題の目標は、与えられた制約条件を満たす任意の点を見つけることです。

線形目的関数は、すべての変数に関して線形である関数です。したがって、次のような形式で表現できます：

$f(x)=c^{T}x+c_0$

ここで、$c\in {\mathbb{R}}^n$です。スカラー$c_0$は決定変数$x$の選択に影響を与えないため、通常省略されます。以降のテキストでは使用しません。

二次目的関数は、線形関数を二次項で拡張したものです：

$f(x)=\frac{1}{2}{x}^{T}Hx+c^{T}x.$

ここで、$H$は実対称$n\times n$行列です。さらに、$H$が正半定値（すべての固有値が非負）である場合、目的関数は凸です。凸の場合、二次項は次のような因数分解形式で定義することもできます：

$f(x)=\frac{1}{2}{x}^T{F}^{T}Fx+c^{T}x$

ここで、$F$は$H=F^{T}F$の因子とみなすことができます。例えば、線形最小二乗問題$\Vert Fx-y{\Vert }_2^2$の目的関数はこのクラスに属します。その二次項は$x^T{F}^{T}Fx$で、$c=-2y^{T}F$です。

一般的な非線形目的関数は、特別な構造を持たない任意の$f:{\mathbb{R}}^n\to \mathbb{R}$です。

損失関数の和の形式の目的関数には特別な考慮が払われます。例えば：

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

ここで、$r_i:{\mathbb{R}}^n\to \mathbb{R}$はしばしば残差関数と呼ばれ、この種の問題はセクション2.3で示すように最小二乗問題として解かれます。そして、この形式の目的関数はデータ適合で重要な役割を果たします。ここでは、$l_1$ノルムやHuber関数などの一般的な損失関数$\chi$が以下のように使用されます：

$f(x)=\sum _{i=1}^m\chi (r_i(x)).$

2.2 制約の種類

最適化問題における制約は、解の探索空間を定義する重要な要素です。しかし、すべての最適化問題に制約があるわけではありません。 ここでは、無制約問題から始めて、様々な種類の制約とその数学的表現について詳しく見ていきます。

まず、最適化問題には必ずしも制約がつきものではありません。決定変数$x$が集合$F={\mathbb{R}}^n$に属する以外に選択の制限がない場合、その問題は無制約問題と呼ばれます。このとき、すべての点が実行可能解となります。

一方、決定変数$x\in {\mathbb{R}}^n$に対する単純な境界（ボックス制約あるいは境界制約としても知られる）は、変数の値に制限を加えます。例えば、$x_5\le 10$のような形で表されます。これらの制約は一般的に次のような形式で記述できます：

$l{x}_i\le x_i\le u{x}_i,i=1,\dots ,n$

またはベクトル表記で：

$lx\le x\le ux$

ここで、$lx$と$ux$は$n$次元ベクトルを表します。すべての変数に対して下限と上限が指定されていることが特徴です。概念的には$l{x}_i=-\mathrm{\infty }$や$u{x}_i=+\mathrm{\infty }$、あるいは$l{x}_i=u{x}_i$を許容することで、無制約変数、片側不等式、範囲制約、または等式制約（変数の固定）など、様々な種類の制約を一般化して表現できます。

この境界形式は、nAGの数理最適化ソルバーにおける線形制約と非線形制約に採用されています。ただし、ルーチンに無限大の境界を渡す際、特定の閾値（通常は${10}^{20}$）を超えるすべての値は$+\mathrm{\infty }$として扱われることに留意してください。

線形制約は、すべての変数に対して線形である制約関数として定義されます。例えば、$3x_1+2x_2\ge 4$のような形で表されます。これらの制約は行列形式で次のように表現できます：

$lB\le Bx\le uB$

ここで、$B$は一般的な$m_B\times n$の長方形行列で、$lB$と$uB$は$m_B$次元ベクトルです。$B$の各行は1つの線形制約の線形係数を表します。単純な境界の場合と同じ規則が適用されます。

$x_i$に対する境界は線形制約の定義に含めることが可能ですが、計算効率の観点から、多くのソルバーが単純な境界を明示的に扱うため、これらを区別することが推奨されます。

二次制約は、変数の集合の二次関数として標準形式で次のように定義されます：

$\frac{1}{2}{x}^{T}Qx+r^{T}x+s\le 0$

ここで、$Q$は対称$n\times n$行列、$r$は$n$次元ベクトル、$s$はスカラーです。$Q$が正半定値の場合、制約は凸となります。凸の場合、二次制約は二次目的関数と同様に、因数分解形式でも定義できます：

$\frac{1}{2}{x}^T{F}^{T}Fx+r^{T}x+s\le 0$

ここで、$F$は長方形行列で、$Q=F^{T}F$の因子とみなすことができます。

$m_g$個の非線形制約の集合は、非線形関数$g:{\mathbb{R}}^n\to {\mathbb{R}}^{m_g}$と、単純な境界および線形制約と同じ形式に従う境界$l_g$および$u_g$の観点から次のように定義できます：

$l_g\le g(x)\le u_g.$

線形制約は非線形制約の定義に含めることが可能ですが、ここでも計算効率の観点から、これらを区別することが推奨されます。

一般的に使用される2つの二次錐（二次、Lorentzまたはアイスクリーム錐としても知られる）があります：二次錐と回転二次錐です。これらは以下の不等式によって定義されます：

• 二次錐：

  ${\mathcal{K}}_q^{m_i}\triangleq \{z=(z_1,z_2,\dots ,z_{m_i})\in {\mathbb{R}}^{m_i}:z_1^2\ge \sum _{j=2}^{m_i}{z}_j^2,z_1\ge 0\}.$

• 回転二次錐：

  ${\mathcal{K}}_r^{m_i}\triangleq \{z=(z_1,z_2,\dots ,z_{m_i})\in {\mathbb{R}}^{m_i}:2z_1{z}_2\ge \sum _{j=3}^{m_i}{z}_j^2,z_1\ge 0,z_2\ge 0\}.$

ここで、$z$は決定変数$x$の部分集合を表します。このような錐はモデルの定式化に自然に現れるわけではないため、しばしば再定式化が必要となります。例えば、すべての凸二次制約や多くの種類のノルム最小化問題は二次錐として表現することができます。詳細については、nAGライブラリルーチンe04ptf 大規模二次錐計画問題ソルバー（SOCP）のセクション9.1を参照してください。

行列制約（または行列不等式）は、行列演算子の固有値に対する制約です。より厳密には、${\mathbb{S}}^m$を$m\times m$実対称行列の空間とし、$\mathcal{A}$を行列演算子$\mathcal{A}:{\mathbb{R}}^n\to {\mathbb{S}}^m$とします。つまり、各$x$に対して対称行列$\mathcal{A}(x)$を割り当てます。行列制約は次のように表現できます：

$\mathcal{A}(x)⪰0$

ここで、$S\in {\mathbb{S}}^m$に対する不等式$S⪰0$は固有値の観点から解釈されます。つまり、行列$S$のすべての固有値が非負（行列が正半定値）でなければなりません。

nAGの数理最適化ソルバーで許可されている行列制約には2つのタイプがあります。1つ目は次のように定式化される線形行列不等式（LMI）です：

$\mathcal{A}(x)=\sum _{i=1}^n{x}_i{A}_i-A_0⪰0$

2つ目は双線形行列不等式（BMI）と呼ばれ、次のように記述されます：

$\mathcal{A}(x)=\sum _{i,j=1}^n{x}_i{x}_j{Q}_{ij}+\sum _{i=1}^n{x}_i{A}_i-A_0⪰0.$

ここで、すべての行列$A_i$、$Q_{ij}$は同じ次元の与えられた実対称行列です。後者のタイプは実際には$x$に関して二次ですが、歴史的な理由から双線形と呼ばれています。

2.3 典型的な最適化問題のクラス

目的関数と制約の特定の組み合わせにより、様々なクラスの最適化問題が生じます。以下に一般的なものを示します。ソルバーを選択する際は、常に問題を最も適切にカバーする定式化を考慮することが推奨されます。

詳細については、Dantzig (1963)、Gill et al. (1981)、Fletcher (1987)、Nocedal and Wright (2006)、Chvatal (1983)などの代表的な文献を参照してください。

線形計画法（LP）問題は、線形目的関数、線形制約、および単純な境界を持つ問題です。次のように書くことができます：

$$\begin{array}{rl}\text{minimize}& c^{T}x\\ \text{subject to}& l_B\le Bx\le u_B,\\ & l_x\le x\le u_x.\end{array}$$

二次計画法（QP）問題は、線形制約と単純な境界で定義される集合上で二次目的関数を最適化します。目的関数の凸性に応じて、凸QPと非凸QP（または一般QP）に分類されます。

$$\begin{array}{rl}\text{minimize}& \frac{1}{2}{x}^{T}Hx+c^{T}x\\ \text{subject to}& l_B\le Bx\le u_B,\\ & l_x\le x\le u_x.\end{array}$$

二次制約付き二次計画法（QCQP）問題は、二次計画問題に二次制約の集合を加えて拡張したものです。目的関数と二次制約の凸性に応じて、凸QCQPと非凸QCQP（または一般QCQP）に分類されます。

$$\begin{array}{rl}\text{minimize}& \frac{1}{2}{x}^{T}Hx+c^{T}x\\ \text{subject to}& \frac{1}{2}{x}^T{Q}_{k}x+r_k^{T}x+s_k\le 0,k=1,\dots ,m_Q,\\ & l_B\le Bx\le u_B,\\ & l_x\le x\le u_x.\end{array}$$

非線形計画法（NLP）問題は、一般的な非線形目的関数$f(x)$を最適化し、非線形、二次、線形、または境界制約のいずれか（あるいはそれらの組み合わせ）を含みます。制約の一部または全部が欠如している特殊なケースとして、無制約NLP、境界制約付きNLP、または線形制約付きNLPがあります。これらの問題に対しては、各制約タイプに特別な配慮をしたアルゴリズムを用いる特定のソルバーが存在する場合があります。なお、線形または二次目的関数と非線形制約を持つ問題は、依然として一般的なNLPとして扱うべきです。

$$\begin{array}{rl}\text{minimize}& f(x)\\ \text{subject to}& l_g\le g(x)\le u_g,\\ & l_B\le Bx\le u_B,\\ & l_x\le x\le u_x.\end{array}$$

二次錐計画法（SOCP）問題は、線形目的関数、線形制約、単純な境界、および1つ以上の二次錐で構成されます。SOCP問題は次のように表現できます：

$$\begin{array}{rl}\text{minimize}& c^{T}x\\ \text{subject to}& l_A\le Ax\le u_A,\\ & l_x\le x\le u_x,\\ & x\in K,\end{array}$$

ここで、$K={\mathcal{K}}^{n_1}\times \cdots \times {\mathcal{K}}^{n_r}\times {\mathbb{R}}^{n_l}$は、$r$個の二次または回転二次錐（セクション2.2で定義）と$n_l$次元実空間のデカルト積です。この定式化では、錐が重複する（つまり、1つの決定変数が複数の二次錐に関与する）可能性があることに注意が必要です。SOCPは多くの凸問題に対して非常に強力なモデリング手法ですが、通常、上記の形式を得るためにモデルの再定式化が必要となります。凸QCQP問題はソルバーによって自動的に再定式化されますが、その他のケースについては、nAGライブラリルーチンe04ptf 大規模二次錐計画問題ソルバー（SOCP）のセクション9.1、Alizadeh and Goldfarb (2003)、Lobo et al. (1998)を参照してください。

半正定値計画法（SDP）は通常、線形半正定値計画法を指し、線形目的関数、線形制約、および線形行列不等式を持つ問題です：

$$\begin{array}{rl}\text{minimize}& c^{T}x\\ \text{subject to}& \sum _{i=1}^n{x}_i{A}_i^k-A_0^k⪰0,k=1,\dots ,m_A,\\ & l_B\le Bx\le u_B,\\ & l_x\le x\le u_x.\end{array}$$

この問題は、二次目的関数と双線形（実際には二次）行列不等式で拡張できます。これを双線形行列不等式付き半正定値計画問題（BMI-SDP）と呼びます：

$$\begin{array}{rl}\text{minimize}& \frac{1}{2}{x}^{T}Hx+c^{T}x\\ \text{subject to}& \sum _{i,j=1}^n{x}_i{x}_j{Q}_{ij}^k+\sum _{i=1}^n{x}_i{A}_i^k-A_0^k⪰0,k=1,\dots ,m_A,\\ & l_B\le Bx\le u_B,\\ & l_x\le x\le u_x.\end{array}$$

最小二乗法（LSQ）問題は、通常の制約の下で二乗和の形式の目的関数を最小化する問題です。残差関数$r_i(x)$の性質に応じて、問題は以下のように分類されます：

• $r_i(x)$が線形の場合：線形最小二乗法
• $r_i(x)$が非線形の場合：非線形最小二乗法

NLPと同様に、制約の有無や種類によって特殊なケースが生じます：

• 無制約最小二乗問題
• 境界制約付き最小二乗問題
• 線形制約付き最小二乗問題

$$\begin{array}{rl}\text{minimize}& \sum _{i=1}^m{r}_i^2(x)\\ \text{subject to}& l_g\le g(x)\le u_g,\\ & l_B\le Bx\le u_B,\\ & l_x\le x\le u_x.\end{array}$$

この形式の問題は、データ適合（DF）において非常に一般的です。以下に例を示します。

時刻$t_i$で観測され、結果$y_i$（$i=1,2,\dots ,m$）で測定されるプロセスを考えます。このプロセスはモデル$\varphi (t;x)$に従って動作すると仮定します。ここで$x$はモデルのパラメータです。

測定の不正確さやプロセスがモデルに完全に従わない可能性を考慮すると、各測定におけるモデルと測定値の適合誤差の二乗和を最小化するようなモデルパラメータ$x$を見つけることが有益です。

これは、$x$を決定変数とし、目的関数を各測定における適合の二乗誤差の和とする最適化問題として次のように定式化できます：

$$\text{minimize}\sum _{i=1}^m{r}_i^2(x)\text{where}{r}_i(x)=\varphi (t_i;x)-y_i.$$

LSQ問題が少数の異常値や極端な観測値の影響を受ける場合、より一般的な非線形データ適合（NLDF）問題へと自然に拡張できます。この場合、二乗和はHuber関数やQuantile関数などのより広範な損失関数に置き換えられます。したがって、一般化モデルは次のように表現されます：

$$\begin{array}{rl}\text{minimize}& \sum _{i=1}^m\chi (r_i(x))+\rho \sum _{i=1}^n\psi (x_i)\\ \text{subject to}& l_g\le g(x)\le u_g,\\ & \frac{1}{2}{x}^T{Q}_{i}x+p_i^{T}x+s_i\le 0,1\le i\le m_Q,\\ & l_B\le Bx\le u_B,\\ & l_x\le x\le u_x,\end{array}$$

ここで、$\chi$は損失関数を、$\psi$は正則化関数を表します。例えば、以下のような正則化関数が一般的です：

• LASSOでの$l_1$ノルム
• リッジ回帰での$l_2$ノルム
• エラスティックネット回帰での上記2つの組み合わせ

$\chi$が$l_2$ノルムで正則化がない場合、問題はLSQの特殊ケースとなります。

有用な損失関数には以下のようなものがあります：

• $l_1$ノルム
• $l_{\mathrm{\infty }}$ノルム
• Huber関数
• Cauchy関数
• Arctan関数
• SmoothL1関数
• Quantile関数

各損失関数の詳細な定義と特性については、nAGライブラリルーチンe04gnf 一般的非線形データフィッティングソルバーのセクション11を参照してください。

フィッティングパラメータに境界制約やより複雑な非線形制約などの特定の要件がある場合、問題に制約を加えることが可能です。

2.4 問題のサイズ、密問題と疎問題

最適化問題の規模やデータ構造は、ソルバー選択に大きく影響します。ここでは、問題のサイズに基づく分類と、密問題・疎問題の概念について説明します。

問題の規模は、ソルバーを選択する際に重要な要素となります。サイズは通常、変数の数$n$と制約の数（および種類）によって特徴づけられます。問題のサイズに応じて、小規模、中規模、または大規模問題として分類されます。

しかし、問題のサイズだけでなく、データとその構造を考慮することがしばしばより実用的です。典型的に、大規模問題ではすべての変数が互いに相互作用するわけではありません。制約の一部（または全部）がすべての変数を含むことはあり得ますが、多くの制約は変数の小さな異なる部分集合にのみ依存することが一般的です。これにより、データ表現に多くの明示的なゼロが生じ、それをとらえてソルバーに渡すことが有益となります。このような場合、問題は疎と呼ばれます。

データ表現は通常、以下のような疎行列の形式をとります：

• 線形制約行列$B$
• 非線形制約$g_i$のヤコビ行列
• 目的関数のヘッシアン$H$

一般的な疎行列フォーマットには、以下のようなものがあります：

• 座標記憶（CS）
• 圧縮列記憶（CCS）

これらの詳細については、nAGライブラリ F11 チャプターイントロダクションのセクション2.1を参照してください。

疎問題の対極にあるのが密問題で、行列は一般的な全体フォーマットで保存され、構造は仮定も利用もされません。密問題を疎ソルバーに渡すことは通常小さなオーバーヘッドしか生じませんが、大規模な疎問題に密ソルバーを使用することは推奨されません。これは著しいパフォーマンスの低下とメモリの過剰使用につながります。

2.5 導関数情報、滑らかさ、ノイズ、および導関数フリー最適化（DFO）

ほとんどの古典的な最適化アルゴリズムは、導関数情報に大きく依存しています。これは必要十分条件（セクション4参照）や各反復での探索方向の計算（セクション5参照）において重要な役割を果たします。したがって、可能な限り非線形目的関数と非線形制約の正確な導関数を提供することが重要です。

特に明記されていない限り、非線形関数は十分に滑らかであると仮定されます。ソルバーは通常、解から離れた場所に孤立した不連続性がある場合でも最適化問題を解きますが、問題のより滑らかな表現が存在するかどうかを常に検討すべきです。典型的な例は、$x_i=0$で一階導関数を持たない絶対値$|x_i|$です。しかし、モデルが許す場合、これは以下のように変換できます：

$$x_i=x_i^{+}-x_i^{-},|x_i|=x_i^{+}+x_i^{-},\text{where}{x}_i^{+},x_i^{-}\ge 0$$

これにより、一階導関数の不連続性を回避できます。多数の不連続点が存在する場合、e04cbf Nelder-Mead法による導関数不要の非線形最適化ソルバーやE05章のe05saf 粒子群最適化、シンプルインタフェース、e05sbf 粒子群最適化、詳細インタフェースなどの確率的アルゴリズムといった代替手法の適用が必要となります。

関数の一階偏導関数のベクトルは勾配ベクトルと呼ばれ、以下のように表されます：

$\mathrm{\nabla }f(x)=[\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\dots ,\frac{\partial f(x)}{\partial x_n}{]}^T,$

二階偏導関数の行列はヘッシアン行列と呼ばれます：

${\mathrm{\nabla }}^{2}f(x)=[\frac{{\partial }^{2}f(x)}{\partial x_i\partial x_j}{]}_{i,j=1,\dots ,n}$

そしてベクトル値関数$g:{\mathbb{R}}^n\to {\mathbb{R}}^m$の一階偏導関数の行列はヤコビアン行列として知られています：

$J(x)=[\frac{\partial g_i(x)}{\partial x_j}{]}_{i=1,\dots ,m,j=1,\dots ,n}.$

関数が滑らかであっても導関数が利用できない場合、変数の微小な摂動に対する関数値の変化である有限差分を用いて近似することができます。多くのnAGの数理最適化ソルバーは、この手法を用いて勾配の欠落要素を自動的に推定します。摂動の大きさの選択は、近似の精度に大きく影響します。摂動が小さすぎると、浮動小数点演算での桁落ちにより近似精度が低下する可能性があり、逆に大きすぎると有限差分と導関数の乖離が大きくなります（最適なバランスについてはnAGライブラリルーチン[e04xaf]/e04xaa 勾配ベクトルおよび/またはヘッセ行列計算](https://support.nag.com/numeric/nl/nagdoc_latest/flhtml/e04/e04xaf.html)を参照してください）。

さらに、有限差分法は$f(x)$の精度に非常に敏感です。$f(x)$が確率的シミュレーションやPDEの近似解から得られる場合など、関数評価に不正確さやノイズが含まれる場合、有限差分法は信頼性が低下したり、完全に失敗したりする可能性があります。

導関数フリー最適化（DFO）は、導関数ベースの最適化アルゴリズムに代わる手法です。DFOソルバーは導関数情報を必要とせず、有限差分による近似も行いません。その代わりに、領域全体で関数値をサンプリングし、それに基づいて次の探索点を決定します（例えば、サンプリングした点を通る二次モデルを用いるなど）。このため、サンプル点同士が近すぎることがなく、関数のノイズによる相対誤差の影響を受けにくくなります。

有限差分が計算可能な場合でも、関数評価回数が少ないためDFOが有効な場合があります。特に$f$の評価コストが高い問題において有用です。DFOソルバーは初期段階での解への収束が速い傾向にありますが、通常は高精度の解を得ることは難しいという特徴があります。

2.6 目的関数に対する境界制約付き最小化

これまで説明してきたすべての問題カテゴリーにおいて、 $a\le f(x)\le b$ という条件が想定されており、ここで$a=-\mathrm{\infty }$および$b=+\mathrm{\infty }$とされています。$a$や$b$が有限値である問題は、$f(x)$の形式に応じて適切なタイプ（線形または非線形）の制約を追加することで解決できます。より詳細な情報については、nAGライブラリのE04チャプター導入部のセクション3.7を参照してください。

2.7 多目的最適化

複数の目的関数を同時に最適化する必要がある問題があります。これらは多目的、多基準、または多属性最適化と呼ばれます。制約条件が線形で、全ての目的関数が線形の場合は、目標計画法という用語も使用されます。

現在のライブラリには、この種の問題を直接扱うルーチンは含まれていませんが、nAGライブラリのE04章とE05章のルーチンを利用して、これらの問題に対処することが可能です。