以下の制約付き最適化問題を考えましょう。
\begin{align*}
\text{Minimize } f(x):= \sum_{i\in \mathcal{I}} f^{(i)} (x) \text{ subject to } x\in C := \bigcap_{i\in \mathcal{I}} C^{(i)}.
\end{align*}
ただし、$H$はHilbert空間、$f^{(i)} \colon H \to \mathbb{R}$ $(i\in \mathcal{I}:= \{1,2,\ldots,I\})$は目的関数、
$C^{(i)}$ $(\subset H)$ $(i\in \mathcal{I})$ は$C \neq \emptyset$を満たす凸制約集合とします。$C^{(i)}$については、単純な形状の場合（例えば、閉球、半空間）や単純な形状ではない場合（例えば、凸多面体や凸関数の最小解の集合、変分不等式の解集合）に焦点をあてます。このような$C^{(i)}$の多くは、非拡大写像 (nonexpansive mapping)と呼ばれる不動点集合 (fixed point set)として表現することができます。不動点集合については、不動点近似法ページをご参照下さい。
ここでは、この問題を以下の4種類に分けます。
上記の問題を解決するための最適化アルゴリズムには、「集中型」と「非集中型」の最適化アルゴリズムが挙げられます。 それぞれのアルゴリズムの特徴は、以下のようにまとめることができます。
以降では、それらの最適化アルゴリズムについて紹介します （論文は研究業績等一覧から入手できます）。
凸最適化問題を解くための有用なアルゴリズム (内点法、射影法等) は数多く存在しますが、 その中で、東京工業大学の山田功先生が提唱された微分可能な凸目的関数に関する凸最適化問題 (単調変分不等式) を解くためのハイブリッド最急降下法が知られています。これまでの研究では、ハイブリッド最急降下法に基づいたアルゴリズムとその収束解析2)や数値実験3)について研究を進めています。
凸最適化問題を解くための非集中型アルゴリズムは、増分劣勾配法 (Incremental Subgradient Method) や並列型最適化手法 (Parallel Optimization Method) 等が知られています。これらの手法は、$C^{(i)} = C$ $(i\in\mathcal{I})$や$C^{(i)}=H$ $(i\in \mathcal{I})$のような、限られた範囲の凸最適化問題にしか適用ができません。そのことから、複雑な$C^{(i)}$から成る凸最適化問題 (帯域幅割り当て、peer-to-peerシステムネットワークでの記憶容量割り当て、アンサンブル学習など、多くの応用例を持ちます) に適用可能な分散型最適化アルゴリズムの開発が待たれていました。 これまでの研究では、上記の問題点を解決できるアルゴリズムとその収束解析について提案することができています。
非平滑凸最適化を解決するための手法としては、近接点法 (Proximal Point Algorithm) や劣勾配法 (Subgradient Method) が有名です。 これまでの研究では、このような既存法のアイデアを活用することで制約付き最適化に関する幾つかのアルゴリズムとその収束解析について提案することができています。
非凸目的関数に関する最適化問題に対しては、凸解析の理論を直接、適用することはできません。そのため非凸最適化問題を解くための集中型最適化アルゴリズムを開発することは易しくはないであろう、ということは理解してもらえると思います。これまでの研究では、東京工業大学名誉教授の高橋渉先生らによって確立された非線形関数解析学や不動点理論を利用することにより、以下の成果を得ることができています。
上記の最適化アルゴリズムのアイデアを組み合わせることにより、非集中型最適化アルゴリズムを提案しています。
非拡大写像の不動点集合上で準凸関数を最小化するための集中型最適化アルゴリズムを提案しています。