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

Kangkang Deng; Zheng Peng; Jianli Chen

doi:10.3934/jimo.2018127

Article Contents

2019, Volume 15, Issue 4: 1881-1896. Doi: 10.3934/jimo.2018127

This issue Previous Article An economic order quantity for deteriorating items with allowable rework of deteriorated products Next Article Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs

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

College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China

* Corresponding author: Zheng Peng
* Corresponding author: Zheng Peng

Received: January 2018

Revised: April 2018

Early access: August 2018

Published: July 2019

The work is supported by NSFC grants 11571074, 11726505, and the Natural Science Foundation of FuJian Province grant 2015J01010.

Abstract / Introduction Full Text(HTML) Figure(5) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.