====== 最適化アルゴリズムの研究紹介 ======
===== 最適化問題とその応用例 =====
以下の制約付き最適化問題を考えましょう。\\
\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)**として表現することができます。不動点集合については、[[intro:researches:fixedpoint|不動点近似法]]ページをご参照下さい。\\
ここでは、この問題を以下の4種類に分けます。
  - **平滑凸最適化問題 (Smooth Convex Optimization Problem)**:\\ $f^{(i)}$ $(i\in \mathcal{I})$が平滑(微分可能)な凸関数((関数の形状がお椀状なもの、例えば、$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|$は微分不可能な凸関数です。))の場合。この問題は、[[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1206687&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F78%2F27152%2F01206687.pdf%3Farnumber%3D1206687|信号復元問題]]、[[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4291862&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F78%2F4291841%2F04291862.pdf%3Farnumber%3D4291862|ビーム形成問題]]、[[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4604754&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F49%2F4604726%2F04604754.pdf%3Farnumber%3D4604754|記憶容量割り当て問題]]、[[http://epubs.siam.org/doi/abs/10.1137/110850542|最適制御問題]]、[[http://epubs.siam.org/doi/abs/10.1137/120866877|(凹満足度指標をもつ)帯域幅割り当て問題]]といった実用的な応用問題を例として含んでいます。
  - **非平滑凸最適化問題 (Nonsmooth Convex Optimization Problem)**:\\ $f^{(i)}$ $(i\in \mathcal{I})$が非平滑(微分不可能)な凸関数の場合。この問題は、[[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4407760&filter%3DAND%28p_IS_Number%3A4407756%29|信号復元問題]]、[[https://ieeexplore.ieee.org/document/8744480|アンサンブル学習]]、[[http://link.springer.com/chapter/10.1007/978-1-4419-9569-8_17|アンテナ選択問題]]、[[https://ieeexplore.ieee.org/document/8584116|(非平滑凹満足度指標をもつ)帯域幅割り当て問題]]といった実用的な応用問題を例として含んでいます。
  - **平滑非凸最適化問題 (Smooth Nonconvex Optimization Problem)**:\\ $f^{(i)}$ $(i\in \mathcal{I})$が微分可能な(非凸)関数の場合。この問題は、[[http://link.springer.com/article/10.1007%2Fs10107-010-0427-x#|電力制御問題]]、[[http://epubs.siam.org/doi/abs/10.1137/110849456|(非凹満足度指標をもつ)帯域幅割り当て問題]]といった実用的な応用問題を例として含んでいます。
  -  **非平滑非凸最適化問題 (Nonsmooth Nonconvex Optimization Problem)**:\\ $f^{(i)}$ $(i\in \mathcal{I})$が微分不可能な(非凸)関数の場合。この問題は、[[https://www.sciencedirect.com/science/article/abs/pii/S037722171400424X|分数計画問題]]といった実用的な応用問題を例として含んでいます。

上記の問題を解決するための最適化アルゴリズムには、「集中型」と「非集中型」の最適化アルゴリズムが挙げられます。
それぞれのアルゴリズムの特徴は、以下のようにまとめることができます。
  - **集中型最適化アルゴリズム**:\\ すべての$f^{(i)}$と$C^{(i)}$の形状、すなわち、$f:= \sum_{i\in \mathcal{I}} f^{(i)}$と$C:= \bigcap_{i\in \mathcal{I}} C^{(i)}$の形状を事前に知り得ているという仮定のもとで実装できるアルゴリズム。
  - **非集中型最適化アルゴリズム**:\\ $f^{(i)}$と$C^{(i)}$の形状はユーザ$i$のみが持つ内密の情報であり、他のユーザがそれらを知ることができないという仮定のもとでも全ユーザの協力を通して実装できるアルゴリズム。

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

===== 平滑凸最適化問題に関する最適化アルゴリズム =====
==== 集中型最適化アルゴリズム ====
凸最適化問題を解くための有用なアルゴリズム ([[http://ja.wikipedia.org/wiki/%E5%86%85%E7%82%B9%E6%B3%95|内点法]]、[[http://www.ams.org/journals/bull/1964-70-05/S0002-9904-1964-11178-2/|射影法]]等) は数多く存在しますが、
その中で、東京工業大学の[[http://www.sp.ss.titech.ac.jp/index.php?%BB%B3%C5%C4%20%B8%F9|山田功先生]]が提唱された**微分可能な凸目的関数に関する凸最適化問題** (単調変分不等式) を解くための[[http://www.sciencedirect.com/science/article/pii/S1570579X01800288|ハイブリッド最急降下法]]が知られています。これまでの研究では、ハイブリッド最急降下法に基づいたアルゴリズムとその収束解析((アルゴリズムで生成された点列が最適化問題の解に収束することを数学的に証明しています。))や数値実験((既存アルゴリズムよりも高速に解への収束を示すために数値実験を行います。))について研究を進めています。
  * [[:iiduka:|H. Iiduka]]: [[http://link.springer.com/article/10.1007/s10107-013-0741-1|Acceleration Method for Convex Optimization over the Fixed Point Set of a Nonexpansive Mapping]], Mathematical Programming, Vol. 149, No. 1, pp. 131-165, 2015.
  * S. Iemoto, K. Hishinuma, and [[:iiduka:|H. Iiduka]]: [[http://www.fixedpointtheoryandapplications.com/content/2014/1/51|Approximate Solutions to Variational Inequality over the Fixed Point Set of a Strongly Nonexpansive Mapping]], Fixed Point Theory and Applications, 51, Vol. 2014, No. 1, 2014.
  * [[:iiduka:|H. Iiduka]] and [[http://www.sp.ss.titech.ac.jp/index.php?%BB%B3%C5%C4%20%B8%F9|I. Yamada]]: [[http://epubs.siam.org/doi/abs/10.1137/110850542|Computational Method for Solving a Stochastic Linear-Quadratic Control Problem Given an Unsolvable Stochastic Algebraic Riccati Equation]], SIAM Journal on Control and Optimization, Vol. 50, No. 4, pp. 2173-2192, 2012.
  * [[:iiduka:|H. Iiduka]]: [[http://www.sciencedirect.com/science/article/pii/S0377042711005358|Fixed Point Optimization Algorithm and Its Application to Network Bandwidth Allocation]], Journal of Computational and Applied Mathematics, Vol. 236, No. 7, pp. 1733-1742, 2012.
  * [[:iiduka:|H. Iiduka]]: [[http://link.springer.com/article/10.1007%2Fs10957-010-9769-z#|Iterative Algorithm for Solving Triple-hierarchical Constrained Optimization Problem]], Journal of Optimization Theory and Applications, Vol. 148, No. 3, pp. 580-592, 2011. 
  * [[:iiduka:|H. Iiduka]]: [[http://www.sciencedirect.com/science/article/pii/S0096300311000099|Three-term Conjugate Gradient Method for the Convex Optimization Problem over the Fixed Point Set of a Nonexpansive Mapping]], Applied Mathematics and Computation, Vol. 217, No. 13, pp. 6315-6327, 2011.
  * [[:iiduka:|H. Iiduka]] and [[http://www.sp.ss.titech.ac.jp/index.php?%BB%B3%C5%C4%20%B8%F9|I. Yamada]]: [[http://epubs.siam.org/action/showAbstract?page=1881&volume=19&issue=4&journalCode=sjope8|A Use of Conjugate Gradient Direction for the Convex Optimization Problem over the Fixed Point Set of a Nonexpansive Mapping]], SIAM Journal on Optimization, Vol. 19, No. 4, pp. 1881-1893, 2009. 

==== 非集中型最適化アルゴリズム ====
凸最適化問題を解くための非集中型アルゴリズムは、[[http://epubs.siam.org/doi/abs/10.1137/S1052623499362111|増分劣勾配法 (Incremental Subgradient Method) ]]や[[http://iopscience.iop.org/0266-5611/24/6/065014|並列型最適化手法 (Parallel Optimization Method) ]]等が知られています。これらの手法は、$C^{(i)} = C$ $(i\in\mathcal{I})$や$C^{(i)}=H$ $(i\in \mathcal{I})$のような、限られた範囲の凸最適化問題にしか適用ができません。そのことから、複雑な$C^{(i)}$から成る凸最適化問題 ([[http://epubs.siam.org/doi/abs/10.1137/120866877|帯域幅割り当て]]、[[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4604754&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F49%2F4604726%2F04604754.pdf%3Farnumber%3D4604754|peer-to-peerシステムネットワークでの記憶容量割り当て]]、[[https://ieeexplore.ieee.org/document/8744480|アンサンブル学習]]など、多くの応用例を持ちます) に適用可能な分散型最適化アルゴリズムの開発が待たれていました。
これまでの研究では、上記の問題点を解決できるアルゴリズムとその収束解析について提案することができています。
  * [[:iiduka:|H. Iiduka]]: [[https://ieeexplore.ieee.org/document/8744480|Stochastic Fixed Point Optimization Algorithm for Classifier Ensemble]], IEEE Transactions on Cybernetics (accepted)
  * [[:iiduka:|H. Iiduka]]: [[https://link.springer.com/article/10.1007/s11081-019-09440-7|Decentralized Hierarchical Constrained Convex Optimization]], Optimization and Engineering, Vol. 21, No. 1, pp. 181–213, 2020. 
  * [[:iiduka:|H. Iiduka]]: [[http://www.orsj.or.jp/~archive/pdf/e_mag/Vol.58_04_330.pdf|Parallel Optimization Algorithm for Smooth Convex Optimization over Fixed Point Sets of Quasi-nonexpansive Mappings]], Journal of the Operations Research Society of Japan, Vol. 58, No. 4, pp. 330-352, 2015.
  * [[:iiduka:|H. Iiduka]]: [[http://www.ybook.co.jp/online-p/JNCA/Open/16/jncav16n11p2159-oa/FLASH/index.html|Distributed Convex Optimization Algorithms and Their Application to Distributed Control in Peer-to-Peer Data Storage System]], Journal of Nonlinear and Convex Analysis: Special Issue-Dedicated to Wataru Takahashi on the occasion of his 70th birth day, Vol. 16, No. 11, pp. 2159-2179, 2015.
  * [[:iiduka:|H. Iiduka]] and K. Hishinuma: [[http://epubs.siam.org/doi/abs/10.1137/130939560|Acceleration Method Combining Broadcast and Incremental Distributed Optimization Algorithms]], SIAM Journal on Optimization, Vol. 24, No. 4, pp. 1840-1863, 2014.
  * [[:iiduka:|H. Iiduka]]: [[http://epubs.siam.org/doi/abs/10.1137/120866877|Fixed Point Optimization Algorithms for Distributed Optimization in Networked Systems]], SIAM Journal on Optimization, Vol. 23, No. 1, pp. 1-26, 2013. 

===== 非平滑凸最適化問題に関する最適化アルゴリズム =====
非平滑凸最適化を解決するための手法としては、[[http://epubs.siam.org/doi/abs/10.1137/0314056|近接点法 (Proximal Point Algorithm) ]]や[[https://en.wikipedia.org/wiki/Subgradient_method|劣勾配法 (Subgradient Method) ]]が有名です。
これまでの研究では、このような既存法のアイデアを活用することで制約付き最適化に関する幾つかのアルゴリズムとその収束解析について提案することができています。
==== 非集中型最適化アルゴリズム ====
  * K. Shimizu, K. Hishinuma, [[:iiduka:|H. Iiduka]]: Parallel Computing Proximal Method for Nonsmooth Convex Optimization With Fixed Point Constraints of Quasi-nonexpansive Mappings, Applied Set-Valued Analysis and Optimization, accepted. 
  * H. Oishi, Y. Kobayashi, [[:iiduka:|H. Iiduka]]: [[http://www.ybook.co.jp/online-p/LNA/Open/vol5/lnav5n3p477-oa/index.html|Incremental Proximal Method for Nonsmooth Convex Optimization With Fixed Point Constraints of Quasi-nonexpansive Mappings]], Linear and Nonlinear Analysis, Vol. 5, No. 3, pp. 477-493, 2019.
  * [[:iiduka:|H. Iiduka]]: [[https://ieeexplore.ieee.org/document/8584116|Distributed Optimization for Network Resource Allocation with Nonsmooth Utility Functions]], IEEE Transactions on Control of Network Systems, Vol. 6, No. 4, pp. 1354-1365, 2019.
  * K. Hishinuma and [[:iiduka:|H. Iiduka]]: [[http://www.ybook.co.jp/online2/opjnca/vol20/p1937.html|Convergence Analysis of Incremental and Parallel Line Search Subgradient Methods in Hilbert Space]], Journal of Nonlinear and Convex Analysis: Special Issue-Dedicated to Wataru Takahashi on the occasion of his 75th birth day, Vol. 20, No. 9, pp.1937-1947, 2019.
  * K. Hishinuma and [[:iiduka:|H. Iiduka]]: [[https://www.frontiersin.org/articles/10.3389/frobt.2019.00077/full|Incremental and Parallel Machine Learning Algorithms with Automated Learning Rate Adjustments]], Frontiers in Robotics and AI: Resolution of Limitations of Deep Learning to Develop New AI Paradigms, Vol. 6, Article 77, 2019. 
  * [[:iiduka:|H. Iiduka]]: [[http://www.tandfonline.com/doi/full/10.1080/10556788.2018.1425860|Two Stochastic Optimization Algorithms for Convex Optimization with Fixed Point Constraints]], Optimization Methods and Software, Vol. 34, No. 4, pp.731-757, 2019.
  * K. Sakurai, T. Jimba, and [[:iiduka:|H. Iiduka]]: [[http://jnva.biemdas.com/archives/843|Iterative Methods for Parallel Convex Optimization with Fixed Point Constraints]], Journal of Nonlinear and Variational Analysis, Vol. 3, No. 2, pp.115-126, 2019. 
  * [[http://gyoseki1.mind.meiji.ac.jp/mjuhp/KgApp?kyoinId=ymkdgygyggy|Y. Hayashi]] and [[:iiduka:|H. Iiduka]]:[[http://www.sciencedirect.com/science/article/pii/S0925231217313486|Optimality and Convergence for Convex Ensemble Learning with Sparsity and Diversity Based on Fixed Point Optimization]], Neurocomputing, Vol. 273, pp.367-372, 2018.
  * [[:iiduka:|H. Iiduka]]: [[http://www.tandfonline.com/doi/full/10.1080/02331934.2016.1252914|Almost Sure Convergence of Random Projected Proximal and Subgradient Algorithms for Distributed Nonsmooth Convex Optimization]], Optimization, Vol. 66, No. 1, pp.35-59, 2017.
  * [[:iiduka:|H. Iiduka]]: [[http://www.tandfonline.com/doi/abs/10.1080/10556788.2016.1175002?journalCode=goms20|Incremental Subgradient Method for Nonsmooth Convex Optimization with Fixed Point Constraints]], Optimization Methods and Software, Vol. 31, No. 5, pp.931-951, 2016.
  * [[:iiduka:|H. Iiduka]]: [[http://link.springer.com/article/10.1007/s10107-015-0967-1|Convergence Analysis of Iterative Methods for Nonsmooth Convex Optimization over Fixed Point Sets of Quasi-Nonexpansive Mappings]], Mathematical Programming, Vol. 159, No. 1, pp. 509-538, 2016. 
  * [[:iiduka:|H. Iiduka]]: [[http://www.sciencedirect.com/science/article/pii/S0377221716301102|Proximal Point Algorithms for Nonsmooth Convex Optimization with Fixed Point Constraints]], European Journal of Operational Research, Vol. 253, No. 2, pp. 503-513, 2016.
  * [[:iiduka:|H. Iiduka]]: [[http://www.fixedpointtheoryandapplications.com/content/2015/1/72|Parallel Computing Subgradient Method for Nonsmooth Convex Optimization over the Intersection of Fixed Point Sets of Nonexpansive Mappings]], Fixed Point Theory and Applications, Vol. 2015, 72, 2015.
===== 平滑非凸最適化問題に関する最適化アルゴリズム =====
==== 集中型最適化アルゴリズム ====
非凸目的関数に関する最適化問題に対しては、[[http://ja.wikipedia.org/wiki/%E5%87%B8%E8%A7%A3%E6%9E%90|凸解析]]の理論を直接、適用することはできません。そのため非凸最適化問題を解くための集中型最適化アルゴリズムを開発することは易しくはないであろう、ということは理解してもらえると思います。これまでの研究では、東京工業大学名誉教授の[[http://www.sci.keio.ac.jp/member/detail.php?eid=00119&katagaki=3&status=1|高橋渉先生]]らによって確立された[[http://www.ybook.co.jp/pub/ISBN978-4-946552-35-9.htm|非線形関数解析学]]や[[http://www.ybook.co.jp/pub/ISBN4-646552-04-9.htm|不動点理論]]を利用することにより、以下の成果を得ることができています。
  * [[:iiduka:|H. Iiduka]]: [[http://epubs.siam.org/doi/abs/10.1137/110849456|Iterative Algorithm for Triple-Hierarchical Constrained Nonconvex Optimization Problem and Its Application to Network Bandwidth Allocation]], SIAM Journal on Optimization, Vol. 22, No. 3, pp. 862-878, 2012.
  * [[:iiduka:|H. Iiduka]]: [[http://link.springer.com/article/10.1007%2Fs10107-010-0427-x#|Fixed Point Optimization Algorithm and Its Application to Power Control in CDMA Data Networks]], Mathematical Programming, Vol. 133, No.1, pp. 227-242, 2012. 
  * [[:iiduka:|H. Iiduka]] and M. Uchida: [[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5752800&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4234%2F5895119%2F05752800.pdf%3Farnumber%3D5752800|Fixed Point Optimization Algorithms for Network Bandwidth Allocation Problems with Compoundable Constraints]], IEEE Communications Letters, Vol. 15, No. 6, pp. 596-598, 2011.
  * [[:iiduka:|H. Iiduka]] and [[http://www.sp.ss.titech.ac.jp/index.php?%BB%B3%C5%C4%20%B8%F9|I. Yamada]]: [[http://www.tandfonline.com/doi/abs/10.1080/02331930701762829|A Subgradient-type Method for the Equilibrium Problem over the Fixed Point Set and its Applications]], Optimization, Vol. 58, No. 2, pp. 251-261, 2009. 




==== 非集中型最適化アルゴリズム ====
上記の最適化アルゴリズムのアイデアを組み合わせることにより、非集中型最適化アルゴリズムを提案しています。
  * [[:iiduka:|H. Iiduka]]: [[http://www.ybook.co.jp/|Distributed Iterative Methods for Solving Nonmonotone Variational Inequality over the Intersection of Fixed Point Sets of Nonexpansive Mappings]], Pacific Journal of Optimization, Vol. 10, No. 4, pp. 691-713, 2014.

===== 非平滑非凸最適化問題に関する最適化アルゴリズム =====
==== 集中型最適化アルゴリズム ====
非拡大写像の不動点集合上で準凸関数を最小化するための集中型最適化アルゴリズムを提案しています。
  * K. Hishinuma and [[:iiduka:|H. Iiduka]]: [[https://doi.org/10.1016/j.ejor.2019.09.037|Fixed Point Quasiconvex Subgradient Method]], European Journal of Operational Research, Vol. 282, No. 2, 428–437, 2020.