New interior-point methods for linear optimization problem

doi:10.1007/s11590-026-02286-w

New interior-point methods for linear optimization problem

2026-03-01

0

PRE

AI

DOI：10.1007/s11590-026-02286-w

原文链接

原文求助

摘要

En 中文

本文提出了一种基于Cho和Cho（J Nonlinear Convex Anal 22:901-917, 2021）中最初定义的广义核函数类的新型内点法求解线性优化问题。基于这些核函数定义了新的搜索方向和邻近度量。我们证明了对于大步长方法，迭代复杂度为O(√n(log n) log n µ(0)/ε)，对于小步长方法，迭代复杂度为O(√n log n µ(0)/ε)，其中n为问题维度，µ(0) > 0，ε > 0。这些是目前此类方法在理论上最佳复杂度结果。最后，给出了数值算例以验证所提方法的效率。在包括36个随机生成问题、25个NETLIB基准问题（Koch in Oper Res Lett 32:138-142, 2004）和41个来自Bouafia等（J Optim Theory Appl 170(2):528-545, 2016）的实例的测试案例中，本方法在84%的案例中达到了最少的迭代次数和最短的运行时间。

Keyword:

Interior-point method

Linear optimization

Long- and short-step methods

Kernel function

Complexity

New interior-point methods for linear optimization problem

摘要

期刊

机构

引用论文