|
|||||
|
|
| 稀疏线性规划研究 | |
| 引用本文： | 陈圣杰,戴彧虹,徐凤敏. 稀疏线性规划研究[J]. 计算数学, 2018, 40(4): 339-353 |
| 作者姓名： | 陈圣杰 戴彧虹 徐凤敏 |
| 作者单位： | 1. 中国科学院数学与系统科学研究院, 北京 100190; 2. 中国科学院大学数学科学学院, 北京 100049; 3. 西安交通大学经济与金融学院, 西安 710049 |
| 基金项目： | 国家973项目（2015CB856002），国家自然科学基金重点项目（11631013），国家自然科学基金（11571271）. |
| 摘 要： | 稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性. |
| 关 键 词： | 稀疏线性规划 非凸优化 NP困难 交替方向乘子法 收敛性分析 |
ON THE STUDY OF SPARSE LINEAR PROGRAMMING |
|
| Chen Shengjie,Dai Yuhong,Xu Fengmin. ON THE STUDY OF SPARSE LINEAR PROGRAMMING[J]. Mathematica Numerica Sinica, 2018, 40(4): 339-353 | |
| Authors: | Chen Shengjie Dai Yuhong Xu Fengmin |
| Affiliation: | 1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; 2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China; 3. School of Economics and Finance, Xi'an Jiaotong University, Xi'an 710049, China |
| Abstract: | Sparse linear programming is widely used in computational finance, industrial production, assembly scheduling and other fields. This paper proposes the general model of sparse linear programming problem and shows that the problem is NP-hard. Then we use alternating direction method of multipliers (ADMM) to solve it and prove the convergence of the algorithm in the approximate form. Numerical experiments show that the ADMM algorithm performs better than the hybrid genetic algorithm for large-scale numerical examples. Meanwhile, the good performance of the algorithm in financial cases verifies the validity of the algorithm and the model for solving sparse portfolio problems. |
| Keywords: | sparse linear programming non-convex optimization NP-hard alternating direction method of multipliers convergence analysis |
| 本文献已被 CNKI 等数据库收录！ | |
| 点击此处可从《计算数学》浏览原始摘要信息 | |
| 点击此处可从《计算数学》下载全文 | |