差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

intro:researches:optimization [2019/06/29 16:22] – [非集中型最適化アルゴリズム] Hideaki IIDUKAintro:researches:optimization [2023/06/14 15:19] (現在) – 外部編集 127.0.0.1
行 7: 行 7:
 ただし、$H$はHilbert空間、$f^{(i)} \colon H \to \mathbb{R}$ $(i\in \mathcal{I}:= \{1,2,\ldots,I\})$は目的関数、 ただし、$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|不動点近似法]]ページをご参照下さい。\\ $C^{(i)}$ $(\subset H)$ $(i\in \mathcal{I})$ は$C \neq \emptyset$を満たす凸制約集合とします。$C^{(i)}$については、単純な形状の場合(例えば、閉球、半空間)や単純な形状ではない場合(例えば、凸多面体や凸関数の最小解の集合、変分不等式の解集合)に焦点をあてます。このような$C^{(i)}$の多くは、**非拡大写像 (nonexpansive mapping)**と呼ばれる**不動点集合 (fixed point set)**として表現することができます。不動点集合については、[[intro:researches:fixedpoint|不動点近似法]]ページをご参照下さい。\\
-ここでは、この問題を以下の3種類に分けます。+ここでは、この問題を以下の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|(凹満足度指標をもつ)帯域幅割り当て問題]]といった実用的な応用問題を例として含んでいます。   - **平滑凸最適化問題 (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|信号復元問題]]、[[http://www.sciencedirect.com/science/article/pii/S0925231214000964|アンサンブル学習]]、[[http://link.springer.com/chapter/10.1007/978-1-4419-9569-8_17|アンテナ選択問題]]、[[https://ieeexplore.ieee.org/document/8584116|(非平滑凹満足度指標をもつ)帯域幅割り当て問題]]といった実用的な応用問題を例として含んでいます。+  - **非平滑凸最適化問題 (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|(非凹満足度指標をもつ)帯域幅割り当て問題]]といった実用的な応用問題を例として含んでいます。   - **平滑非凸最適化問題 (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|分数計画問題]]といった実用的な応用問題を例として含んでいます。
  
 上記の問題を解決するための最適化アルゴリズムには、「集中型」と「非集中型」の最適化アルゴリズムが挙げられます。 上記の問題を解決するための最適化アルゴリズムには、「集中型」と「非集中型」の最適化アルゴリズムが挙げられます。
行 32: 行 33:
  
 ==== 非集中型最適化アルゴリズム ==== ==== 非集中型最適化アルゴリズム ====
-凸最適化問題を解くための非集中型アルゴリズムは、[[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システムネットワークでの記憶容量割り当て]]など、多くの応用例を持ちます) に適用可能な分散型最適化アルゴリズムの開発が待たれていました。+凸最適化問題を解くための非集中型アルゴリズムは、[[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://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 (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.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]]: [[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.
行 45: 行 46:
 これまでの研究では、このような既存法のアイデアを活用することで制約付き最適化に関する幾つかのアルゴリズムとその収束解析について提案することができています。 これまでの研究では、このような既存法のアイデアを活用することで制約付き最適化に関する幾つかのアルゴリズムとその収束解析について提案することができています。
 ==== 非集中型最適化アルゴリズム ==== ==== 非集中型最適化アルゴリズム ====
-  * K. Hishinuma and [[:iiduka:|H. Iiduka]]: 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 (accepted) +  * 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.  
-  * [[: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 (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.   * [[: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. +  * 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.   * [[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/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.
行 69: 行 73:
 上記の最適化アルゴリズムのアイデアを組み合わせることにより、非集中型最適化アルゴリズムを提案しています。 上記の最適化アルゴリズムのアイデアを組み合わせることにより、非集中型最適化アルゴリズムを提案しています。
   * [[: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.   * [[: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.
 +
  • intro/researches/optimization.1561792960.txt.gz
  • 最終更新: 2019/06/29 16:22
  • by Hideaki IIDUKA