{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:51:08Z","timestamp":1760143868595,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:00:00Z","timestamp":1708560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100007197","name":"USPHS","doi-asserted-by":"publisher","award":["GM141798","GM053275"],"award-info":[{"award-number":["GM141798","GM053275"]}],"id":[{"id":"10.13039\/100007197","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The current paper proposes and tests algorithms for finding the diameter of a compact convex set and the farthest point in the set to another point. For these two nonconvex problems, I construct Frank\u2013Wolfe and projected gradient ascent algorithms. Although these algorithms are guaranteed to go uphill, they can become trapped by local maxima. To avoid this defect, I investigate a homotopy method that gradually deforms a ball into the target set. Motivated by the Frank\u2013Wolfe algorithm, I also find the support function of the intersection of a convex cone and a ball centered at the origin and elaborate a known bisection algorithm for calculating the support function of a convex sublevel set. The Frank\u2013Wolfe and projected gradient algorithms are tested on five compact convex sets: (a) the box whose coordinates range between \u22121 and 1, (b) the intersection of the unit ball and the non-negative orthant, (c) the probability simplex, (d) the Manhattan-norm unit ball, and (e) a sublevel set of the elastic net penalty. Frank\u2013Wolfe and projected gradient ascent are about equally fast on these test problems. Ignoring homotopy, the Frank\u2013Wolfe algorithm is more reliable. However, homotopy allows projected gradient ascent to recover from its failures.<\/jats:p>","DOI":"10.3390\/a17030095","type":"journal-article","created":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T07:33:56Z","timestamp":1708673636000},"page":"95","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Closest Farthest Widest"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1313-5030","authenticated-orcid":false,"given":"Kenneth","family":"Lange","sequence":"first","affiliation":[{"name":"Departments of Computational Medicine, Human Genetics, and Statistics, University of California, Los Angeles, CA 90095, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,2,22]]},"reference":[{"key":"ref_1","unstructured":"Valentine, F.A. (1964). Convex Sets, McGraw-Hill."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Webster, R. (1994). Convexity, Oxford University Press.","DOI":"10.1093\/oso\/9780198531470.001.0001"},{"key":"ref_3","unstructured":"Pope, S.B. (2008). Algorithms for Ellipsoids, Cornell University. Cornell University Report No. FDA-08-01."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bauschke, H.H., and Combettes, P.L. (2017). Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer. [2nd ed.].","DOI":"10.1007\/978-3-319-48311-5"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Beck, A. (2014). Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB, SIAM.","DOI":"10.1137\/1.9781611973655"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Beck, A. (2017). First-Order Methods in Optimization, SIAM.","DOI":"10.1137\/1.9781611974997"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Lange, K. (2016). MM Optimization Algorithms, SIAM.","DOI":"10.1137\/1.9781611974409"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/j.orl.2021.06.005","article-title":"Complexity of linear minimization and projection on some sets","volume":"49","author":"Combettes","year":"2021","journal-title":"Oper. Res. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1007\/s11590-022-01919-0","article-title":"A unified analysis of convex and non-convex \u2113_p-ball projection problems","volume":"17","author":"Won","year":"2023","journal-title":"Optim. Lett."},{"key":"ref_10","unstructured":"Stella, L., Antonello, N., and F\u00e4lt, M. (2023, October 27). ProximalOperators.jl. Available online: https:\/\/docs.juliahub.com\/ProximalOperators\/ez37h\/0.14.2\/calculus\/."},{"key":"ref_11","unstructured":"Chierchia, G., Chouzenoux, E., Combettes, P., and Pesquet, J.C. (2024, January 19). The Proximity Operator Repository. Available online: http:\/\/proximity-operator.net\/index.html."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1561\/2400000003","article-title":"Proximal algorithms","volume":"1","author":"Parikh","year":"2014","journal-title":"Found. Trends Optim."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/235815.235821","article-title":"The quickhull algorithm for convex hulls","volume":"22","author":"Barber","year":"1996","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Spinger.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref_15","unstructured":"Ziegler, G.M. (2012). Lectures on Polytopes, Springer."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/060656784","article-title":"Regularization in regression with bounded noise: A Chebyshev center approach","volume":"29","author":"Beck","year":"2007","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/nav.3800030109","article-title":"An algorithm for quadratic programming","volume":"3","author":"Frank","year":"1956","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"A3291","DOI":"10.1137\/15M101628X","article-title":"Scalable robust matrix recovery: Frank-Wolfe meets proximal methods","volume":"38","author":"Mu","year":"2016","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_19","unstructured":"Ledoux, M. (2001). The Concentration of Measure Phenomenon, American Mathematical Society."},{"key":"ref_20","unstructured":"Rademacher, H., and Toeplitz, O. (2015). The Enjoyment of Math, Princeton University Press."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1198\/0003130042836","article-title":"A tutorial on MM algorithms","volume":"58","author":"Hunter","year":"2004","journal-title":"Am. Stat."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"McLachlan, G.J., and Krishnan, T. (2007). The EM Algorithm and Extensions, John Wiley & Sons.","DOI":"10.1002\/9780470191613"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1162\/08997660360581958","article-title":"The concave-convex procedure","volume":"15","author":"Yuille","year":"2003","journal-title":"Neural Comput."},{"key":"ref_24","unstructured":"Jaggi, M. (2013, January 17\u201319). Revisiting Frank\u2013Wolfe: Projection-free sparse convex optimization. Proceedings of the International Conference on Machine Learning, Atlanta, GA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1515\/dema-2022-0159","article-title":"A Dai-Liao-type projection method for monotone nonlinear equations and signal processing","volume":"55","author":"Ibrahim","year":"2022","journal-title":"Demonstr. Math."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Lange, K. (2023). Computation of the Hausdorff Distance between Two Compact Convex Sets. Algorithms, 16.","DOI":"10.3390\/a16100471"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Dunlavy, D.M., and O\u2019Leary, D.P. (2005). Homotopy Optimization Methods for Global Optimization, Technical Report.","DOI":"10.2172\/876373"},{"key":"ref_28","unstructured":"Won, J.H., Xu, J., and Lange, K. (2019, January 9\u201315). Projection onto Minkowski sums with application to constrained learning. Proceedings of the International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_29","unstructured":"Rockafellar, R.T. (2015). Convex Analysis, Princeton University Press."},{"key":"ref_30","unstructured":"Constantin, N.P., and Persson, L.E. (2019). Convex Functions and Their Applications: A Contemporary Approach, Springer."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"337","DOI":"10.21136\/CPM.1988.118346","article-title":"A simple proof of the Rademacher theorem","volume":"113","author":"Nekvinda","year":"1988","journal-title":"\u010casopis pro P\u011bstov\u00e1n\u00ed Matematiky"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10589-022-00434-3","article-title":"Avoiding bad steps in Frank-Wolfe variants","volume":"84","author":"Rinaldi","year":"2023","journal-title":"Comput. Optim. Appl."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"2158","DOI":"10.1137\/17M1141849","article-title":"Projecting onto the intersection of a cone and a sphere","volume":"28","author":"Bauschke","year":"2018","journal-title":"SIAM J. Optim."},{"key":"ref_34","unstructured":"Zangwill, W.I. (1969). Nonlinear Programming: A Unified Approach, Prentice-Hall."},{"key":"ref_35","unstructured":"Lacoste-Julien, S. (2016). Convergence rate of Frank-Wolfe for non-convex objectives. arXiv."},{"key":"ref_36","unstructured":"Mangasarian, O.L. (1996). Applied Mathematics and Parallel Computing: Festschrift for Klaus Ritter, Springer."},{"key":"ref_37","first-page":"35352","article-title":"CCCP is Frank\u2013Wolfe in disguise","volume":"35","author":"Yurtsever","year":"2022","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s10107-011-0484-9","article-title":"Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward\u2013backward splitting, and regularized Gauss\u2013Seidel methods","volume":"137","author":"Attouch","year":"2013","journal-title":"Math. Program."},{"key":"ref_39","unstructured":"Bertsekas, D. (1999). Nonlinear Programming, Athena Scientific. [2nd ed.]."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1137\/0329022","article-title":"On the convergence of the proximal point algorithm for convex minimization","volume":"29","year":"1991","journal-title":"SIAM J. Control. Optim."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1590\/S0101-82052003000100003","article-title":"On the convergence properties of the projected gradient method for convex optimization","volume":"22","author":"Iusem","year":"2003","journal-title":"Comput. Appl. Math."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Lange, K., Won, J.H., Landeros, A., and Zhou, H. (2021). Nonconvex optimization via MM algorithms: Convergence theory. arXiv.","DOI":"10.1002\/9781118445112.stat08295"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/3\/95\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:03:13Z","timestamp":1760104993000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/3\/95"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,22]]},"references-count":42,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,3]]}},"alternative-id":["a17030095"],"URL":"https:\/\/doi.org\/10.3390\/a17030095","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,2,22]]}}}