条件梯度法求解非线性分裂可行问题
Solving Nonlinear Split Feasibility Problem via Conditional Gradient Method
摘要: 本文研究了分裂可行问题的条件梯度算法，该算法将求解迭代方向转化成求解一线性子问题，并以线搜索得到的步长作为凸因子，当前方向与上一步迭代点的凸组合作为新的迭代点。算法在迭代的更新步中不使用投影，并且得到的解有较好的稀疏性和低秩性。我们获得了算法的收敛性并给出数值实验对比分析了本文的算法与相关算法在同一算例下的表现情况，得到了良好的结果。
Abstract: In this paper, we consider a conditional gradient algorithm for the split feasibility problem. We get the iterative direction by solving a linear subproblem, use the step size obtained by the line search as the convex factor, and get the new iteration point by the convex combination of the current direction and the previous step iteration point. The algorithm does not use projection in the update step. And the obtained solution has good properties of sparsity and low rank. The numerical experiment compares the performance of the proposed algorithm with other algorithms under the same calculation example.
文章引用：宇振盛, 王子伦. 条件梯度法求解非线性分裂可行问题[J]. 应用数学进展, 2020, 9(9): 1652-1663. https://doi.org/10.12677/AAM.2020.99192

参考文献

[1] Censor, Y. and Elfving, T. (1994) A Multiprojection Algorithm Using Bregman Projections in a Product Space. Numerical Algorithms, 8, 221-239. [Google Scholar] [CrossRef] 
[2] Censor, Y., Elfving, T., Kopf, N. and Bortfeld, T. (2005) The Multiple-Sets Split Feasibility Problem and Its Applications for Inverse Problems. Inverse Problems, 21, 2071-2084. [Google Scholar] [CrossRef] 
[3] Censor, Y., Bortfeld, T., Martin, B. and Trofimov, A. (2006) A Unified Approach for Inversion Problems in Intensity-Modulated Radiation Therapy. Physics in Medicine & Biology, 51, 2353-2365. [Google Scholar] [CrossRef] [PubMed]
[4] Byrne, C. (2003) A Unified Treatment of Some Iterative Algorithms in Signal Processing and Image Reconstruction. Inverse Problems, 20, 103-120. [Google Scholar] [CrossRef] 
[5] Xu, H.-K. (2014) Properties and Iterative Methods for the Lasso and Its Variants. Chinese Annals of Mathematics, Series B, 35, 501-518. [Google Scholar] [CrossRef] 
[6] He, H.J. and Xu, H.-K. (2017) Splitting Methods for Split Feasibility Problems with Application to Dantzig Selectors. Inverse Problems, 33, Article ID: 055003. [Google Scholar] [CrossRef] 
[7] Byrne, C. (2002) Iterative Oblique Projection onto Convex Sets and the Split Feasibility Problem. Inverse Problems, 18, 441-453. [Google Scholar] [CrossRef] 
[8] Guélat, J. and Marcotte, P. (1986) Some Comments on Wolfe’s “Away Step”. Mathematical Programming, 35, 110-119. [Google Scholar] [CrossRef] 
[9] Shang, M. and Zhang, C. and Xiu, N.H. (2014) Minimal Zero Norm Solutions of Linear Complementarity Problems. Journal of Optimization Theory and Applications, 163, 795-814. [Google Scholar] [CrossRef] 
[10] Byrne, C., Censor, Y., Gibali, A. and Reich, S. (2012) The Split Common Null Point Problem. Journal of Nonlinear and Convex Analysis, 13, 759-775.
[11] Masad, E. and Reich, S. (2007) A Note on the Multiple-Set Split Convex Feasibility Problem in Hilbert Space. Journal of Nonlinear and Convex Analysis, 8, 367-371.
[12] Krasnoselskii, M.A. (1955) Two Remarks about the Method of Successive Approximations. Uspekhi Matematicheskikh Nauk, 10, 123-127.
[13] Robert, M.W. (1953) Mean Value Methods in Iteration. Proceedings of the American Mathematical Society, 4, 506-510. [Google Scholar] [CrossRef] 
[14] Xu, H.-K. (2006) A Variable Krasnosel’skii-Mann Algorithm and the Multiple-Set Split Feasibility Problem. Inverse Problems, 22, 2021. [Google Scholar] [CrossRef] 
[15] Li, Z.B., Han, D.R. and Zhang, W.X. (2013) A Self-Adaptive Projection-Type Method for Nonlinear Multiple-Sets Split Feasibility Problem. Inverse Problems in Science and Engineering, 21, 155-170. [Google Scholar] [CrossRef] 
[16] Gibali, A., Küfer, K.H. and Süss, P. (2014) Successive Linear Programing Approach for Solving the Nonlinear Split Feasibility Problem. Journal of Nonlinear and Convex Analysi, 15, 345-353.
[17] Xu, J., Chi, E.C., Yang, M. and Lange, K. (2018) A Majorization-Minimization Algorithm for Split Feasibility Problems. Computational Optimization and Applications, 71, 795-828. [Google Scholar] [CrossRef] 
[18] 畅含笑, 孙军, 屈彪. 带稀疏约束的分裂可行问题的算法[J]. 应用数学进展, 2016, 5(2): 269-275.
[19] Censor, Y., Gibali, A. and Reich, S. (2012) Algorithms for the Split Variational Inequality Problem. Numerical Algorithms, 59, 301-323. [Google Scholar] [CrossRef] 
[20] Frank, M. and Wolfe, P. (1956) An Algorithm for Quadratic Programming. Naval Research Logistics Quarterly, 3, 95-110. [Google Scholar] [CrossRef] 
[21] Freund, R.M. and Grigas, P. (2016) New Analysis and Results for the Frank-Wolfe Method. Mathematical Programming, 155, 199-230. [Google Scholar] [CrossRef] 
[22] Goncalves, M.L.N. and Melo, J.G. (2017) A Newton Conditional Gradient Method for Constrained Nonlinear Systems. Journal of Computational and Applied Mathematics, 311, 473-483. [Google Scholar] [CrossRef] 
[23] Jaggi, M. (2013) Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. Proceedings of the 30th International Conference on Machine Learning, Atlanta, 17-19 January 2013, 427-435.
[24] Hearn, D.W. (1982) The Gap Function of a Convex Program. Operations Research Letters, 1, 67-71. [Google Scholar] [CrossRef] 
[25] Bauschke, H.H. and Borwein, J.M. (1996) On Projection Algorithms for Solving Convex Feasibility Problems. SIAM Review, 38, 367-426. [Google Scholar] [CrossRef] 

为你推荐