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 functi...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.展开更多
In this paper,we introduce for the first time a new eligible kernel function with a hyperbolic barrier term for semidefinite programming(SDP).This add a new type of functions to the class of eligible kernel functions....In this paper,we introduce for the first time a new eligible kernel function with a hyperbolic barrier term for semidefinite programming(SDP).This add a new type of functions to the class of eligible kernel functions.We prove that the interior-point algorithm based on the new kernel function meets O(n3/4 logε/n)iterations as the worst case complexity bound for the large-update method.This coincides with the complexity bound obtained by the first kernel function with a trigonometric barrier term proposed by El Ghami et al.in2012,and improves with a factor n(1/4)the obtained iteration bound based on the classic kernel function.We present some numerical simulations which show the effectiveness of the algorithm developed in this paper.展开更多
文摘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.
文摘In this paper,we introduce for the first time a new eligible kernel function with a hyperbolic barrier term for semidefinite programming(SDP).This add a new type of functions to the class of eligible kernel functions.We prove that the interior-point algorithm based on the new kernel function meets O(n3/4 logε/n)iterations as the worst case complexity bound for the large-update method.This coincides with the complexity bound obtained by the first kernel function with a trigonometric barrier term proposed by El Ghami et al.in2012,and improves with a factor n(1/4)the obtained iteration bound based on the classic kernel function.We present some numerical simulations which show the effectiveness of the algorithm developed in this paper.
