intro:researches:optimization

最適化アルゴリズムの研究紹介

最適化問題とその応用例

以下の制約付き最適化問題を考えましょう。
\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種類に分けます。

  1. 平滑凸最適化問題 (Smooth Convex Optimization Problem):
    $f^{(i)}$ $(i\in \mathcal{I})$が平滑(微分可能)な凸関数1)の場合。この問題は、信号復元問題、ビーム形成問題、記憶容量割り当て問題、最適制御問題、(凹満足度指標をもつ)帯域幅割り当て問題といった実用的な応用問題を例として含んでいます。
  2. 非平滑凸最適化問題 (Nonsmooth Convex Optimization Problem):
    $f^{(i)}$ $(i\in \mathcal{I})$が非平滑(微分不可能)な凸関数の場合。この問題は、信号復元問題、アンサンブル学習、アンテナ選択問題、(非平滑凹満足度指標をもつ)帯域幅割り当て問題といった実用的な応用問題を例として含んでいます。
  3. 平滑非凸最適化問題 (Smooth Nonconvex Optimization Problem):
    $f^{(i)}$ $(i\in \mathcal{I})$が微分可能な(非凸)関数の場合。この問題は、電力制御問題、(非凹満足度指標をもつ)帯域幅割り当て問題といった実用的な応用問題を例として含んでいます。
  4. 非平滑非凸最適化問題 (Nonsmooth Nonconvex Optimization Problem):
    $f^{(i)}$ $(i\in \mathcal{I})$が微分不可能な(非凸)関数の場合。この問題は、分数計画問題といった実用的な応用問題を例として含んでいます。

上記の問題を解決するための最適化アルゴリズムには、「集中型」と「非集中型」の最適化アルゴリズムが挙げられます。 それぞれのアルゴリズムの特徴は、以下のようにまとめることができます。

  1. 集中型最適化アルゴリズム:
    すべての$f^{(i)}$と$C^{(i)}$の形状、すなわち、$f:= \sum_{i\in \mathcal{I}} f^{(i)}$と$C:= \bigcap_{i\in \mathcal{I}} C^{(i)}$の形状を事前に知り得ているという仮定のもとで実装できるアルゴリズム。
  2. 非集中型最適化アルゴリズム:
    $f^{(i)}$と$C^{(i)}$の形状はユーザ$i$のみが持つ内密の情報であり、他のユーザがそれらを知ることができないという仮定のもとでも全ユーザの協力を通して実装できるアルゴリズム。

以降では、それらの最適化アルゴリズムについて紹介します （論文は研究業績等一覧から入手できます）。

平滑凸最適化問題に関する最適化アルゴリズム

集中型最適化アルゴリズム

凸最適化問題を解くための有用なアルゴリズム (内点法、射影法等) は数多く存在しますが、 その中で、東京工業大学の山田功先生が提唱された微分可能な凸目的関数に関する凸最適化問題 (単調変分不等式) を解くためのハイブリッド最急降下法が知られています。これまでの研究では、ハイブリッド最急降下法に基づいたアルゴリズムとその収束解析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) が有名です。 これまでの研究では、このような既存法のアイデアを活用することで制約付き最適化に関する幾つかのアルゴリズムとその収束解析について提案することができています。

非集中型最適化アルゴリズム

平滑非凸最適化問題に関する最適化アルゴリズム

集中型最適化アルゴリズム

非凸目的関数に関する最適化問題に対しては、凸解析の理論を直接、適用することはできません。そのため非凸最適化問題を解くための集中型最適化アルゴリズムを開発することは易しくはないであろう、ということは理解してもらえると思います。これまでの研究では、東京工業大学名誉教授の高橋渉先生らによって確立された非線形関数解析学や不動点理論を利用することにより、以下の成果を得ることができています。

非集中型最適化アルゴリズム

上記の最適化アルゴリズムのアイデアを組み合わせることにより、非集中型最適化アルゴリズムを提案しています。

非平滑非凸最適化問題に関する最適化アルゴリズム

集中型最適化アルゴリズム

非拡大写像の不動点集合上で準凸関数を最小化するための集中型最適化アルゴリズムを提案しています。

1)
関数の形状がお椀状なもの、例えば、$f^{(i)}(x) = f^{(i)} (x_1,x_2,\ldots,x_N) = x_1^2 + x_2^2 + \cdots + x_N^2$のような二次関数は微分可能な凸関数です。$f^{(i)}(x) = |x_1| + |x_2| + \cdots + |x_N|$は微分不可能な凸関数です。
2)
アルゴリズムで生成された点列が最適化問題の解に収束することを数学的に証明しています。
3)
既存アルゴリズムよりも高速に解への収束を示すために数値実験を行います。
  • intro/researches/optimization.txt
  • 最終更新: 2023/06/14 15:19
  • by 127.0.0.1