Search

Kernel functions play an important role in the complexity analysis of the interior point methods (IPMs) for linear optimization (LO). In this paper, an interior-point algorithm for LO based on a new parametric kernel function is proposed. By means of some simple analysis tools, we prove that the primal-dual interior-point algorithm for solving LO problems meets (...log(n) log(...)), iteration complexity bound for large-update methods with the special choice of its parameters. [ABSTRACT FROM AUTHOR]

Copyright of Palestine Journal of Mathematics is the property of Palestine Polytechnic University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Our aim in this work is to extend the primal-dual interior point method based on a kernel function for linear fractional problem. We apply the techniques of kernel function-based interior point methods to solve a standard linear fractional program. By relying on the method of Charnes and Cooper [3], we transform the standard linear fractional problem into a linear program. This transformation will allow us to define the associated linear program and solve it efficiently using an appropriate kernel function. To show the efficiency of our approach, we apply our algorithm on the standard linear fractional programming found in numerical tests in the paper of A. Bennani et al. [4], we introduce the linear programming associated with this problem. We give three interior point conditions on this example, which depend on the dimension of the problem. We give the optimal solution for each linear program and each linear fractional program. We also obtain, using the new algorithm, the optimal solutions for the previous two problems. Moreover, some numerical results are illustrated to show the effectiveness of the method.

In this paper, we propose a full-Newton step infeasible interior-point algorithm (IPA) for solving linear optimization problems based on a new kernel function (KF). The latter belongs to the newly introduced hyperbolic type (Guerdouh et al. in An efficient primal-dual interior point algorithm for linear optimization problems based on a novel parameterized kernel function with a hyperbolic barrier term, 2021; Touil and Chikouche in Acta Math Appl Sin Engl Ser 38:44–67, 2022; Touil and Chikouche in Filomat 34:3957–3969, 2020). Unlike feasible IPAs, our algorithm doesn't require a feasible starting point. In each iteration, the new feasibility search directions are computed using the newly introduced hyperbolic KF whereas the centering search directions are obtained using the classical KF. A simple analysis for the primal-dual infeasible interior-point method (IIPM) based on the new KF shows that the iteration bound of the algorithm matches the currently best iteration bound for IIPMs. We consolidate these theoretical results by performing some numerical experiments in which we compare our algorithm with the famous SeDuMi solver. To our knowledge, this is the first full-Newton step IIPM based on a KF with a hyperbolic barrier term. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in the complexity analysis of the interior point methods (IPMs) for linear optimization (LO). In this paper, an interior-point algorithm for LO based on a new parametric kernel function is proposed. By means of some simple analysis tools, we prove that the primal-dual interior-point algorithm for solving LO problems meets ..., iteration complexity bound for large-update methods with the special choice of its parameters. [ABSTRACT FROM AUTHOR]

In this paper, we propose a primal–dual interior point method for Linear Complementarity Problem (LCP) based on a new parameterized kernel function. The investigation according to it yields the best-known iteration bound O (n log ⁡ (n) log ⁡ (n ϵ)) for large-update algorithm and thus improves the iteration bound obtained in Bai et al. (SIAM J Optim. 2004;15:101–128) for large-update algorithm. Finally, we present few numerical results to demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper we are generalizing the efficient kernel function with trigonometric barrier term given by (M. Bouafia, D. Benterki and A. Yassine, J. Optim. Theory Appl.170 (2016) 528–545). Using an elegant and simple analysis and under some easy to check conditions, we explore the best complexity result for the large update primal-dual interior point methods for linear optimization. This complexity estimate improves results obtained in (X. Li and M. Zhang, Oper. Res. Lett.43 (2015) 471–475; M.R. Peyghami and S.F. Hafshejani, Numer. Algo.67 (2014) 33–48; M. Bouafia, D. Benterki and A. Yassine, J. Optim. Theory Appl.170 (2016) 528–545). Our comparative numerical experiments on some test problems consolidate and confirm our theoretical results according to which the new kernel function has promising applications compared to the kernel function given by (M. Bouafia and A. Yassine, Optim. Eng.21 (2020) 651–672). Moreover, the comparative numerical study that we have established favors our new kernel function better than other best trigonometric kernel functions (M. Bouafia, D. Benterki and A. Yassine, J. Optim. Theory Appl.170 (2016) 528–545; M. Bouafia and A. Yassine, Optim. Eng.21 (2020) 651–672). [ABSTRACT FROM AUTHOR]

