计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  重点论文 |  在线办公 | 
计算数学  2018, Vol. 40 Issue (4): 339-353    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
稀疏线性规划研究
陈圣杰1,2, 戴彧虹1,2, 徐凤敏3
1. 中国科学院数学与系统科学研究院, 北京 100190;
2. 中国科学院大学数学科学学院, 北京 100049;
3. 西安交通大学经济与金融学院, 西安 710049
ON THE STUDY OF SPARSE LINEAR PROGRAMMING
Chen Shengjie1,2, Dai Yuhong1,2, Xu Fengmin3
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
 全文: PDF (433 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词稀疏线性规划   非凸优化   NP困难   交替方向乘子法   收敛性分析     
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.
Key wordssparse linear programming   non-convex optimization   NP-hard   alternating direction method of multipliers   convergence analysis   
收稿日期: 2017-12-30;
基金资助:

国家973项目(2015CB856002),国家自然科学基金重点项目(11631013),国家自然科学基金(11571271).

通讯作者: 徐凤敏,Email:fengminxu@mail.xjtu.edu.cn     E-mail: fengminxu@mail.xjtu.edu.cn
引用本文:   
. 稀疏线性规划研究[J]. 计算数学, 2018, 40(4): 339-353.
. ON THE STUDY OF SPARSE LINEAR PROGRAMMING[J]. Mathematica Numerica Sinica, 2018, 40(4): 339-353.
 
[1] Zou H, Hastie T, Tibshirani R. Sparse Principal Component Analysis[J]. Journal of Computational & Graphical Statistics, 2006, 15(2):265-286.
[2] Wu M. A Direct Method for Building Sparse Kernel Learning Algorithms[M]. JMLR. org, 2006.
[3] Brodie J, Daubechies I, De M C, et al. Sparse and stable Markowitz portfolios[J]. Proceedings of the National Academy of Sciences of the United States of America, 2009, 106(30):12267.
[4] Tibshirani R. Regression shrinkage and selection via the lasso:a retrospective[J]. Journal of the Royal Statistical Society, 2011, 73(3):273-282.
[5] Efron B, Hastie T, Johnstone I, et al. Least angle regression[J]. Annals of Statistics, 2004, 32(2):407-451.
[6] Pan L L, Xiu N H, Fan J. Optimality conditions for sparse nonlinear programming[J]. Science China, 2017, 60(5):1-18.
[7] Lu Z, Zhang Y. Penalty Decomposition Methods for L0-Norm Minimization[J]. Mathematics, 2010.
[8] Lu Z, Zhang Y. Sparse Approximation via Penalty Decomposition Methods[J]. Siam Journal on Optimization, 2012, 23(4):2448-2478.
[9] Chen X, Lu Z, Pong T K. Penalty methods for a class of non-Lipschitz optimization problems[J]. Mathematics, 2016, 26(3):1465-1492.
[10] Ruiztorrubiano R. Cardinality constraints and dimensionality reduction in optimization problems[J]. Universidad Autónoma De Madrid, 2012.
[11] Karmarkar N. A new polynomial-time algorithm for linear programming[J]. Combinatorica, 1984, 4(4):373-395.
[12] 加里. 计算机和难解性[M]. 科学出版社, 1987.
[13] Guo K, Han D R, Wu T T. Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints[J]. International Journal of Computer Mathematics, 2016, 94(8):1-18.
[14] Duration W T S D S. The Method of Multipliers for Equality Constrained Problems-Constrained Optimization and Lagrange Multiplier Methods-Chapter 2[J]. Constrained Optimization & Lagrange Multiplier Methods, 1982, 95-157.
[15] Boyd S, Parikh N, Chu E, et al. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[J]. Foundations & Trends in Machine Learning, 2011, 3(1):1-122.
[16] Bai Y, Liang R, Yang Z. Splitting augmented Lagrangian method for optimization problems with a cardinality constraint and semicontinuous variables[J]. Optimization Methods and Software, 2016, 31(5):1089-1109.
[17] Ruiz-Torrubiano R, Suárez A. A hybrid optimization approach to index tracking[J]. Annals of Operations Research, 2009, 166(1):57-71.
[18] Xu F, Wang M, Dai Y H. A sparse enhanced indexation model with chance and cardinality constraints[J]. Journal of Global Optimization, 2017(3):1-21.
[19] Xu F, Dai Y H, Zhao Z, Xu Z. Efficient projected gradient methods for a class of L0 constrained optimization[J]. Science China Mathematics, 2017, 60(1):1-xx.
[20] Xu F, Lu Z, Xu Z. An efficient optimization approach for a cardinality-constrained index tracking problem[J]. Optimization Methods & Software, 2016, 31(2):258-271.
[21] Rockafellar R T, Uryasev S. Optimization of Conditional Value-at-Risk[J]. Journal of Risk, 2000, 29(1):1071-1074.
[22] Beasley J E. OR-Library:Distributing Test Problems by Electronic Mail[J]. Journal of the Operational Research Society, 1990, 41(11):1069-1072.
[1] 徐薇, 吴钰炜, 陈彩华. 基于交替方向乘子法的大规模线性多商品流问题求解算法[J]. 计算数学, 2018, 40(4): 436-449.
[2] 姜帆, 刘雅梅, 蔡邢菊. 一类自适应广义交替方向乘子法[J]. 计算数学, 2018, 40(4): 367-386.
[3] 郭科, 韩德仁. 单调算子理论与分裂算法[J]. 计算数学, 2018, 40(4): 418-435.
[4] 古振东, 孙丽英. 一类弱奇性Volterra积分微分方程的级数展开数值解法[J]. 计算数学, 2017, 39(4): 351-362.
[5] 乐航睿, 杨庆之. 求解正则化最小二乘问题的一个非精确交替方向乘子法[J]. 计算数学, 2016, 37(3): 223-232.
[6] 刘丽华, 马昌凤, 唐嘉. 求解广义鞍点问题的一个新的类SOR算法[J]. 计算数学, 2016, 38(1): 83-95.
[7] 黄娜, 马昌凤, 谢亚君. 求解非对称代数Riccati 方程几个新的预估-校正法[J]. 计算数学, 2013, 35(4): 401-418.
[8] 任志茹. 三阶线性常微分方程Sinc方程组的结构预处理方法[J]. 计算数学, 2013, 35(3): 305-322.
[9] 陈绍春, 梁冠男, 陈红如. Zienkiewicz元插值的非各向异性估计[J]. 计算数学, 2013, 35(3): 271-274.
[10] 张亚东, 石东洋. 各向异性网格下抛物方程一个新的非协调混合元收敛性分析[J]. 计算数学, 2013, 35(2): 171-180.
[11] 王风娟, 王同科. 一维抛物型方程第三边值问题的紧有限体积格式[J]. 计算数学, 2013, 34(1): 59-74.
[12] 陈争, 马昌凤. 求解非线性互补问题一个新的 Jacobian 光滑化方法[J]. 计算数学, 2010, 32(4): 361-372.
[13] 来翔, 袁益让. 一类三维拟线性双曲型方程交替方向有限元法[J]. 计算数学, 2010, 32(1): 15-36.
[14] 蔚喜军. 非线性波动方程的交替显-隐差分方法[J]. 计算数学, 1998, 20(3): 225-238.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10