An inexact infeasible arc-search interior-point method for linear optimization problems

An inexact infeasible arc-search interior-point method for linear optimization problems | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article An inexact infeasible arc-search interior-point method for linear optimization problems Einosuke Iida, Makoto Yamashita This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7144611/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 20 Apr, 2026 Read the published version in Numerical Algorithms → Version 1 posted 9 You are reading this latest preprint version Abstract We propose an inexact infeasible arc-search interior-point method (IPM) for solving linear optimization problems. The method combines an arc-search strategy with inexact solutions to Newton systems and admits an iteration complexity bound that is polynomial in the problem size. Compared with an existing inexact infeasible line-search IPM, the proposed IPM achieves a tighter worst-case iteration bound. Numerical experiments on NETLIB benchmark problems demonstrate that the proposed IPM reduces both the number of iterations and the computation time. interior-point method arc-search inexact IPM infeasible IPM linear optimization Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 20 Apr, 2026 Read the published version in Numerical Algorithms → Version 1 posted Editorial decision: Revision requested 15 Oct, 2025 Reviews received at journal 14 Oct, 2025 Reviews received at journal 01 Oct, 2025 Reviewers agreed at journal 31 Jul, 2025 Reviewers agreed at journal 23 Jul, 2025 Reviewers invited by journal 23 Jul, 2025 Editor assigned by journal 23 Jul, 2025 Submission checks completed at journal 22 Jul, 2025 First submitted to journal 16 Jul, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7144611","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":489884979,"identity":"01088d8a-fa07-4518-bc69-b5cea338110b","order_by":0,"name":"Einosuke Iida","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABHUlEQVRIiWNgGAWjYBAC9gaGhANAmgfCrQBiZiBmbABzE7Bp4TmAouUMkMXMTFALEmBsA2lGaMEKeCQSHh66UXFPBuhExg8/521jsGfnP/jg5w4Gef4GhmcPsGtJOJxzppgHaB+zZO+22yCHMRv2nmEwnHGAId0AixZ7kJbctgQeBokEBgleiBY2aaALGTcwMKRJ4LIFrEX+AfPPv3PAWth/A7XYE9YiwcAmzdsAsYUZqCURpxaeByC/JPCw8SS2Wcscu83Dc5jZWLK3TSJ5xmHsfuFhz0n+nFORYM/PfvjwzTc1t+XY+w8+/PCzzca2v70nDVuIATUlgCk2aFxA4xToTgZmnjSsOhjYD2AXB0kdwyk1CkbBKBgFIwkAAA/0WHM0LphsAAAAAElFTkSuQmCC","orcid":"","institution":"Institute of Science Tokyo","correspondingAuthor":true,"prefix":"","firstName":"Einosuke","middleName":"","lastName":"Iida","suffix":""},{"id":489884980,"identity":"42a02d06-8889-4abc-8bbc-bdd6fd77769f","order_by":1,"name":"Makoto Yamashita","email":"","orcid":"","institution":"Institute of Science Tokyo","correspondingAuthor":false,"prefix":"","firstName":"Makoto","middleName":"","lastName":"Yamashita","suffix":""}],"badges":[],"createdAt":"2025-07-17 03:53:25","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7144611/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7144611/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s11075-026-02374-z","type":"published","date":"2026-04-20T15:58:45+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":107928195,"identity":"28c176f6-3694-4c82-a785-a154ff8f078d","added_by":"auto","created_at":"2026-04-27 16:09:17","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":361781,"visible":true,"origin":"","legend":"","description":"","filename":"article.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7144611/v1_covered_0537d2a6-1e6a-48fc-bb70-c271fd1c3762.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"An inexact infeasible arc-search interior-point method for linear optimization problems","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"numerical-algorithms","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"numa","sideBox":"Learn more about [Numerical Algorithms](http://link.springer.com/journal/11075)","snPcode":"11075","submissionUrl":"https://submission.nature.com/new-submission/11075/3","title":"Numerical Algorithms","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"interior-point method, arc-search, inexact IPM, infeasible IPM, linear optimization","lastPublishedDoi":"10.21203/rs.3.rs-7144611/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7144611/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003e We propose an inexact infeasible arc-search interior-point method (IPM) for solving linear optimization problems. The method combines an arc-search strategy with inexact solutions to Newton systems and admits an iteration complexity bound that is polynomial in the problem size. Compared with an existing inexact infeasible line-search IPM, the proposed IPM achieves a tighter worst-case iteration bound. Numerical experiments on NETLIB benchmark problems demonstrate that the proposed IPM reduces both the number of iterations and the computation time.\u003c/p\u003e","manuscriptTitle":"An inexact infeasible arc-search interior-point method for linear optimization problems","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-07-25 09:28:16","doi":"10.21203/rs.3.rs-7144611/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-10-15T06:19:52+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-10-14T21:50:03+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-10-01T22:48:06+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"5437658421720055645889934005442960728","date":"2025-07-31T14:54:19+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"32418066134713450391376739296072422489","date":"2025-07-23T16:07:58+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-07-23T11:56:42+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-07-23T09:49:40+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-07-23T03:49:51+00:00","index":"","fulltext":""},{"type":"submitted","content":"Numerical Algorithms","date":"2025-07-17T03:45:12+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"numerical-algorithms","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"numa","sideBox":"Learn more about [Numerical Algorithms](http://link.springer.com/journal/11075)","snPcode":"11075","submissionUrl":"https://submission.nature.com/new-submission/11075/3","title":"Numerical Algorithms","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"93e751bd-8895-48e1-b05b-ce6bdd360b60","owner":[],"postedDate":"July 25th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2026-04-27T16:06:49+00:00","versionOfRecord":{"articleIdentity":"rs-7144611","link":"https://doi.org/10.1007/s11075-026-02374-z","journal":{"identity":"numerical-algorithms","isVorOnly":false,"title":"Numerical Algorithms"},"publishedOn":"2026-04-20 15:58:45","publishedOnDateReadable":"April 20th, 2026"},"versionCreatedAt":"2025-07-25 09:28:16","video":"","vorDoi":"10.1007/s11075-026-02374-z","vorDoiUrl":"https://doi.org/10.1007/s11075-026-02374-z","workflowStages":[]},"version":"v1","identity":"rs-7144611","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7144611","identity":"rs-7144611","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}