A reduced-space algorithm for minimizing \(\ell_1\)-regularized convex functions.

*(English)*Zbl 1369.90103##### MSC:

90C06 | Large-scale problems in mathematical programming |

90C25 | Convex programming |

90C30 | Nonlinear programming |

90C55 | Methods of successive quadratic programming type |

90C90 | Applications of mathematical programming |

49J52 | Nonsmooth analysis |

49M37 | Numerical methods based on nonlinear programming |

62M20 | Inference from stochastic processes and prediction |

65K05 | Numerical mathematical programming methods |

##### Keywords:

nonlinear optimization; convex optimization; sparse optimization; active-set methods; reduced-space methods; subspace minimization; model prediction##### References:

[1] | G. Andrew and J. Gao, Scalable training of \(l_1\)-regularized log-linear models, in Proceedings of the 24th International Conference on Machine Learning, 2007, pp. 33–40. |

[2] | A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183–202. · Zbl 1175.94009 |

[3] | R. H. Byrd, G. M. Chin, J. Nocedal, and F. Oztoprak, A family of second-order methods for convex \(ℓ_1\)-regularized optimization, Math. Program., 159 (2016), pp. 435–467. · Zbl 1350.49046 |

[4] | R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu, A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Comput., 16 (1995), pp. 1190–1208. · Zbl 0836.65080 |

[5] | R. H. Byrd, J. Nocedal, and F. Oztoprak, An inexact successive quadratic approximation method for \(ℓ_1\) regularized optimization, Math. Program., 157 (2016), pp. 375–396. · Zbl 1342.49037 |

[6] | F. E. Curtis, Z. Han, and D. P. Robinson, A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization, Comput. Oper. Appl., 60 (2015), pp. 311–341. · Zbl 1309.90072 |

[7] | Z. Dostál, Box constrained quadratic programming with proportioning and projections, SIAM J. Optim., 7 (1997), pp. 871–887, . · Zbl 0912.65052 |

[8] | Z. Dostál, A proportioning based algorithm with rate of convergence for bound constrained quadratic programming, Numer. Algorithms, 34 (2003), pp. 293–302, . · Zbl 1037.65061 |

[9] | Z. Dostál and J. Schoberl, Minimizing quadratic functions subject to bound constraints with the rate of convergence and finite termination, Comput. Oper. Appl., 30 (2005), pp. 23–43, . · Zbl 1071.65085 |

[10] | E. Elhamifar and R. Vidal, Sparse subspace clustering, in IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2009, pp. 2790–2797. |

[11] | A. Friedlander, J. M. Martínez, and M. Raydon, A new method for large-scale box constrained convex quadratic minimization problems, Optim. Meth. Softw., 5 (1995), pp. 57–74. |

[12] | A. Friedlander and J. M. Martínez, On the numerical solution of bound constrained optimization problems, Revue française d’automatique, d’informatique et de recherche opérationnelle. Rech. Oper., 23 (1989), pp. 319–341. |

[13] | A. Friedlander and J. M. Martinez, On the maximization of a concave quadratic function with box constraints, SIAM J. Optim., 4 (1994), pp. 177–192. · Zbl 0801.65058 |

[14] | M. D. Gonzalez-Lima, W. W. Hager, and H. Zhang, An affine-scaling interior-point method for continuous knapsack constraints, SIAM J. Optim., 21 (2011), pp. 361–390. · Zbl 1218.90114 |

[15] | W. W. Hager and H. Zhang, A new active set algorithm for box constrained optimization, SIAM J. Optim., 17 (2006), pp. 526–557. · Zbl 1165.90570 |

[16] | C.-J. Hsieh, I. S. Dhillon, P. K. Ravikumar, and M. A. Sustik, Sparse inverse covariance matrix estimation using quadratic approximation, in Advances in Neural Information Processing Systems, 2011, pp. 2330–2338. |

[17] | T. Joachims, Making large-scale support vector machine learning practical, Advances in Kernel Methods: Support Vector Machines, 1999. |

