{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:21:19Z","timestamp":1740122479857,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T00:00:00Z","timestamp":1726099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T00:00:00Z","timestamp":1726099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a random coordinate descent algorithm for optimizing a non-convex objective function subject to one linear constraint and simple bounds on the variables. Although it is common use to update only two random coordinates simultaneously in each iteration of a coordinate descent algorithm, our algorithm allows updating arbitrary number of coordinates. We provide a proof of convergence of the algorithm. The convergence rate of the algorithm improves when we update more coordinates per iteration. Numerical experiments on large scale instances of different optimization problems show the benefit of updating many coordinates simultaneously.<\/jats:p>","DOI":"10.1007\/s10898-024-01429-6","type":"journal-article","created":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T03:43:38Z","timestamp":1726112618000},"page":"843-868","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On convergence of a q-random coordinate constrained algorithm for non-convex problems"],"prefix":"10.1007","volume":"90","author":[{"given":"A.","family":"Ghaffari-Hadigheh","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0516-6360","authenticated-orcid":false,"given":"L.","family":"Sinjorgo","sequence":"additional","affiliation":[]},{"given":"R.","family":"Sotirov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,12]]},"reference":[{"issue":"3","key":"1429_CR1","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1080\/10618600.1998.10474784","volume":"7","author":"JF Wenjiang","year":"1998","unstructured":"Wenjiang, J.F.: Penalized regressions: the bridge versus the lasso. J. Comput. Graph. Stat. 7(3), 397\u2013416 (1998)","journal-title":"J. Comput. Graph. Stat."},{"key":"1429_CR2","unstructured":"Shi, H.-J.M., Tu, S., Xu, Y., Yin, W.: A primer on coordinate descent algorithms. arXiv preprint arXiv:1610.00040, (2016)"},{"issue":"1","key":"1429_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0892-3","volume":"151","author":"SJ Wright","year":"2015","unstructured":"Wright, S.J.: Coordinate descent algorithms. Math. Program. 151(1), 3\u201334 (2015)","journal-title":"Math. Program."},{"issue":"4","key":"1429_CR4","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1109\/TIP.2015.2400813","volume":"24","author":"MG McGaffin","year":"2015","unstructured":"McGaffin, M.G., Fessler, J.A.: Edge-preserving image denoising via group coordinate descent on the GPU. IEEE Trans. Image Process. 24(4), 1273\u20131281 (2015)","journal-title":"IEEE Trans. Image Process."},{"key":"1429_CR5","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1007\/s11590-021-01762-9","volume":"16","author":"M Nishijima","year":"2022","unstructured":"Nishijima, M., Nakata, K.: A block coordinate descent method for sensor network localization. Optim. Lett. 16, 1051\u20131071 (2022)","journal-title":"Optim. Lett."},{"key":"1429_CR6","doi-asserted-by":"crossref","unstructured":"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\u2013415, (2008)","DOI":"10.1145\/1390156.1390208"},{"issue":"1","key":"1429_CR7","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1214\/10-AOAS388","volume":"5","author":"P Breheny","year":"2011","unstructured":"Breheny, P., Huang, J.: Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection. Ann. Appl. Stat. 5(1), 232\u2013253 (2011)","journal-title":"Ann. Appl. Stat."},{"issue":"2","key":"1429_CR8","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"1429_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-012-0614-z","volume":"144","author":"P Richt\u00e1rik","year":"2014","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144(1\u20132), 1\u201338 (2014)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1429_CR10","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10107-013-0686-4","volume":"146","author":"Y Nesterov","year":"2014","unstructured":"Nesterov, Y.: Subgradient methods for huge-scale optimization problems. Math. Program. 146(1\u20132), 275\u2013297 (2014)","journal-title":"Math. Program."},{"issue":"1","key":"1429_CR11","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s10898-014-0151-9","volume":"61","author":"A Patrascu","year":"2015","unstructured":"Patrascu, A., Necoara, I.: Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization. J. Global Optim. 61(1), 19\u201346 (2015)","journal-title":"J. Global Optim."},{"issue":"2","key":"1429_CR12","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s10589-019-00082-0","volume":"73","author":"A Cristofari","year":"2019","unstructured":"Cristofari, A.: An almost cyclic 2-coordinate descent method for singly linearly constrained problems. Comput. Optim. Appl. 73(2), 411\u2013452 (2019)","journal-title":"Comput. Optim. Appl."},{"issue":"6","key":"1429_CR13","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1080\/10556788.2019.1595620","volume":"35","author":"R Sotirov","year":"2020","unstructured":"Sotirov, R.: On solving the densest $$k$$-subgraph problem on large graphs. Optim. Methods Softw. 35(6), 1160\u20131178 (2020)","journal-title":"Optim. Methods Softw."},{"key":"1429_CR14","doi-asserted-by":"crossref","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. In: Foundations and Trends\u00ae in Machine learning, vol. 3, pp. 1\u2013122. Now Publishers, Inc., (2011)","DOI":"10.1561\/2200000016"},{"issue":"1","key":"1429_CR15","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF02592073","volume":"39","author":"PH Calamai","year":"1987","unstructured":"Calamai, P.H., Mor\u00e9, J.J.: Projected gradient methods for linearly constrained problems. Math. Program. 39(1), 93\u2013116 (1987)","journal-title":"Math. Program."},{"key":"1429_CR16","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1007\/s10957-013-0491-5","volume":"162","author":"A Beck","year":"2014","unstructured":"Beck, A.: The 2-coordinate descent method for solving double-sided simplex constrained minimization problems. J. Optim. Theory Appl. 162, 892\u2013919 (2014)","journal-title":"J. Optim. Theory Appl."},{"key":"1429_CR17","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.: Lectures on convex optimization, volume 137 of springer optimization and its applications. Springer, (2018)","DOI":"10.1007\/978-3-319-91578-4_2"},{"issue":"5","key":"1429_CR18","first-page":"1049","volume":"248","author":"MK Kozlov","year":"1979","unstructured":"Kozlov, M.K., Tarasov, S.P., Khachiyan, L.G.: Polynomial solvability of convex quadratic programming. Dokl. Akad. Nauk SSSR 248(5), 1049\u20131051 (1979)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"1429_CR19","unstructured":"Rockafellar, R.T.: The elementary vectors of a subspace of $$\\mathbb{R}^n$$. In: Combinatorial mathematics and its applications, pp. 104\u2013127. University of North Carolina Press, (1969)"},{"key":"1429_CR20","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/s10957-008-9458-3","volume":"140","author":"P Tseng","year":"2009","unstructured":"Tseng, P., Yun, S.: Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization. J. Optim. Theory Appl. 140, 513\u2013535 (2009)","journal-title":"J. Optim. Theory Appl."},{"key":"1429_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813658","volume-title":"Probability with martingales","author":"D Williams","year":"1991","unstructured":"Williams, D.: Probability with martingales. Cambridge University Press, Cambridge (1991)"},{"key":"1429_CR22","volume-title":"Nonlinear programming","author":"DP Bertsekas","year":"1999","unstructured":"Bertsekas, D.P.: Nonlinear programming, 2nd edn. Athena scientific, Nashua (1999)","edition":"2"},{"issue":"4","key":"1429_CR23","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, dense $$k$$-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"1429_CR24","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.cor.2015.07.008","volume":"66","author":"N Krislock","year":"2016","unstructured":"Krislock, N., Malick, J., Roupin, F.: Computational results of a semidefinite branch-and-bound algorithm for $$k$$-cluster. Comput. Op. Res. 66, 153\u2013159 (2016)","journal-title":"Comput. Op. Res."},{"key":"1429_CR25","unstructured":"Wang, W., Lu, C.: Projection onto the capped simplex. arXiv preprint arXiv:1503.01002, (2015)"},{"issue":"23","key":"1429_CR26","first-page":"1","volume":"1","author":"P Bombina","year":"2020","unstructured":"Bombina, P., Ames, B.: Convex optimization for the densest subgraph and densest submatrix problems. Springer Nat. Op. Res. Forum 1(23), 1\u201324 (2020)","journal-title":"Springer Nat. Op. Res. Forum"},{"key":"1429_CR27","unstructured":"Leskovec, J., Krevl, A.: SNAP datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data, June 2014. Accessed on May 25, (2023)"},{"key":"1429_CR28","doi-asserted-by":"crossref","unstructured":"Rossi, R., Ahmed, N.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the AAAI conference on artificial intelligence, vol.\u00a029, (2015)","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"3","key":"1429_CR29","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1007\/s10589-010-9388-5","volume":"51","author":"HA Le Thi","year":"2012","unstructured":"Le Thi, H.A., Moeini, M., Pham Dinh, T., Judice, J.: A DC programming approach for solving the symmetric Eigenvalue Complementarity Problem. Comput. Optim. Appl. 51(3), 1097\u20131117 (2012)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"1429_CR30","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s11075-008-9194-7","volume":"47","author":"JJ J\u00fadice","year":"2008","unstructured":"J\u00fadice, J.J., Raydan, M., Rosa, S.S., Santos, S.A.: On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm. Numer. Algorithms 47(4), 391\u2013407 (2008)","journal-title":"Numer. Algorithms"},{"issue":"1","key":"1429_CR31","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10107-015-0946-6","volume":"158","author":"L Condat","year":"2016","unstructured":"Condat, L.: Fast Projection onto the Simplex and the $$\\ell _1$$ Ball. Math. Program. 158(1), 575\u2013585 (2016)","journal-title":"Math. Program."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01429-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01429-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01429-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T14:03:44Z","timestamp":1730297024000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01429-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["1429"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01429-6","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2024,9,12]]},"assertion":[{"value":"17 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}