In this paper, a wide neighborhood path-following interior point algorithm for linear optimization (LO) is proposed that uses a trigonometric kernel function to get search directions. The method treats the Newton direction as the sum of two other directions, according to the negative and positive parts of the right-hand-side based on the kernel function. By choosing different and appropriate step sizes for these two directions, the iterates stop in the Ai–Zhang's wide neighborhood. By an elegant analysis, we show that the method enjoys the low iteration bound of O (n log (x 0) T s 0 ε) , where n is the dimension of the problem and (x 0 , s 0) the initial interior point with ε the required precision. In our knowledge, this result is the first instance of a wide neighborhood interior point method for LO which involving the trigonometric kernel function. [ABSTRACT FROM AUTHOR]

Recently, Bouafia et al. (J Optim Theory Appl 170:528–545, 2016) investigated a new efficient kernel function that differs from self-regular kernel functions. The kernel function has a trigonometric barrier term. This paper introduces a new efficient twice parametric kernel function that combines the parametric classic function with the parametric kernel function trigonometric barrier term given by Bouafia et al. (J Optim Theory Appl 170:528–545, 2016) to develop primal–dual interior-point algorithms for solving linear programming problems. In addition, we obtain the best complexity bound for large and small-update primal–dual interior point methods. This complexity estimate improves results obtained in Li and Zhang (Oper Res Lett 43(5):471–475, 2015), Peyghami and Hafshejani (Numer Algorithms 67:33–48, 2014) and matches the best bound obtained in Bai et al. (J Glob Optim 54:353–366) and Peng et al. (J Comput Technol 6:61–80, 2001). Finally, our numerical experiments on some test problems confirm that the new kernel function has promising applications compared to the kernel function given by Fathi-Hafshejani (Optimization 67(10):1605–1630, 2018). [ABSTRACT FROM AUTHOR]

In this paper, we propose a large-update primal-dual interior-point algorithm for linear optimization problems based on a new kernel function with a trigonometric growth term. By simple analysis, we prove that in the large neighbourhood of the central path, the worst case iteration complexity of the new algorithm is bounded above by , which matches the currently best known iteration bound for large-update methods. Moreover, we show that, most of the so far proposed kernel functions can be rewritten as a kernel function with trigonometric growth term. Finally, numerical experiments on some test problems confirm that the new kernel function is well promising in practice in comparison with some existing kernel functions in the literature. [ABSTRACT FROM AUTHOR]

The introduction of kernel function in primal-dual interior point methods represents not only a measure of the distance between the iterate and the central path, but also plays an important role in the amelioration of the computational complexity of an interior point algorithm. In this work, we present a primal-dual interior point method for linear optimization problems based on a new kernel function with an efficient logarithmic barrier term. We derive the complexity bounds for large and small-update methods respectively. We obtain the best known complexity bound for large-update given by Peng et al., which improves significantly the so far obtained complexity results based on a logarithmic kernel function given by El Ghami et al. The results obtained in this paper are the first with respect to the kernel function with a logarithmic barrier term. [ABSTRACT FROM AUTHOR]

In this paper, we propose a large-update interior-point algorithm for linear optimization based on a new kernel function. New search directions and proximity measure are defined based on this kernel function. We show that if a strictly feasible starting point is available, then the new algorithm has O(3/4log n/ε) iteration complexity.

Kernel function plays an important role in defining new search directions for primaldual interior point algorithm for solving linear optimization problems. This problem has attracted the attention of many researchers for some years. The goal of their works is to find kernel functions that improve algorithmic complexity of this problem. In this paper, we introduce a real parameter p > 0 to generalize the kernel function (5) given by Bai et al. in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101-128.], and give the corresponding primal-dual interior point methods for linear optimization. This parameterized kernel function yields the similar complexity bound given in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101-128.] for both large-update and small-update methods. [ABSTRACT FROM AUTHOR]

In this paper, we present a primal-dual interior point method for linear optimization problems based on a new efficient kernel function with a trigonometric barrier term. We derive the complexity bounds for large and small-update methods, respectively. We obtain the best known complexity bound for large update, which improves significantly the so far obtained complexity results based on a trigonometric kernel function given by Peyghami et al. The results obtained in this paper are the first to reach this goal. [ABSTRACT FROM AUTHOR]

