{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:57Z","timestamp":1740109317903,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T00:00:00Z","timestamp":1691625600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T00:00:00Z","timestamp":1691625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["QIP-805241"],"award-info":[{"award-number":["QIP-805241"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function <jats:italic>f<\/jats:italic> over a convex set <jats:italic>K<\/jats:italic> given by a separation oracle. Our method utilizes the Frank\u2013Wolfe algorithm over the cone of valid inequalities of <jats:italic>K<\/jats:italic> and subgradients of <jats:italic>f<\/jats:italic>. Under the assumption that <jats:italic>f<\/jats:italic> is <jats:italic>L<\/jats:italic>-Lipschitz and that <jats:italic>K<\/jats:italic> contains a ball of radius <jats:italic>r<\/jats:italic> and is contained inside the origin centered ball of radius <jats:italic>R<\/jats:italic>, using <jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\left( \\frac{(RL)^2}{\\varepsilon ^2} \\cdot \\frac{R^2}{r^2}\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mfenced>\n                      <mml:mfrac>\n                        <mml:msup>\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>R<\/mml:mi>\n                            <mml:mi>L<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msup>\n                        <mml:msup>\n                          <mml:mi>\u03b5<\/mml:mi>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msup>\n                      <\/mml:mfrac>\n                      <mml:mo>\u00b7<\/mml:mo>\n                      <mml:mfrac>\n                        <mml:msup>\n                          <mml:mi>R<\/mml:mi>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msup>\n                        <mml:msup>\n                          <mml:mi>r<\/mml:mi>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msup>\n                      <\/mml:mfrac>\n                    <\/mml:mfenced>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> iterations and calls to the oracle, our main method outputs a point <jats:inline-formula><jats:alternatives><jats:tex-math>$$x \\in K$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>K<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> satisfying <jats:inline-formula><jats:alternatives><jats:tex-math>$$f(x) \\le \\varepsilon + \\min _{z \\in K} f(z)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:msub>\n                      <mml:mo>min<\/mml:mo>\n                      <mml:mrow>\n                        <mml:mi>z<\/mml:mi>\n                        <mml:mo>\u2208<\/mml:mo>\n                        <mml:mi>K<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>z<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our algorithm is easy to implement, and we believe it can serve as a useful alternative to existing cutting plane methods. As evidence towards this, we show that it compares favorably in terms of iteration counts to the standard LP based cutting plane method and the analytic center cutting plane method, on a testbed of combinatorial, semidefinite and machine learning instances.\n<\/jats:p>","DOI":"10.1007\/s10107-023-02005-8","type":"journal-article","created":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T15:02:32Z","timestamp":1691679752000},"page":"283-304","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A simple method for convex optimization in the oracle model"],"prefix":"10.1007","volume":"206","author":[{"given":"Daniel","family":"Dadush","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5324-8996","authenticated-orcid":false,"given":"Christopher","family":"Hojny","sequence":"additional","affiliation":[]},{"given":"Sophie","family":"Huiberts","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Weltge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,10]]},"reference":[{"issue":"1","key":"2005_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01585551","volume":"69","author":"DS Atkinson","year":"1995","unstructured":"Atkinson, D.S., Vaidya, P.M.: A cutting plane algorithm for convex programming that uses analytic centers. Math. Program. 69(1), 1\u201343 (1995)","journal-title":"Math. Program."},{"key":"2005_CR2","doi-asserted-by":"publisher","unstructured":"Badenbroek, R., de Klerk, E.: An analytic center cutting plane method to determine complete positivity of a matrix. INFORMS J. Comput. 34, 1115\u2013125 2022 . https:\/\/doi.org\/10.1287\/ijoc.2021.1108","DOI":"10.1287\/ijoc.2021.1108"},{"key":"2005_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974997","volume-title":"First-Order Methods in Optimization","author":"A Beck","year":"2017","unstructured":"Beck, A.: First-Order Methods in Optimization. Society for Industrial and Applied Mathematics (2017). https:\/\/doi.org\/10.1137\/1.9781611974997"},{"issue":"3","key":"2005_CR4","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1287\/moor.1090.0388","volume":"34","author":"A Belloni","year":"2009","unstructured":"Belloni, A., Freund, R.M., Vempala, S.: An efficient rescaled perceptron algorithm for conic systems. Math. Oper. Res. 34(3), 621\u2013641 (2009)","journal-title":"Math. Oper. Res."},{"key":"2005_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718829","volume-title":"Lectures on Modern Convex Optimization","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics, London (2001). https:\/\/doi.org\/10.1137\/1.9780898718829"},{"key":"2005_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-2878-4","author":"U Betke","year":"2004","unstructured":"Betke, U.: Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discret. Comput. Geom. (2004). https:\/\/doi.org\/10.1007\/s00454-004-2878-4","journal-title":"Discret. Comput. Geom."},{"key":"2005_CR7","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Quanrud, K.: Approximating the Held\u2013Karp bound for metric TSP in nearly-linear time. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE (2017). https:\/\/doi.org\/10.1109\/focs.2017.78","DOI":"10.1109\/focs.2017.78"},{"key":"2005_CR8","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Quanrud, K.: Near-linear time approximation schemes for some implicit fractional packing problems. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.51","DOI":"10.1137\/1.9781611974782.51"},{"issue":"1","key":"2005_CR9","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF01386389","volume":"1","author":"EW Cheney","year":"1959","unstructured":"Cheney, E.W., Goldstein, A.A.: Newton\u2019s method for convex programming and Tchebycheff approximation. Numer. Math. 1(1), 253\u2013268 (1959)","journal-title":"Numer. Math."},{"issue":"2","key":"2005_CR10","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-011-0445-3","volume":"134","author":"S Chubanov","year":"2011","unstructured":"Chubanov, S.: A strongly polynomial algorithm for linear systems having a binary solution. Math. Program. 134(2), 533\u2013570 (2011). https:\/\/doi.org\/10.1007\/s10107-011-0445-3","journal-title":"Math. Program."},{"key":"2005_CR11","unstructured":"Chubanov, S.: A polynomial algorithm for linear feasibility problems given by separation oracles. Optimization Online (2017)"},{"key":"2005_CR12","unstructured":"Color02\u2014Computational Symposium: Graph Coloring and its Generalizations. Available at http:\/\/mat.gsia.cmu.edu\/COLOR02 (2002)"},{"key":"2005_CR13","doi-asserted-by":"crossref","unstructured":"Dadush, D., Hojny, C., Huiberts, S., Weltge, S.: A simple method for convex optimization in the oracle model. In: Aardal, K., Sanit\u00e0, L. (eds.) Integer Programming and Combinatorial Optimization, 23rd International Conference, IPCO 2022 (2022)","DOI":"10.1007\/s10107-023-02005-8"},{"issue":"2","key":"2005_CR14","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1287\/moor.2019.1011","volume":"45","author":"D Dadush","year":"2020","unstructured":"Dadush, D., V\u00e9gh, L.A., Zambelli, G.: Rescaling algorithms for linear conic feasibility. Math. Oper. Res. 45(2), 732\u2013754 (2020). https:\/\/doi.org\/10.1287\/moor.2019.1011","journal-title":"Math. Oper. Res."},{"key":"2005_CR15","unstructured":"Dantzig, G.B.: Converting a converging algorithm into a polynomially bounded algorithm. Technical report, Stanford University, 1992. 5.6, 6.1, 6.5 (1991)"},{"issue":"1","key":"2005_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1023\/A:1012470815092","volume":"46","author":"A Demiriz","year":"2002","unstructured":"Demiriz, A., Bennett, K.P., Shawe-Taylor, J.: Linear programming boosting via column generation. Mach. Learn. 46(1), 225\u2013254 (2002)","journal-title":"Mach. Learn."},{"issue":"1","key":"2005_CR17","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s10107-007-0095-7","volume":"114","author":"J Dunagan","year":"2007","unstructured":"Dunagan, J., Vempala, S.: A simple polynomial-time rescaling algorithm for solving linear programs. Math. Program. 114(1), 101\u2013114 (2007). https:\/\/doi.org\/10.1007\/s10107-007-0095-7","journal-title":"Math. Program."},{"issue":"1\u20132","key":"2005_CR18","first-page":"125","volume":"69B","author":"J Edmonds","year":"1964","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bureau Stand. 69B(1\u20132), 125\u2013130 (1964)","journal-title":"J. Res. Natl. Bureau Stand."},{"issue":"1\u20132","key":"2005_CR19","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3(1\u20132), 95\u2013110 (1956)","journal-title":"Naval Res. Logist. Q."},{"issue":"2","key":"2005_CR20","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1137\/s0097539704446232","volume":"37","author":"N Garg","year":"2007","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2), 630\u2013652 (2007). https:\/\/doi.org\/10.1137\/s0097539704446232","journal-title":"SIAM J. Comput."},{"issue":"6","key":"2005_CR21","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995). https:\/\/doi.org\/10.1145\/227683.227684","journal-title":"J. ACM"},{"key":"2005_CR22","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"RE Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275\u2013278 (1958)","journal-title":"Bull. Am. Math. Soc."},{"key":"2005_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer (1988). https:\/\/doi.org\/10.1007\/978-3-642-78240-4"},{"key":"2005_CR24","unstructured":"Jaggi, M.: Revisiting Frank\u2013Wolfe: projection-free sparse convex optimization. In: Proceedings of Machine Learning Research, vol.\u00a028, pp. 427\u2013435. PMLR, Atlanta, Georgia, USA (17\u201319, 2013). http:\/\/proceedings.mlr.press\/v28\/jaggi13.html"},{"key":"2005_CR25","doi-asserted-by":"publisher","unstructured":"Jiang, H., Lee, Y.T., Song, Z., Wong, S.C.w.: An improved cutting plane method for convex optimization, convex-concave games, and its applications. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 944\u2013953. STOC 2020, Association for Computing Machinery, New York, NY, USA (2020). https:\/\/doi.org\/10.1145\/3357713.3384284","DOI":"10.1145\/3357713.3384284"},{"issue":"4","key":"2005_CR26","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0108053","volume":"8","author":"JE Kelley Jr","year":"1960","unstructured":"Kelley, J.E., Jr.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703\u2013712 (1960)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"2005_CR27","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming (in Russian). Doklady Akademiia Nauk SSSR 224, 1093\u20131096 (1979), English Translation: Soviet Mathematics Doklady 20, 191\u2013194"},{"key":"2005_CR28","doi-asserted-by":"publisher","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.: A faster cutting plane method and its implications for combinatorial and convex optimization. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049\u20131065 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.68","DOI":"10.1109\/FOCS.2015.68"},{"issue":"1","key":"2005_CR29","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BF01585556","volume":"69","author":"Y Nesterov","year":"1995","unstructured":"Nesterov, Y.: Cutting plane algorithms from analytic centers: efficiency estimates. Math. Program. 69(1), 149\u2013176 (1995)","journal-title":"Math. Program."},{"issue":"2","key":"2005_CR30","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2), 257\u2013301 (1995). https:\/\/doi.org\/10.1287\/moor.20.2.257","journal-title":"Math. Oper. Res."},{"issue":"6","key":"2005_CR31","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1037\/h0042519","volume":"65","author":"F Rosenblatt","year":"1958","unstructured":"Rosenblatt, F.: The perceptron: a probabilistic model for information storage and organization in the brain. Psychol. Rev. 65(6), 386\u2013408 (1958). https:\/\/doi.org\/10.1037\/h0042519","journal-title":"Psychol. Rev."},{"issue":"2","key":"2005_CR32","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1145\/77600.77620","volume":"37","author":"F Shahrokhi","year":"1990","unstructured":"Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. J. ACM 37(2), 318\u2013334 (1990). https:\/\/doi.org\/10.1145\/77600.77620","journal-title":"J. ACM"},{"key":"2005_CR33","doi-asserted-by":"crossref","unstructured":"Sonnevend, G.: New algorithms in convex programming based on a notion of \u201ccentre\u201d (for systems of analytic inequalities) and on rational extrapolation. In: Hoffmann, K.H., Zowe, J., Hiriart-Urruty, J.B., Lemarechal, C. (eds.) Trends in Mathematical Optimization: 4th French-German Conference on Optimization, pp. 311\u2013326. Birkh\u00e4user Basel, Basel (1988)","DOI":"10.1007\/978-3-0348-9297-1_20"},{"key":"2005_CR34","unstructured":"UC Irvine Machine Learning Repository. https:\/\/archive-beta.ics.uci.edu\/ml\/datasets. Accessed 3 Sep 2021"},{"issue":"3","key":"2005_CR35","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/bf02592216","volume":"73","author":"PM Vaidya","year":"1996","unstructured":"Vaidya, P.M.: A new algorithm for minimizing convex functions over convex sets. Math. Program. 73(3), 291\u2013341 (1996). https:\/\/doi.org\/10.1007\/bf02592216","journal-title":"Math. Program."},{"key":"2005_CR36","first-page":"357","volume":"12","author":"D Yudin","year":"1976","unstructured":"Yudin, D., Nemirovsky, A.: Informational complexity and efficient methods for solution of convex extremal problems. Econ. Math. Methods 12, 357\u2013369 (1976)","journal-title":"Econ. Math. Methods"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02005-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02005-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02005-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T12:22:02Z","timestamp":1721823722000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02005-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":36,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["2005"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02005-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,8,10]]},"assertion":[{"value":"27 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}