Backtracking New Q-Newton’s Method

Backtracking New Q-Newton’s Method | 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 Backtracking New Q-Newton’s Method Tuyen Trung Truong This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-9111824/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract In this paper, we introduce a new Newton-type method-named Backtracking New Q-Newton’s method (BNQN)-which retains the same quick local rate of convergence while having much stronger global convergence guarantees. It is a combination of a previously designed algorithm (New Q-Newton’s method) and Armijo’s Backtracking line search. The main contribution of this paper is as follows: We prove that this new algorithm, applied to a general C 3 cost function f , has the following good properties: For a sequence {xn} constructed by this algorithm from a random initial point x0: -Finding critical points: Any cluster point of the sequence is a critical point of f . -Fast convergence rate: Near any non-degenerate local minimum, it has local quadratic convergence rate. -Avoidance of saddle points: If x0 is outside an exceptional set of Lebesgue measure 0, then {xn} cannot converge to a saddle points. BNQN is the first variant of Newton’s method in the literature satisfying all these 3 properties. We also prove some further results, and propose some other variants. We illustrate the main results with both theoretical and experimental examples. 2020 Mathematics Subject Classification. 37N40, 49M15, 49M37, 65Exx, 65Hxx, 65K05, 90C26. Backtracking line search Basin of attraction Convergence guarantee Dynamical systems Lojasiewicz gradient inequality Optimization Newton’s method Random processes Rate of convergence Root finding Saddle points Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted 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-9111824","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":614027529,"identity":"218ca45c-6833-417f-9f36-5b35d7d657b3","order_by":0,"name":"Tuyen Trung Truong","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAyElEQVRIiWNgGAWjYBADOSBmA2IJwkp5wGSCgTEDAzOJWhIbIFqIAPYSOYaPC3/8SV/bfv7YA8Y2CzkG6eYD+G2RyDE2npFgkLvtTDK7AWObhDGDzLEEQlrMpHlAWg4ks0kAtSQ2SOQYENJi/huoJd3s/GPitZgxA7UkmN0g2pYzz4qledKMDbfdeGwmkXBOwphNIg2/X9jbkzd+5rGRkzc7n/hM4kNZnRy/RPIBvFoYGDiQnAEynojYYX9AWM0oGAWjYBSMbAAAspU5Hnk5Ae8AAAAASUVORK5CYII=","orcid":"","institution":"University of Oslo","correspondingAuthor":true,"prefix":"","firstName":"Tuyen","middleName":"Trung","lastName":"Truong","suffix":""}],"badges":[],"createdAt":"2026-03-13 07:53:15","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-9111824/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-9111824/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":105783378,"identity":"a1a75964-919c-4a6e-9d01-a145accc53a5","added_by":"auto","created_at":"2026-03-31 05:56:22","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1172664,"visible":true,"origin":"","legend":"","description":"","filename":"NewQNewtonPlusImprovement2025.pdf","url":"https://assets-eu.researchsquare.com/files/rs-9111824/v1_covered_9b0a46d9-bb3f-491b-b20b-eff3d357078d.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"\u003cp\u003eBacktracking New Q-Newton’s Method\u003c/p\u003e","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Backtracking line search, Basin of attraction, Convergence guarantee, Dynamical systems, Lojasiewicz gradient inequality, Optimization, Newton’s method, Random processes, Rate of convergence, Root finding, Saddle points","lastPublishedDoi":"10.21203/rs.3.rs-9111824/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-9111824/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eIn this paper, we introduce a new Newton-type method-named Backtracking New Q-Newton’s method (BNQN)-which retains the same quick local rate of convergence while having much stronger global convergence guarantees. It is a combination of a previously designed algorithm (New Q-Newton’s method) and Armijo’s Backtracking line search. The main contribution of this paper is as follows: We prove that this new algorithm, applied to a general C 3 cost function f , has the following good properties: For a sequence {xn} constructed by this algorithm from a random initial point x0:\u003c/p\u003e\n\u003cp\u003e-Finding critical points: Any cluster point of the sequence is a critical point of f .\u003c/p\u003e\n\u003cp\u003e-Fast convergence rate: Near any non-degenerate local minimum, it has local quadratic convergence rate.\u003c/p\u003e\n\u003cp\u003e-Avoidance of saddle points: If x0 is outside an exceptional set of Lebesgue measure 0, then {xn} cannot converge to a saddle points.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eBNQN is the first variant of Newton’s method in the literature satisfying all these 3 properties.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eWe also prove some further results, and propose some other variants. We illustrate the main results with both theoretical and experimental examples.\u003c/p\u003e\n\u003cp\u003e2020 Mathematics Subject Classification. 37N40, 49M15, 49M37, 65Exx, 65Hxx, 65K05, 90C26.\u003c/p\u003e","manuscriptTitle":"Backtracking New Q-Newton’s Method","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-03-31 05:54:41","doi":"10.21203/rs.3.rs-9111824/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"9a248a52-d5c9-41f3-ae2c-413e73d1f061","owner":[],"postedDate":"March 31st, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2026-03-31T05:54:41+00:00","versionOfRecord":[],"versionCreatedAt":"2026-03-31 05:54:41","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-9111824","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-9111824","identity":"rs-9111824","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}