• 论文 • 上一篇    下一篇

稀疏线性规划研究

陈圣杰1,2, 戴彧虹1,2, 徐凤敏3   

  1. 1. 中国科学院数学与系统科学研究院, 北京 100190;
    2. 中国科学院大学数学科学学院, 北京 100049;
    3. 西安交通大学经济与金融学院, 西安 710049
  • 收稿日期:2017-12-30 出版日期:2018-12-15 发布日期:2018-11-20
  • 通讯作者: 徐凤敏,Email:fengminxu@mail.xjtu.edu.cn
  • 基金资助:

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

陈圣杰, 戴彧虹, 徐凤敏. 稀疏线性规划研究[J]. 计算数学, 2018, 40(4): 339-353.

Chen Shengjie, Dai Yuhong, Xu Fengmin. ON THE STUDY OF SPARSE LINEAR PROGRAMMING[J]. Mathematica Numerica Sinica, 2018, 40(4): 339-353.

ON THE STUDY OF SPARSE LINEAR PROGRAMMING

Chen Shengjie1,2, Dai Yuhong1,2, Xu Fengmin3   

  1. 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
  • Received:2017-12-30 Online:2018-12-15 Published:2018-11-20
稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.
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.

MR(2010)主题分类: 

()
[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] 古振东, 孙丽英. 非线性第二类Volterra积分方程的Chebyshev谱配置法[J]. 计算数学, 2020, 42(4): 445-456.
[2] 王志强, 文立平, 朱珍民. 时间延迟扩散-波动分数阶微分方程有限差分方法[J]. 计算数学, 2019, 41(1): 82-90.
[3] 徐薇, 吴钰炜, 陈彩华. 基于交替方向乘子法的大规模线性多商品流问题求解算法[J]. 计算数学, 2018, 40(4): 436-449.
[4] 姜帆, 刘雅梅, 蔡邢菊. 一类自适应广义交替方向乘子法[J]. 计算数学, 2018, 40(4): 367-386.
[5] 郭科, 韩德仁. 单调算子理论与分裂算法[J]. 计算数学, 2018, 40(4): 418-435.
[6] 古振东, 孙丽英. 一类弱奇性Volterra积分微分方程的级数展开数值解法[J]. 计算数学, 2017, 39(4): 351-362.
[7] 刘丽华, 马昌凤, 唐嘉. 求解广义鞍点问题的一个新的类SOR算法[J]. 计算数学, 2016, 38(1): 83-95.
[8] 黄娜, 马昌凤, 谢亚君. 求解非对称代数Riccati 方程几个新的预估-校正法[J]. 计算数学, 2013, 35(4): 401-418.
[9] 任志茹. 三阶线性常微分方程Sinc方程组的结构预处理方法[J]. 计算数学, 2013, 35(3): 305-322.
[10] 陈绍春, 梁冠男, 陈红如. Zienkiewicz元插值的非各向异性估计[J]. 计算数学, 2013, 35(3): 271-274.
[11] 张亚东, 石东洋. 各向异性网格下抛物方程一个新的非协调混合元收敛性分析[J]. 计算数学, 2013, 35(2): 171-180.
[12] 陈争, 马昌凤. 求解非线性互补问题一个新的 Jacobian 光滑化方法[J]. 计算数学, 2010, 32(4): 361-372.
[13] 来翔, 袁益让. 一类三维拟线性双曲型方程交替方向有限元法[J]. 计算数学, 2010, 32(1): 15-36.
[14] 蔚喜军. 非线性波动方程的交替显-隐差分方法[J]. 计算数学, 1998, 20(3): 225-238.
阅读次数
全文


摘要