An Efficient Hyperbolic Kernel Function Yielding the Best Known Iteration Bounds for Linear Programming  

作　　者：Imene TOUIL Wided CHIKOUCHE Djamel BENTERKI Amina ZERARI 

机构地区：[1]LMPA,Mohammed Seddik Ben Yahia University,PO Box 98,Ouled Aissa,18000 Jijel,Algeria [2]LMFN,Ferhat Abbas University,Setif 19000,Algeria

出　　处：《Acta Mathematicae Applicatae Sinica》2025年第1期133-151,共19页应用数学学报(英文版)

摘　　要：Interior-point methods(IPMs) for linear programming(LP) are generally based on the logarithmic barrier function. Peng et al.(J. Comput. Technol. 6: 61–80, 2001) were the first to propose non-logarithmic kernel functions(KFs) for solving IPMs. These KFs are strongly convex and smoothly coercive on their domains.Later, Bai et al.(SIAM J. Optim. 15(1): 101–128, 2004) introduced the first KF with a trigonometric barrier term. Since then, no new type of KFs were proposed until 2020, when Touil and Chikouche(Filomat. 34(12):3957–3969, 2020;Acta Math. Sin.(Engl. Ser.), 38(1): 44–67, 2022) introduced the first hyperbolic KFs for semidefinite program(ming(SD)P). They( establishe)d that the iteration complexities of algorithms based on their proposed KFs are O(n2/3log(n/ε) and O(n3/4log(n/ε)) for large-update methods, respectively. The aim of this work is to improve the complexity result for large-update method. In fact, we present a new parametric KF with a hyperbolic barrier term. By simple tools, we show that the worst-case iteration complexity of our algorithm for the large-update method is O(√n log n log(n/ε)) iterations. This coincides with the currently best-known iteration bounds for IPMs based on all existing kind of KFs.The algorithm based on the proposed KF has been tested. Extensive numerical simulations on test problems with different sizes have shown that this KF has promising results.

关 键 词：linear programming primal-dual interior-point methods kernel functions complexity analysis large and small-update methods 

分 类 号：O221.1[理学—运筹学与控制论]