非凸可行问题的近似算法

目前，国内外学者对于分裂可行、凸可行等所涉集合或约束为凸的可行类问题已进行了深入的研究，并取得了许多研究成果；但是，由于技术和方法等所限，大量存在的非凸可行问题却尚未引起广泛研究，仅有少量研究成果。本项目主要研究非凸可行问题的松弛和近似算法。研究内容包括秩约束线性矩阵不等式（LMI）和秩约束双线性矩阵不等式（BMI）问题的SDP松弛、SOCP松弛和其它近似算法，作出相应的收敛性分析，给出逼近界，并进行数值试验对各种算法进行比较；以及建立其它非凸可行问题的SDP松弛、SOCP松弛等近似算法，并针对非凸可行问题自身的特点，研究新的求解方法。这一课题的研究，对于非凸优化问题的可行解、图像重构、医疗影像、逼近理论领域，以及控制理论中包括鲁棒控制和系统稳定性等在内的许多问题的更好解决，都有着重大的影响。因而，本项目的研究既具有重要的理论意义，又具有广泛的应用前景。

可行类问题在研究最优化问题的可行解、图像重构、医疗影像、可调强度放射性治疗、逼近理论领域，以及控制理论中包括鲁棒控制和系统稳定性等在内的许多领域中都有着广泛的应用。在本项目执行期内，我们深入研读和讨论了大量有关于凸可行问题、分裂可行问题、多集分裂可行问题以及非凸可行问题的文献资料，并主要致力于多集分裂可行问题的投影算法研究与改进。受到文献[P. Tseng, A modified forward–backward splitting method for maximal monotone mappings, SIAM J. Control Optim. 38 (2000): 431–446]中求解极大单调算子零点问题的改进Forward- backward分裂方法的启发，改进了由C. Byrne提出的求解分裂可行问题的经典而有效的CQ算法，加快收敛速度；同时考虑到CQ算法中迭代步长是固定的，其取值范围受到矩阵谱半径的限制，而谱半径，即最大特征值的获取在数值计算中一直被认为是有困难的，故而我们把固定步长改进为自适应步长（变步长）的形式，给出了算法收敛性证明，并对之进行了初步的数值检验，并进一步将这样的方法推广应用于多集分裂可行问题上。此后，我们考虑到投影算法的收敛速度问题，将主要精力集中于多集分裂可行问题的有关算法的搜索方向与搜索步长的改造上。首先，由于自适应投影算法中，每步迭代为求得合适的迭代步长都需要不少的计算量，故而我们将当前迭代点及其像点分别向各凸集进行投影，将从各点到相应投影点的方向进行凸组合以得到迭代方向，进而利用该方向直接计算出迭代步长，这种直接计算步长的方法避免了算法迭代中大量的内循环，从而使得算法效率得到改善，我们也从理论上验证了这样计算步长的方式相应于当前迭代方向是最好的；与此同时，我们还在迭代步中引入了松弛因子，以期进一步提高算法的收敛速度。初步的数值试验结果表明，我们的算法是简单而且有效的。此外，我们也针对特定的多集分裂可行问题研究了这一算法相应的松弛投影算法，通过引入向包含各凸集的半空间投影使得该算法更具有实用性。相应研究结果均已发表。.总体来说，本项目组老师和学生共计发表SCI检索论文8篇和中文核心期刊论文2篇（均已作资助标注）；曾多次参加学术会议进行交流活动；此外，项目负责人三年内还指导了7名本科生做毕业设计，并协助指导了3名研究生。