凸可行问题的松弛投影算法及其应用研究

The convex feasibility problem (CFP) is a common and important class of mathematical problems, which has a very strong application background and has a wide range of applications in the field of modern physics, medical, signal processing, image reconstruction, game theory and so on. Therefore, it has important theoretical significance and notable value to design effective algorithms for the convex feasibility problem. This project is to give a systematic and in-depth study of relaxed projection algorithm for solving the convex feasibility problem. It has the following specific research contents: (1)theoretical analysis of the convex feasibility problem, including the regeneration form, the structure and features of solutions; (2) to construct the new projection region or set which is easy to projection and establish some new feasible effective relaxation projection algorithms for solving the convex feasible problem, especially the effective new algorithms with fast convergence, and give theoretical analysis for the algorithms presented in this project mentioned above; (3) collect some typical instances in signal processing, image reconstruction and game theory and give model analysis for these instances. Then attempt to solve these problems by the new algorithms proposed in this project and try to design some feasible mumerical algorithmic programmes.

凸可行问题是一类常见而又重要的数学问题，有着极强的应用背景，在现代物理、医学、信号处理、图像重建、博弈论等领域中都有着广泛的应用. 因此，对凸可行问题设计有效的算法，具有重要的理论意义与显著的应用价值. 本项目就是对求解凸可行问题的松弛投影算法进行系统和深入的研究. 具体研究内容是：(1) 凸可行问题的理论分析，包括再生形式、解的结构、解的特征等；(2)构造易于投影的投影区域(集合)，建立求解凸可行问题的可行有效的松弛投影新算法，特别是具有快速收敛的有效新算法，并进行算法的理论分析；(3)收集信号处理、图像重建和博弈论中的典型实例，对它们进行模型分析，并尝试应用新算法求解. 编制数值算法程序.

凸可行问题是一类常见而又重要的数学问题，有着极强的应用背景，对凸可行问题设计有效的算法，具有重要的理论意义与显著的应用价值. 本项目按照预期计划，对求解凸可行问题的松弛投影算法进行系统和深入的研究，主要得到了如下研究结果：1.在求解凸可行问题（分裂可行问题）的快速收敛的算法设计上，我们分析了分裂可行问题的一个价值函数的性质，提出了一种具有超线性收敛的Newton投影方法；然后用投影算子将分裂可行问题转化为一个带凸约束的半光滑方程，又给出了一个具有超线性收敛的光滑SQP算法．值得提出的是，目前我们尚未见到有关解决分裂可行问题的投影类算法具有超线性收敛速率的文献．2.在凸可行问题（分裂可行问题）的松弛投影算法设计上，我们从减少算法的计算量考虑，设计出一种简单易行的CQ类算法及其松弛形式，其步长可直接根据先前迭代点的信息计算出来，而不需要计算相关矩阵的逆矩阵、特征值，也不需要任何的线性搜索．这些算法，大大减少了求解问题的计算量．3.在对带锥约束的凸可行问题的算法设计上，提出了一种新的半空间松弛投影方法，该算法有两点优势：一方面，在构造所涉及到的半空间时，只需要根据当前迭代点的信息，而不再需要求次梯度，使得算法相对容易执行；另一方面，算法所涉及的目标函数是对原先目标凸函数的松弛，这样，相关的投影更容易计算． 4.在带稀疏约束的凸可行问题的算法设计上，通过凸松弛将其转化为一个凸可行问题后，设计了如下求解方法：（1）投影算法；（2）松弛投影算法；（3）无约束优化算法．5.在凸可行问题（分裂可行问题）应用的研究上：我们主要考虑了压缩传感问题的求解．分别将其等价转化为一个分裂可行问题和一个凸可行问题的基础上，分别设计了合适的松弛投影算法来求解．6.另外，我们还对与凸可行问题（分裂可行问题）的相关问题进行了研究，如拟变分不等式问题、非凸半无限极大极小问题、罚函数、非线性互补问题等，得到了若干有意义的结果．