非凸锥优化理论算法及其在蛋白质分类的应用研究

本项目旨在探索和研究非凸优化问题锥优化模型的对偶理论、具有多项式时间内点算法及其在蛋白质同源性探测和分类问题的应用。锥优化是解决非凸优化问题的强有力工具，其主要特点是把受限制的、不可计算的和不可变尺度的非凸难问题变换或松弛成连续的、可计算的和可变换尺度的凸优化问题。理论上，我们研究带锥约束非凸优化问题的对偶理论、可行域几何结构的代数表示和参数表示、锥优化松弛方法和技术分析与比较。算法上，设计具有多项式和强多项式时间的内点算法、分析松弛界与原问题解的误差、计算参数鲁棒性、对偶间隙、松弛界对计算复杂性的控制和影响。应用上，我们根据已知蛋白质样本的生物结构和功能，建立计算规模适中、分类精准率高的锥优化模型和算法，应用于识辨和探测未知蛋白质序列的同源性结构和功能，为生物信息学提供方法和工具。本项目研究课题以问题为驱动，属于最优化理论方法在生物信息学的交叉应用研究，具有重要科学意义和应用价值。

本项目探索和研究非凸二次规划问题的锥优化模型等价转化和松弛模型、有效内点算法以及应用研究。众所周知，非凸二次规划问题具有简单的优化模型表达形式、并能广泛的表述实际问题。然而，很多非凸二次规划问题是NP-hard计算问题。 我们研究的方法是把非凸二次规划问题的凸锥优化等价转化和松弛离散的、受限制的和不可变尺度的非凸难问题转化或提升到高维空间连续的、松弛的、可变换尺度的和可计算的凸锥优化问题。在理论方面的进展是，研究了通过提升技术把几个可用非凸二次规划表示的问题，如蛋白质分类问题、多目标投资组合问题、投资风险管理问题转化成高维空间的等价凸锥优化问题，即目标是线性函数、约束锥是协正锥(copositve cone)或者是完全正锥(completely positive cones)的凸锥优化问题。由于尽管这个约束锥规划问题可以与原问题等价，但于非凸可计算难度被嵌入了协正锥或完全正锥内部里， 即验证一个元素是否属于协正锥依然保持了NP难问题。因此, 研究的第二步是找协正锥和完全正锥的近似锥, 我们用双非负锥(Doubly nonnegative cone) 和半正定锥近似或替代协正锥和完全正锥。研究的第三步是研究原问题被转化后，对协正锥和完全正锥约束的松弛后的误差界估计以及对偶理论、可行域几何结构的代数表示和参数表示、锥优化松弛方法和技术分析与比较。在有效内点算法研究和设计中，我们设计具有多项式时间的内点算法、分析松弛界与原问题解的误差、计算参数鲁棒性、对偶间隙、松弛界对计算复杂性的控制和影响。应用上，我们根据已知蛋白质样本的生物结构和功能，建立计算规模适中、分类精准率高的锥优化模型和算法，把锥优化模型应用到蛋白质同源性探测中的应用分类问题上。 对于实际问题，我们选取了UCI Repository 的实际算例进行了数值试验. 试验结果表明，给出的等价和松弛地模型在分类问题准确性比较显著。但我们也认识到模型的局限性，主要是对大规模分类问题计算效果不明显，没有目前流行的ADMM算法效果好，我们分析了原因，主要是局限在内点算法的内核算法上。本项目的研究成果以论文的形式体现，包括24期刊论文，其中15篇研究论文进入运筹与优化领域SCI 检索的国际期刊、其中3篇研究论文发表在优化领域的高水平期刊上。其余的9篇研究论文分别发表在应用数学、运筹学的中文核心期刊上。