一类求解约束离散不适定问题的积极集随机迭代方法

A Class of Active Set Randomized Iterative Methods for Solving Constrained Discrete Ill-Posed Problems

摘要:

许多科学和工程领域的应用问题都可以归结为线性离散不适定问题的求解。考虑大规模带盒子约束的线性离散不适定问题的求解，提出一类基于积极集策略的随机内外迭代方法。基于积极集策略的内外迭代法在外层迭代上更新积极集和对应的非积极集，并采用投影算子，将不在可行域中的数值解分量投影到可行域边界上，同时在内层迭代上采用Krylov子空间方法求解无约束子问题。提出一类积极集迭代法，在内层迭代上采用高性能随机算法，依照概率分布选取子问题系数矩阵的列进行更新，并利用Armijo下降准则对迭代步长进行选择，这样就可以保证目标函数值随着迭代步数的增加而单调下降。在图像复原问题的数值实验中，验证所构造算法的高效性。在偏差准则的收敛条件下，新的积极集内外迭代法所利用的计算量、迭代步数和CPU时间都比前人提出的算法更少。

Abstract:

Linear discrete ill-posed problems arise from many scientific computation and engineering application areas. Considering the solution to large scale ill-posed problems with box constraints， A novel class of randomized internal and external iterative methods are proposed based on the active set strategy， which contain a two-level iteration that， for the external iteration， updates the active set and free variable set， and orthogonally project the iterate onto the feasible boundary， while for the internal iteration， solves the unconstrained linear system with the Krylov subspace methods. The proposed novel active set algorithm is to utilize the efficient randomized method for the internal iteration and the step size is chosen by the Armijo criterion， so that the objective function value can be monotonically decreased with the increase of the number of iterations. Numerical experiments on the image restoration show the efficiency of the proposed algorithm. Under the condition of the discrepancy principle， the computational complexity， iteration steps， and CPU time of the novel active set randomized iteration methods are less than those of previous methods.