An almost cyclic 2-coordinate descent method for singly linearly constrained problems. (English) Zbl 1414.90226
Summary: A block decomposition method is proposed for minimizing a (possibly non-convex) continuously differentiable function subject to one linear equality constraint and simple bounds on the variables. The proposed method iteratively selects a pair of coordinates according to an almost cyclic strategy that does not use first-order information, allowing us not to compute the whole gradient of the objective function during the algorithm. Using first-order search directions to update each pair of coordinates, global convergence to stationary points is established for different choices of the stepsize under an appropriate assumption on the level set. In particular, both inexact and exact line search strategies are analyzed. Further, linear convergence rate is proved under standard additional assumptions. Numerical results are finally provided to show the effectiveness of the proposed method.
MSC:
| 90C06 | Large-scale problems in mathematical programming |
| 90C30 | Nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
block coordinate descent methods; block decomposition methods; linear convergence rate; SVMSoftware:
LIBSVMReferences:
| [1] | Beck, A.: The 2-coordinate descent method for solving double-sided simplex constrained minimization problems. J. Optim. Theory Appl. 162(3), 892-919 (2014) · Zbl 1312.90058 · doi:10.1007/s10957-013-0491-5 |
| [2] | Beck, A., Tetruashvili, L.: On the convergence of block coordinate descent type methods. SIAM J. Optim. 23(4), 2037-2060 (2013) · Zbl 1297.90113 · doi:10.1137/120887679 |
| [3] | Bertsekas, D.P.: Projected Newton methods for optimization problems with simple constraints. SIAM J. Control Optim. 20(2), 221-246 (1982) · Zbl 0507.49018 · doi:10.1137/0320018 |
| [4] | Bomze, I.M., Rinaldi, F., Rota Bulò, S.: First-order methods for the impatient: support identification in finite time with convergent Frank-Wolfe variants. Optimization Online (2018). http://www.optimization-online.org/DB_HTML/2018/07/6694.html · Zbl 1461.65132 |
| [5] | Boser, B.E., Guyon, I.M., Vapnik, V.N.: A training algorithm for optimal margin classifiers. In: Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pp. 144-152. ACM (1992) |
| [6] | Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. (TIST) 2(3), 27 (2011) |
| [7] | Chang, K.W., Hsieh, C.J., Lin, C.J.: Coordinate descent method for large-scale l2-loss linear support vector machines. J. Mach. Learn. Res. 9, 1369-1398 (2008) · Zbl 1225.68157 |
| [8] | Cristofari, A., De Santis, M., Lucidi, S., Rinaldi, F.: An active-set algorithmic framework for non-convex optimization problems over the simplex (2018). arXiv preprint arXiv:1703.07761 · Zbl 1398.90170 |
| [9] | Fan, R.E., Chen, P.H., Lin, C.J.: Working set selection using second order information for training support vector machines. J. Mach. Learn. Res. 6, 1889-1918 (2005) · Zbl 1222.68198 |
| [10] | Hsieh, C.J., Chang, K.W., Lin, C.J., Keerthi, S.S., Sundararajan, S.: A dual coordinate descent method for large-scale linear SVM. In: Proceedings of the 25th International Conference on Machine Learning, pp. 408-415. ACM (2008) |
| [11] | Joachims, T.; Schölkopf, B. (ed.); Burges, CJ (ed.); Smola, AJ (ed.), Making large-scale support vector machine learning practical, 169-184 (1999), Cambridge |
| [12] | Konnov, I.V.: Selective bi-coordinate variations for resource allocation type problems. Comput. Optim. Appl. 64(3), 821-842 (2016) · Zbl 1381.90085 · doi:10.1007/s10589-016-9824-2 |
| [13] | Lin, C.J.: On the convergence of the decomposition method for support vector machines. IEEE Trans. Neural Netw. 12(6), 1288-1298 (2001) · doi:10.1109/72.963765 |
| [14] | Lin, C.J., Lucidi, S., Palagi, L., Risi, A., Sciandrone, M.: Decomposition algorithm model for singly linearly-constrained problems subject to lower and upper bounds. J. Optim. Theory Appl. 141(1), 107-126 (2009) · Zbl 1168.90556 · doi:10.1007/s10957-008-9489-9 |
| [15] | Liuzzi, G., Palagi, L., Piacentini, M.: On the convergence of a Jacobi-type algorithm for singly linearly-constrained problems subject to simple bounds. Optim. Lett. 5(2), 347-362 (2011) · Zbl 1242.90238 · doi:10.1007/s11590-010-0214-x |
| [16] | Lucidi, S., Palagi, L., Risi, A., Sciandrone, M.: A convergent decomposition algorithm for support vector machines. Comput. Optim. Appl. 38(2), 217-234 (2007) · Zbl 1172.90443 · doi:10.1007/s10589-007-9044-x |
| [17] | Luo, Z.Q., Tseng, P.: On the convergence of the coordinate descent method for convex differentiable minimization. J. Optim. Theory Appl. 72(1), 7-35 (1992) · Zbl 0795.90069 · doi:10.1007/BF00939948 |
| [18] | Manno, A., Palagi, L., Sagratella, S.: Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training. Comput. Optim. Appl. 71(1), 115-145 (2018) · Zbl 1405.90095 · doi:10.1007/s10589-018-9987-0 |
| [19] | Necoara, I.: Random coordinate descent algorithms for multi-agent convex optimization over networks. IEEE Trans. Autom. Control 58(8), 2001-2012 (2013) · Zbl 1369.90124 · doi:10.1109/TAC.2013.2250071 |
| [20] | Necoara, I., Nesterov, Y., Glineur, F.: Random block coordinate descent methods for linearly constrained optimization over networks. J. Optim. Theory Appl. 173(1), 227-254 (2017) · Zbl 1370.90145 · doi:10.1007/s10957-016-1058-z |
| [21] | Necoara, I., Patrascu, A.: A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints. Comput. Optim. Appl. 57(2), 307-337 (2014) · Zbl 1304.90160 · doi:10.1007/s10589-013-9598-8 |
| [22] | Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341-362 (2012) · Zbl 1257.90073 · doi:10.1137/100802001 |
| [23] | Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer, New York (2013) · Zbl 1086.90045 |
| [24] | Palagi, L., Sciandrone, M.: On the convergence of a modified version of SVM light algorithm. Optim. Methods Softw. 20(2-3), 317-334 (2005) · Zbl 1072.90042 · doi:10.1080/10556780512331318209 |
| [25] | Patrascu, A., Necoara, I.: Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization. J. Glob. Optim. 61(1), 19-46 (2015) · Zbl 1335.90074 · doi:10.1007/s10898-014-0151-9 |
| [26] | Platt, JC; Schölkopf, B. (ed.); Burges, CJ (ed.); Smola, AJ (ed.), Sequential minimal optimization: a fast algorithm for training support vector machines, 185-208 (1998), Cambridge |
| [27] | Raj, A., Olbrich, J., Gärtner, B., Schölkopf, B., Jaggi, M.: Screening rules for convex problems (2016). arXiv preprint arXiv:1609.07478 |
| [28] | Reddi, S., Hefny, A., Downey, C., Dubey, A., Sra, S.: Large-scale randomized-coordinate descent methods with non-separable linear constraints (2014). arXiv preprint arXiv:1409.2617 |
| [29] | Tseng, P.: Descent methods for convex essentially smooth minimization. J. Optim. Theory Appl. 71(3), 425-463 (1991) · Zbl 0793.90050 · doi:10.1007/BF00941397 |
| [30] | Tseng, P., Yun, S.: A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training. Comput. Optim. Appl. 47(2), 179-206 (2010) · Zbl 1226.90062 · doi:10.1007/s10589-008-9215-4 |
| [31] | Wright, S.J.: Coordinate descent algorithms. Math. Program. 151(1), 3-34 (2015) · Zbl 1317.49038 · doi:10.1007/s10107-015-0892-3 |
| [32] | Xiao, L., Boyd, S.: Optimal scaling of a gradient method for distributed resource allocation. J. Optim. Theory Appl. 129(3), 469-488 (2006) · Zbl 1330.90136 · doi:10.1007/s10957-006-9080-1 |
| [33] | Xu, S., Freund, R.M., Sun, J.: Solution methodologies for the smallest enclosing circle problem. Comput. Optim. Appl. 25(1-3), 283-292 (2003) · Zbl 1038.90080 · doi:10.1023/A:1022977709811 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
