Article Contents
Article Contents

# Sparse probabilistic Boolean network problems: A partial proximal-type operator splitting method

• * Corresponding author: Zheng Peng
The work is supported by NSFC grants 11571074, 11726505, and the Natural Science Foundation of FuJian Province grant 2015J01010.
• The sparse probabilistic Boolean network (SPBN) model has been applied in various fields of industrial engineering and management. The goal of this model is to find a sparse probability distribution based on a given transition-probability matrix and a set of Boolean networks (BNs). In this paper, a partial proximal-type operator splitting method is proposed to solve a separable minimization problem arising from the study of the SPBN model. All the subproblem-solvers of the proposed method do not involve matrix multiplication, and consequently the proposed method can be used to deal with large-scale problems. The global convergence to a critical point of the proposed method is proved under some mild conditions. Numerical experiments on some real probabilistic Boolean network problems show that the proposed method is effective and efficient compared with some existing methods.

Mathematics Subject Classification: Primary: 90B15, 90C52; Secondary: 90C90.

 Citation:

• Figure 1.  The probability distribution $x$ for the case $j = 2$ and $l = 2$

Figure 2.  The probability distribution $x$ for the case $j = 2$ and $l = 3$

Figure 3.  The probability distribution $x$ for the case $j = 3$ and 1024 BNs

Figure 4.  The probability distribution $x$ for the case $j = 3$ and 2048 BNs

Figure 5.  The probability distribution $x$ for the case $j = 4$ and 4096 BNs

Table 1.  The computational results of Algorithm 1 with different stopping error

 Stopping error $\varepsilon$ $10^{-2}$ $10^{-3}$ $5\times 10^{-4}$ $10^{-4}$ $5\times 10^{-5}$ $10^{-5}$ Total iteration number $k$ 97 260 267 520 562 722 Identified major BNs 104 118 189 118 118 118 118 118 358 360 360 360 360 360 360 395 395 395 395 395 376 594 594 594 594 594 395 836 836 836 836 836 594 911 911 911 911 911 836 939 939 939 939 939 911 939
