差分

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

この比較画面へのリンク

intro:researches:optimization [2020/02/21 10:51] – [非集中型最適化アルゴリズム] 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|信号復元問題]]、[[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|(非平滑凹満足度指標をもつ)帯域幅割り当て問題]]といった実用的な応用問題を例として含んでいます。   - **非平滑凸最適化問題 (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|分数計画問題]]といった実用的な応用問題を例として含んでいます。
  
 上記の問題を解決するための最適化アルゴリズムには、「集中型」と「非集中型」の最適化アルゴリズムが挙げられます。 上記の問題を解決するための最適化アルゴリズムには、「集中型」と「非集中型」の最適化アルゴリズムが挙げられます。
行 45: 行 46:
 これまでの研究では、このような既存法のアイデアを活用することで制約付き最適化に関する幾つかのアルゴリズムとその収束解析について提案することができています。 これまでの研究では、このような既存法のアイデアを活用することで制約付き最適化に関する幾つかのアルゴリズムとその収束解析について提案することができています。
 ==== 非集中型最適化アルゴリズム ==== ==== 非集中型最適化アルゴリズム ====
-  * K. Shimizu, K. Hishinuma, [[:iiduka:|H. Iiduka]]: Parallel Computing Proximal Method for Nonsmooth Convex Optimization with Fixed Point Constraints of Quasi-nonexpansive Mappings, submitted  +  * 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]]: Incremental Proximal Method for Nonsmooth Convex Optimization with Fixed Point Constraints of Quasi-nonexpansive Mappings, Linear and Nonlinear Analysis (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 (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, Vol. 6, No. 4, pp. 1354-1365, 2019. 
-  * 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, Vol. 20, No. 9, pp.1937-1947, 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.    * 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.
行 71: 行 72:
 ==== 非集中型最適化アルゴリズム ==== ==== 非集中型最適化アルゴリズム ====
 上記の最適化アルゴリズムのアイデアを組み合わせることにより、非集中型最適化アルゴリズムを提案しています。 上記の最適化アルゴリズムのアイデアを組み合わせることにより、非集中型最適化アルゴリズムを提案しています。
-  * 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. 
   * [[: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.1582249881.txt.gz
  • 最終更新: 2020/02/21 10:51
  • by Hideaki IIDUKA