In this paper, we propose a primal-dual interior point method for linear optimization (LO) based on a new parameterized kernel function. The proposed kernel function is a generalization of the one used recently in Bai et al. (SIAM J Optim 15:101–128, 2004) for LO. The investigation according to it yields the best known iteration bound O(√n log n log n/ϵ) for large-update algorithm and thus improves the iteration bound obtained in Bai et al. (SIAM J Optim 15:101–128, 2004) for large-update algorithm. Finally, we present few numerical results to demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm. In this paper, a new kernel function which its barrier term is integral type is proposed. We study the properties of the new kernel function, and give a primal-dual interior-point algorithm for solving linear optimization based on the new kernel function. Polynomial complexity of algorithm is analyzed. The iteration bounds both for large-update and for small-update methods are obtained, respectively. The iteration bound for small-update method is the best known complexity bound. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in the complexity analysis of the interior point methods for linear optimization. In this paper, we present a primal-dual interior point method for linear optimization based on a new kernel function consisting of a trigonometric function in its barrier term. By simple analysis, we show that the feasible primal-dual interior point methods based on the new proposed kernel function enjoys $O\left (\sqrt {n}\left (\log {n}\right )^{2}\log \frac {n}{\epsilon }\right )$ worst case complexity result which improves the results obtained by El Ghami et al. (J Comput Appl Math 236:3613-3623, 2012) for the kernel functions with trigonometric barrier terms. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we propose a new kernel function with trigonometric barrier term for primal–dual interior point methods in linear optimization. Using an elegant and simple analysis and under some easy to check conditions, we explore the worst case complexity result for the large update primal–dual interior point methods. We obtain the worst case iteration bound for the large update primal–dual interior point methods as which improves the so far obtained complexity results for the trigonometric kernel function in [M. El Ghami, Z.A. Guennoun, S. Boula, T. Steihaug, Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term, Journal of Computational and Applied Mathematics 236 (2012) 3613–3623] significantly. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new barrier function for primal–dual interior-point methods in linear optimization. The proposed kernel function has a trigonometric barrier term. It is shown that in the interior-point methods based on this function for large-update methods, the iteration bound is improved significantly. For small-update interior-point methods, the iteration bound is the best currently known bound for primal–dual interior-point methods. [Copyright &y& Elsevier]

In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large- and small-update methods are derived, namely, O( nlog( n/ɛ)) and $O(\sqrt n \log (n/\varepsilon ))$. This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other primal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions. [ABSTRACT FROM AUTHOR]

Abstract: Primal–dual interior-point methods (IPMs) are the most efficient methods for a computational point of view. At present the theoretical iteration bound for small-update IPMs is better than the one for large-update IPMs. However, in practice, large-update IPMs are much more efficient than small-update IPMs. Peng et al. proposed new variants of IPMs based on self-regular barrier functions and proved so far the best known complexity, e.g. , for large-update IPMs with some specific self-regular barrier functions. Recently, Roos et al. proposed new primal–dual IPMs based on various barrier functions to improve the iteration bound for large-update methods from to . Motivated by their works we define a new barrier function and propose a new primal–dual interior point algorithm based on this function for linear optimization (LO) problems. We show that the new algorithm has iteration bound for large-update and for small-update methods which are currently the best known bounds, respectively. [Copyright &y& Elsevier]

Abstract: Interior point methods have shown their powers in solving linear optimization problems and large classes of other optimization problems. However, at present there is still a gap between the practical behavior of these algorithms and their theoretical worst case complexity. The so-called large update interior point methods perform in practice much better than the small update methods which have the best known theoretical complexity. Recently, this gap has been reduced by Peng, Roos and Terlaky by introducing new self regular kernel functions. In this paper, by focusing on linear optimization problem and motivated by the self regular family of kernel functions, we impose some mild condition on the kernel functions and we give a new class of kernel functions. We also give a simple complexity analysis for large-update interior point methods based on the kernel functions in this new class. Finally, we apply our analysis to two family of kernel functions in our new class. We also explore the complexity of the algorithm and we show that the so far worst case iteration bound can be achieved in special case. [Copyright &y& Elsevier]