[00133639]最优化中交替方向类收缩算法的研究

课题来源与背景：本课题来源于国家自然科学基金资助下的自选课题1.项目名称：社会计算问题与逆变分不等式求解,项目编号：10971095;2.项目名称：问题驱动的大型优化问题的可计算建模与算法探索,项目编号：91130007,主要研究大型优化问题的建模与求解方法。近年来,在信号处理、计算机视觉、矩阵完整化、机器学习等信息科学的诸多分支中,涌现出大量的大型最优化问题。最近两届世界数学家大会的邀请报告人 S.Boyd 和 S.Osher 都对求解这些问题格外重视。这些问题往往具有可分离结构且维数较高,如何利用问题的结构特点设计高效且易实现的算法,需要有新的思想和方法。 研究目的与意义： 1)研究问题驱动的大型优化问题的结构特点,尤其是针对具有分离结构的优化问题,提出有效的数值求解方法。 2)对提出的算法,分析其在最坏情况下计算时间与精度的关系,研究计算复杂性。3)将提出的算法推广应用到求解更广泛的问题驱动的大型优化问题上。 主要论点与论据： 1)约束最优化问题的一阶最优性条件是一个变分不等式。在变分不等式的框架指导下研究优化问题的求解方法,简单清晰,同时极大地简化了收敛性证明。 2)收缩思想对算法收敛性给出了统一的准则,本课题提出了在一个简单统一的框架内研究求解优化问题的数值算法。 3)对所提出的方法,分析其在最坏情况下计算时间与精度的关系,证明了O（1/t）的计算复杂性。 创见与创新： 1)采用交替方向式的分裂算法,把难于解决的大问题分解成一系列能够容易求解的子问题。在求解每个子问题的时候尽可能利用已有信息,根据“分解降低难度,整合把握方向”的原理,构造距离函数的下降方向。 2)利用回代法则,对多个算子的可分离凸优化问题,给出了基于交替方向的收缩算法。对多个算子的问题,这是至今唯一的基于交替方向、不需任何额外条件并具有收敛性保证的方法。 技术的成熟程度：交替方向法,原始—对偶混合梯度的邻近点算法（PDHG—PPA）已经成为求解大型可分离结构优化问题的主要工具。 应用情况：该课题研究的是普适性方法,在机器学习、图像处理等方面有广泛的应用。在国际上,被包括美国两院院士、加州大学伯克利分校、加州大学洛杉矶分校等北美名校的教授用来解决有关问题。也被诸如宾夕法尼亚大学、多伦多大学、哥伦比亚大学等大学的博士们在语音识别、光纤网络等研究中采用。在国内,这类算法也被有关课题组成功应用到机器人的运动规划和实时控制中。 历年获奖情况： 1.成果完成人袁晓明获香港浸会大学2013年the President’s Award for Outstanding Young Researcher（每年全校1至2名） 2.成果完成人韩德仁2010年获中国运筹学会运筹学青年科技二等奖