Scholarlink

<p>Interior-point methods are among the most efficient algorithms for solving linear programming problems. The performance of these methods depends significantly on the choice of the barrier function, particularly in large-update methods, where step sizes are more assertive. In this paper, we introduce a new logarithmic kernel function designed to enhance the efficiency of large-update methods. We establish that the proposed kernel function leads to an iteration complexity of <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1907_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="93" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathscr {O}}(\sqrt{n} \log \frac{ n}{\epsilon }),\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msqrt> <mi>n</mi> </msqrt> <mo>log</mo> <mfrac> <mi>n</mi> <mi>ϵ</mi> </mfrac> <mo stretchy="false">)</mo> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> which matches the best-known complexity bound for small-update methods. This result contributes to closing the theoretical gap between large- and small-update approaches. To validate our findings, we conduct numerical experiments that compare the performance of our approach against existing methods. The results show that our kernel function not only preserves theoretical guarantees but also improves practical efficiency.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Closing the Iteration Gap in Linear Programming with a New Kernel Function

  • 期刊论文

  • 发表日期：

    2025年6月21日

查看全文
  • Imene Touil

摘要

Interior-point methods are among the most efficient algorithms for solving linear programming problems. The performance of these methods depends significantly on the choice of the barrier function, particularly in large-update methods, where step sizes are more assertive. In this paper, we introduce a new logarithmic kernel function designed to enhance the efficiency of large-update methods. We establish that the proposed kernel function leads to an iteration complexity of \({\mathscr {O}}(\sqrt{n} \log \frac{ n}{\epsilon }),\) O ( n log n ϵ ) , which matches the best-known complexity bound for small-update methods. This result contributes to closing the theoretical gap between large- and small-update approaches. To validate our findings, we conduct numerical experiments that compare the performance of our approach against existing methods. The results show that our kernel function not only preserves theoretical guarantees but also improves practical efficiency.