{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:46:21Z","timestamp":1740123981599,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,24]],"date-time":"2024-12-24T00:00:00Z","timestamp":1734998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,24]],"date-time":"2024-12-24T00:00:00Z","timestamp":1734998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Ivannikov Institute for System Programming of the RAS","award":["70-2021-00142"],"award-info":[{"award-number":["70-2021-00142"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2025,1]]},"DOI":"10.1007\/s10957-024-02599-9","type":"journal-article","created":{"date-parts":[[2024,12,24]],"date-time":"2024-12-24T15:54:33Z","timestamp":1735055673000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Accuracy Certificates for Convex Minimization with Inexact Oracle"],"prefix":"10.1007","volume":"204","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9086-996X","authenticated-orcid":false,"given":"Egor","family":"Gladin","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Gasnikov","sequence":"additional","affiliation":[]},{"given":"Pavel","family":"Dvurechensky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,24]]},"reference":[{"issue":"1","key":"2599_CR1","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1287\/moor.22.1.63","volume":"22","author":"KM Anstreicher","year":"1997","unstructured":"Anstreicher, K.M.: On Vaidya\u2019s volumetric cutting plane method for convex programming. Math. Oper. Res. 22(1), 63\u201389 (1997)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2599_CR2","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/S1052623401390902","volume":"13","author":"KM Anstreicher","year":"2002","unstructured":"Anstreicher, K.M.: Improved complexity for maximum volume inscribed ellipsoids. SIAM J. Optim. 13(2), 309\u2013320 (2002)","journal-title":"SIAM J. Optim."},{"issue":"1\u20133","key":"2599_CR3","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\u20133), 1\u201343 (1995)","journal-title":"Math. Program."},{"key":"2599_CR4","doi-asserted-by":"publisher","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004). https:\/\/doi.org\/10.1017\/CBO9780511804441","DOI":"10.1017\/CBO9780511804441"},{"key":"2599_CR5","unstructured":"Bulatov, V.P., Shepot\u2019ko, L.O.: Method of centers of orthogonal simplexes for solving convex programming problems. Methods Optim. Appl. (1982)"},{"key":"2599_CR6","unstructured":"Cohen, M.B., Cousins, B., Lee, Y.T., Yang, X.: A near-optimal algorithm for approximating the John ellipsoid. In: Proceedings of the Thirty-Second Conference on Learning Theory, vol.\u00a099, pp. 849\u2013873. PMLR (2019). https:\/\/proceedings.mlr.press\/v99\/cohen19a.html"},{"issue":"2","key":"2599_CR7","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1137\/110826102","volume":"22","author":"O Devolder","year":"2012","unstructured":"Devolder, O., Glineur, F., Nesterov, Y.: Double smoothing technique for large-scale linearly constrained convex optimization. SIAM J. Optim. 22(2), 702\u2013727 (2012)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"2599_CR8","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1134\/S0965542516040084","volume":"56","author":"AV Gasnikov","year":"2016","unstructured":"Gasnikov, A.V., Gasnikova, E.V., Nesterov, Y.E., Chernov, A.V.: Efficient numerical methods for entropy-linear programming problems. Comput. Math. Math. Phys. 56(4), 514\u2013524 (2016). https:\/\/doi.org\/10.1134\/S0965542516040084","journal-title":"Comput. Math. Math. Phys."},{"key":"2599_CR9","unstructured":"Gladin, E., Lavrik-Karmazin, M., Zainullina, K., Rudenko, V., Gasnikov, A., Takac, M.: Algorithm for constrained markov decision process with linear convergence. In: International Conference on Artificial Intelligence and Statistics, pp. 11506\u201311533. PMLR (2023)"},{"issue":"1","key":"2599_CR10","first-page":"226","volume":"37","author":"LG Khachiyan","year":"1988","unstructured":"Khachiyan, L.G., Tarasov, S.P., Erlikh, I.I.: The method of inscribed ellipsoids. Soviet Math. Dokl 37(1), 226\u2013230 (1988)","journal-title":"Soviet Math. Dokl"},{"issue":"1","key":"2599_CR11","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF01582144","volume":"61","author":"LG Khachiyan","year":"1993","unstructured":"Khachiyan, L.G., Todd, M.J.: On the complexity of approximating the maximal inscribed ellipsoid for a polytope. Math. Program. 61(1), 137\u2013159 (1993). https:\/\/doi.org\/10.1007\/BF01582144","journal-title":"Math. Program."},{"issue":"1","key":"2599_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10957-005-2653-6","volume":"126","author":"P Kumar","year":"2005","unstructured":"Kumar, P., Yildirim, E.A.: Minimum-volume enclosing ellipsoids and core sets. J. Optim. Theory Appl. 126(1), 1\u201321 (2005)","journal-title":"J. Optim. Theory Appl."},{"issue":"6","key":"2599_CR13","first-page":"1244","volume":"160","author":"AY Levin","year":"1965","unstructured":"Levin, A.Y.: A minimization algorithm for convex functions. Dokl. Akad. Nauk SSSR 160(6), 1244\u20131247 (1965)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"1\u20134","key":"2599_CR14","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1080\/10556789908805755","volume":"11","author":"A Nemirovski","year":"1999","unstructured":"Nemirovski, A.: On self-concordant convex\u2013concave functions. Optim. Methods Softw. 11(1\u20134), 303\u2013384 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"2599_CR15","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1287\/moor.1090.0427","volume":"35","author":"A Nemirovski","year":"2010","unstructured":"Nemirovski, A., Onn, S., Rothblum, U.G.: Accuracy certificates for computational problems with convex structure. Math. Oper. Res. 35(1), 52\u201378 (2010)","journal-title":"Math. Oper. Res."},{"key":"2599_CR16","doi-asserted-by":"publisher","unstructured":"Nesterov, Y.: Lectures on Convex Optimization. Springer International Publishing (2018). https:\/\/doi.org\/10.1007\/978-3-319-91578-4","DOI":"10.1007\/978-3-319-91578-4"},{"issue":"3","key":"2599_CR17","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/321281.321291","volume":"12","author":"DJ Newman","year":"1965","unstructured":"Newman, D.J.: Location of the maximum on unimodal surfaces. J. ACM (JACM) 12(3), 395\u2013398 (1965)","journal-title":"J. ACM (JACM)"},{"key":"2599_CR18","unstructured":"Paffenholz, A.: Polyhedral Geometry and Linear Optimization. https:\/\/www2.mathematik.tu-darmstadt.de\/paffenholz\/daten\/preprints\/ln.pdf (2010). Lecture notes, Technische Universit\u00e4t Darmstadt"},{"key":"2599_CR19","volume-title":"Introduction to Optimization","author":"BT Polyak","year":"1987","unstructured":"Polyak, B.T.: Introduction to Optimization. Publications Division, Inc., New York (1987)"},{"issue":"1","key":"2599_CR20","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10107-022-01833-4","volume":"199","author":"A Rodomanov","year":"2023","unstructured":"Rodomanov, A., Nesterov, Y.: Subgradient ellipsoid method for nonsmooth convex problems. Math. Program. 199(1), 305\u2013341 (2023)","journal-title":"Math. Program."},{"key":"2599_CR21","first-page":"42","volume":"1","author":"N Shor","year":"1977","unstructured":"Shor, N.: A cutting method with space dilation for solving convex programming problems. Kibernetika 1, 42\u201350 (1977)","journal-title":"Kibernetika"},{"issue":"13","key":"2599_CR22","doi-asserted-by":"publisher","first-page":"1731","DOI":"10.1016\/j.dam.2007.02.013","volume":"155","author":"MJ Todd","year":"2007","unstructured":"Todd, M.J., Y\u0131ld\u0131r\u0131m, E.A.: On Khachiyan\u2019s algorithm for the computation of minimum-volume enclosing ellipsoids. Discret. Appl. Math. 155(13), 1731\u20131744 (2007)","journal-title":"Discret. Appl. Math."},{"key":"2599_CR23","doi-asserted-by":"crossref","unstructured":"Vaidya, P.M.: A new algorithm for minimizing convex functions over convex sets. In: 30th Annual Symposium on Foundations of Computer Science, pp. 338\u2013343. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63500"},{"issue":"3","key":"2599_CR24","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)","journal-title":"Math. Program."},{"key":"2599_CR25","doi-asserted-by":"crossref","unstructured":"van\u00a0den Brand, J.: A deterministic linear program solver in current matrix multiplication time. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 259\u2013278. SIAM (2020)","DOI":"10.1137\/1.9781611975994.16"},{"key":"2599_CR26","doi-asserted-by":"crossref","unstructured":"Yamnitsky, B., Levin, L.A.: An old linear programming algorithm runs in polynomial time. In: 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pp. 327\u2013328. IEEE (1982)","DOI":"10.1109\/SFCS.1982.63"},{"key":"2599_CR27","unstructured":"Yudin, D.B., Nemirovskii, A.S.: Informational complexity and efficient methods for the solution of convex extremal problems. Matekon 13(2), 22\u201345 (1976)"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-024-02599-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-024-02599-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-024-02599-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T06:34:54Z","timestamp":1737527694000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-024-02599-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,24]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["2599"],"URL":"https:\/\/doi.org\/10.1007\/s10957-024-02599-9","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2024,12,24]]},"assertion":[{"value":"1 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"1"}}