A New Parametric Kernel Function Based on p-generalized Sigmoid Function for the Primal-dual Interior Point Method of Linear Optimization

Abstract

For the purpose of linear optimization, we propose a novel parametric kernel function situated within the context of the primal-dual interior point methodology. This function incorporates a logarithmic barrier term and a p-generalized sigmoid function. To evaluate the complexity associated with iterations of the algorithm, we consider various simple cases and mild conditions. The results show that the iteration bounds for the small- and large-update interior point methods constructed with these functions are, respectively, given by O (√n/p log (n/ε)) andO (n/p3 log (n/ε)). By selecting a specific parameter p, the primal-dual interior point methods based on this kernel function can achieve an optimal iteration bound of O(√nlog(n)log (n/ε)) for large update methods. This bound is consistent with the known complexity results for linear and semidefinite optimization problems obtained from self-regular kernel functions. In order to demonstrate the effectiveness of the new kernel function, we present numerical results from several test problems, which confirm that the optimal number of iterations has been achieved.

Keywords: kernel function, interior-point algorithms, linear optimization, primal-dual methods.

2010 Mathematics Subject Classification. 90C51; 90C05