•  [1] Y.-Q. Bai and K.-J. Shen, Alternating direction method of multipliers for $\ell1-\ell 2$ regularized Logistic regression model, Journal of the Operations Research Society of China, 4 (2016), 243-253.  doi: 10.1007/s40305-015-0090-2. [2] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2010), 1-122. [3] M. Caetano and T. Yoneyama, An autocatalytic network model for stock markets, Physica A, 419 (2015), 122-127.  doi: 10.1016/j.physa.2014.10.052. [4] X. Chen, W.-K. Ching and X.-S. Chen, Construction of probabilistic boolean networks from a prescribed transition probability matrix: A maximum entropy rate approach, East Asian Journal on Applied Mathematics, 1 (2011), 132-154.  doi: 10.4208/eajam.080310.200910a. [5] X. Chen, H. Jiang and W.-K. Ching, Construction of sparse probabilistic boolean networks, East Asian Journal of Applied Mathematics, 2 (2012), 1-18.  doi: 10.4208/eajam.030511.060911a. [6] Y.-H. Dai, D.-R. Han, X.-M. Yuan and W.-X. Zhang, A sequential updating scheme of Lagrange multiplier for separable convex programming, Mathematics of Computation, 86 (2017), 315-343.  doi: 10.1090/mcom/3104. [7] J. Eckstein and M. Fukushima, Some reformulations and applications of the alternating direction method of multipliers, in Large Scale Optimization: State of the Art Springer US, (1994), 115-134. [8] M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Computational Optimization and Applications, 1 (1992), 93-111.  doi: 10.1007/BF00247655. [9] J.-W. Gu, W.-K. Ching, T.-K. Siu and H. Zheng, On modeling credit defaults: A probabilistic Boolean network approach, Risk and Decision Analysis, 4 (2013), 119-129. [10] D.-R. Han, X.-M. Yuan and W.-X. Zhang, An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Mathematics of Computation, 83 (2014), 2263-2291.  doi: 10.1090/S0025-5718-2014-02829-9. [11] B.-S. He and X.-M. Yuan, Alternating direction method of multipliers for linear programming, Journal of the Operations Research Society of China, 4 (2016), 425-436.  doi: 10.1007/s40305-016-0136-0. [12] B.-S. He, M. Tao and X.-M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22 (2012), 313-340.  doi: 10.1137/110822347. [13] I. Ivanov, R. Pal and E.-R. Dougherty, Dynamics preserving size reduction mappings for probabilistic Boolean networks, IEEE Transactions on Signal Processing, 55 (2007), 2310-2322.  doi: 10.1109/TSP.2006.890929. [14] K. Kobayashi and K. Hiraishi, An integer programming approach to optimal control problems in context-sensitive probabilistic Boolean networks, Automatica, 47 (2011), 1260-1264.  doi: 10.1016/j.automatica.2011.01.035. [15] K. Kobayashi and K. Hiraishi, A probabilistic approach to control of complex systems and its application to real-time pricing, Mathematical Problems in Engineering, Volume (2014), Art. ID 906717, 8 pp. doi: 10.1155/2014/906717. [16] K. Kobayashi and K. Hiraishi, Verification of real-time pricing systems based on probabilistic Boolean networks, Applied Mathematics, 7 (2016), Article ID: 70627, 14 pages. doi: 10.4236/am.2016.715146. [17] J. Li, A. Ritter and D. Jurafsky, Inferring user preferences by probabilistic logical reasoning over social networks, preprint, arXiv: 1411.2679. [18] R. Liang, Y. Qiu and W.-K. Ching, Construction of probabilistic Boolean network for credit default data, Computational Sciences and Optimization (CSO), 2014 Seventh International Joint Conference on. IEEE, (2014), 11-15. [19] 2003. Available from: http://code.google.com/p/pbn-matlab-toolbox. [20] B.-K. Natraajan, Sparse approximation to linear systems, SIAM Journal on Computing, 24 (1995), 227-234.  doi: 10.1137/S0097539792240406. [21] Z. Peng and D.-H. Wu, A partial parallel splitting augmented Lagrangian method for solving constrained matrix optimization problems, Computers and Mathematics with Applications, 60 (2010), 1515-1524.  doi: 10.1016/j.camwa.2010.06.035. [22] B.-E. Rhoades, S. Sessa, M.-S. Khan and M. Swaleh, On fixed points of asymptotically regular mappings, Journal of the Australian Mathematical Society, 43 (1987), 328-346.  doi: 10.1017/S1446788700029621. [23] I. Shmulevich, E.-R. Dougherty, S. Kim and W. Zhang, Probabilistic Boolean networks: A rule- based uncertainty model for gene regulatory networks, Bioinformatics, 18 (2002), 261-274.  doi: 10.1093/bioinformatics/18.2.261. [24] I. Shmulevich, E-R. Dougherty and W. Zhang, From Boolean to probabilistic Boolean networks as models of genetic regulatory networks, Proceedings of the IEEE, 90 (2002), 1778-1792.  doi: 10.1109/JPROC.2002.804686. [25] I. Shmulevich, E.-R. Dougherty and W. Zhang, Gene perturbation and intervention in probabilistic Boolean networks, Bioinformatics, 18 (2002), 1319-1331.  doi: 10.1093/bioinformatics/18.10.1319. [26] B. Tian, X.-Q. Yang and K.-W. Meng, An interior-point $\ell_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization, Journal of Industrial & Management Optimization, 12 (2016), 949-973.  doi: 10.3934/jimo.2016.12.949. [27] X.-F. Wang and G. Chen, Complex networks: Small-world, scale-free and beyond, IEEE Circuits and Systems Magazine, 3 (2003), 6-20. [28] Z.-M. Wu, X.-J. Cai and D.-R. Han, Linearized block-wise alternating direction method of multipliers for multiple-block convex programming, Journal of Industrial & Management Optimization, 14 (2018), 833-855.  doi: 10.3934/jimo.2017078. [29] M.-H. Xu, Proximal alternating directions method for structured variational inequalities, Journal of Optimization Theory and Applications, 134 (2007), 107-117.  doi: 10.1007/s10957-007-9192-2. [30] Z.-B. Xu, H. Guo, Y. Wang and H. Zhang, The representation of $\ell_{\frac{1}{2}}$ regularizer among $\ell_q (0 < q < 1)$ regularizer: an experimental study based on phase diagram, Acta Automatica Sinica, 38 (2012), 1225-1228.  doi: 10.3724/SP.J.1004.2012.01225. [31] Z.-B. Xu, X.-Y. Chang, F.-M. Xu and H. Zhang, $\ell_{\frac{1}{2}}$ regularization: a thresholding representation theory and a fast slover, IEEE Transactions on Neural Networks and Learning Systems, 23 (2012), 1013-1027. [32] F.-M. Xu, Y.-H. Dai, Z.-H. Zhao and Z.-B. Xu, Efficient projected gradient methods for a class of $\ell_0$ constrained optimization problems, Mathematical Programming, to appear. [33] J. Yang, Y.-Q. Dai, Z. Peng, J.-P. Zhuang and W.-X. Zhu, A homotopy alternating direction method of multipliers for linearly constrained separable convex optimization, Journal of the Operations Research Society of China, 5 (2017), 271-290.  doi: 10.1007/s40305-017-0170-6. [34] J. Zeng, S. Lin, Y. Wang and Z.-B. Xu, $\ell_\frac{1}{2}$ Regularization: convergence of iterative half thresholding algorithm, IEEE Transactions on Signal Processing, 62 (2014), 2317-2329.  doi: 10.1109/TSP.2014.2309076. [35] K.-Z. Zhang and L.-Z. Zhang, Controllability of probabilistic Boolean control networks with time-variant delays in states, Science China: Information Sciences, 59(9)(2016), 092204, 10pp. doi: 10.1007/s11432-015-5423-6.

Figures(5)

Tables(1)