[18] | N. Keskar, J. Nocedal, F. Öztoprak, and A. Wächter, A second-order method for convex 1-regularized optimization with active-set prediction, Optim. Meth. Softw., 31 (2016), pp. 605–621. · Zbl 1341.49039 |

[19] | M. Ko, J. Zowe, et al., An iterative two-step algorithm for linear complementarity problems, Numer. Math., 68 (1994), pp. 95–106. · Zbl 0820.65033 |

[20] | J. Lee, Y. Sun, and M. Saunders, Proximal newton-type methods for convex optimization, in Advances in Neural Information Processing Systems, 2012, pp. 836–844. |

[21] | C.-J. Lin and J. J. Moré, Newton’s method for large bound-constrained optimization problems, SIAM J. Opti., 9 (1999), pp. 1100–1127. · Zbl 0957.65064 |

[22] | H. Mohy-ud-Din and D. P. Robinson, A solver for nonconvex bound-constrained quadratic optimization, SIAM J. Optim., 25 (2015), pp. 2385–2407, . · Zbl 1330.49029 |

[23] | J. J. Moré and G. Toraldo, On the solution of large quadratic programming problems with bound constraints, SIAM J. Optim., 1 (1991), pp. 93–113. · Zbl 0752.90053 |

[24] | D. P. Robinson, L. Feng, J. M. Nocedal, and J.-S. Pang, Subspace accelerated matrix splitting algorithms for asymmetric and symmetric linear complementarity problems, SIAM J. Optim., 23 (2013), pp. 1371–1397. · Zbl 1291.49023 |

[25] | K. Scheinberg and X. Tang, Practical inexact proximal quasi-newton method with global complexity analysis, preprint (2013). · Zbl 1366.90166 |

[26] | T. Serafini, G. Zanghirati, and L. Zanni, Gradient projection methods for quadratic programs and applications in training support vector machines, Optim. Meth. Softw., 20 (2005), pp. 353–378. · Zbl 1072.90026 |

[27] | T. Serafini and L. Zanni, On the working set selection in gradient projection-based decomposition techniques for support vector machines, Optim. Meth. Softw., 20 (2005), pp. 583–596. · Zbl 1116.90115 |

[28] | H. M. ud Din and D. P. Robinson, A solver for nonconvex bound-constrained quadratic optimization, SIAM J. Optim., 25 (2015), pp. 2385–2407, . · Zbl 1330.49029 |

[29] | S. J. Wright, R. D. Nowak, and M. A. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57 (2009), pp. 2479–2493. · Zbl 1391.94442 |

[30] | C. Yang, D. P. Robinson, and R. Vidal, Sparse subspace clustering with missing entries, in International Conference on Machine Learning, 2015, pp. 2463–2472. |

[31] | C. You, C.-G. Li, D. P. Robinson, and R. Vidal, Oracle based active set algorithm for scalable elastic net subspace clustering, in IEEE Conference on Computer Vision and Pattern Recognition, 2016. |

[32] | C. You, D. P. Robinson, and R. Vidal, Sparse subspace clustering by orthogonal matching pursuit, in IEEE Conference on Computer Vision and Pattern Recognition, 2016. |

[33] | G.-X. Yuan, C.-H. Ho, and C.-J. Lin, An improved glmnet for l\(1\)-regularized logistic regression, J. Mach. Learn. Res., 13 (2012), pp. 1999–2030. · Zbl 1432.68404 |

[34] | L. Zanni, An improved gradient projection-based decomposition technique for support vector machines, Comput. Manag. Sci., 3 (2006), pp. 131–145. · Zbl 1163.90693 |

[35] | L. Zanni, T. Serafini, and G. Zanghirati, Parallel software for training large scale support vector machines on multiprocessor systems, J. Mach. Learn. Res., 7 (2006), pp. 1467–1492. · Zbl 1222.68341 |

[36] | Q. Zhu, E. Izumchenko, A. M. Aliper, E. Makarev, K. Paz, A. A. Buzdin, A. A. Zhavoronkov, and D. Sidransky, Pathway activation strength is a novel independent prognostic biomarker for cetuximab sensitivity in colorectal cancer patients, Hum. Gen. Var., 2 (2015). |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.