稀疏线性规划研究

来源：计算数学杂志2018年第4期北京时间：

作者：陈圣杰, 戴彧虹, 徐凤敏

单位：1. 中国科学院数学与系统科学研究院, 北京 100190;\r\n2. 中国科学院大学数学科学学院, 北京 100049;\r\n3. 西安交通大学经济与金融学院, 西安 710049

摘要：稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题；其次采用交替方向乘子法（ADMM）求解该问题；最后证明了算法在近似问题上的收敛性.数值实验表明，算法在大规模数值算例上的表现优于已有的混合遗传算法；同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.

关键词：稀疏线性规划,非凸优化,NP困难,交替方向乘子法,收敛性分析

基金资助：<p>国家973项目（2015CB856002），国家自然科学基金重点项目（11631013），国家自然科学基金（11571271）.</p>