网站地图 | 联系我们 | English | 意见反馈 | 主任信箱
 
首页 中心概况 新闻动态 科研进展 交流合作 人才培养 研究队伍 人才招聘 政策规章 数学交叉科学传播
科研进展
科研成果
研究专题
获奖
现在位置:首页 > 科研进展 > 科研成果
非多面体矩阵优化的扰动性分析研究
【打印】【关闭】

2016-07-20 | 编辑:文\信息技术部 丁超

优化问题的扰动分析是数学规划中的一个重要的本质数学问题。研究优化问题在系统参数发生扰动时解的稳定性为设计有效的求解算法,分析算法的收敛性计算复杂度提供了重要的理论基础。众所周知,一般优化问题的解往往是不唯一的,直到上世纪70年代,由S.M. Robinson (Dantzig奖获得者,INFORMS前主席) 为代表的研究者才给出了关于最优解随变量变化的类Lipschitz性质的严格定义。其中,关于刻画KKT解的Robinson强正则性 (Robinson’s strong regularity),Aubin性质 (Aubin property) 和鲁棒孤立平稳性 (Robust isolated calmness) 是研究优化问题稳定性的重要理论方向。

一般非线性规划的扰动分析理论得到了R.T. Rockafellar (Dantzig奖与von Neumann理论奖获得者)、A.L. Dontchev、A. Shapiro等知名优化专家的关注。目前针对非线性规划的扰动性理论已被研究的比较透彻了。特别的,在上世纪末本世纪初,R.T. Rockafellar、A.L. Dontchev、M.S. Gowda以及A.B. Levy在相关的论文中相继证明了在非线性规划中Robinson强正则性与Aubin性质是等价的,并且给出鲁棒孤立平稳性的等价数学刻画。

值得注意的是,在非线性规划的扰动分析中,多面体锥的分片线性都起到了至关重要的作用。一旦缺少了这一性质,相应的理论分析就变得异常困难。另一方面,随着近来大数据科学大迅猛发展,大规模矩阵优化问题(例如半正定规划问题)在实际应用如压缩感知、机器学习、图像处理等领域变得越来越重要。然而,由于矩阵优化问题往往是非多面体的,因此相应的扰动性分析理论一直是悬而未决的公开问题。

对于一般非线性非多面体的可约锥优化问题,信息技术部的丁超与合作者给出了KKT解随参数变化的鲁棒孤立平稳性 (Robust isolated calmness) 的完整数学刻画,证明了鲁棒孤立平稳性等价于相应优化问题的二阶充分性条件(SOSC)和严格Robinson约束品性 (SRCQ) 成立。此外,相关结果为研究一般非线性非多面体的可约锥优化问题KKT解的Robinson强正则性和Aubin性质的数学刻画与相互关系提供了重要启示 (参见图1)。这一结果得到了SIAM J. Optimization的副主编与审稿专家的高度评价。他们一致认为此项工作在非多面体锥优化扰动性分析理论方面取得了突破性进展,所取得的结果与采用的方法开启了进一步研究其他扰动性理论的大门。

图1 一般非线性非多面体的可约锥优化问题KKT解的三种类Lipschitz性质。

欢迎访问国家数学与交叉科学中心 
地址:北京海淀区中关村东路55号 邮编:100190 电话: 86-10-62613242 Fax: 86-10-62616840 邮箱: ncmis@amss.ac.cn