Search

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: In this paper, we propose a new large-update primal–dual interior point algorithm for complementarity problems (CPs). Different from most interior point methods which are based on the logarithmic kernel function, the new method is based on a class of kernel functions ,, . We show that if a strictly feasible starting point is available and the undertaken problem satisfies some conditions, then the new large-update primal–dual interior point algorithm for CPs has iteration complexity which is currently the best known result for such methods with and . [Copyright &y& Elsevier]

Abstract: In this paper we propose a new large-update primal-dual interior point algorithm for linear complementarity problems (LCPs). We generalize Bai et al.''s [A primal-dual interior-point method for linear optimization based on a new proximity function, Optim. Methods Software 17(2002) 985–1008] primal-dual interior point algorithm for linear optimization (LO) problem to LCPs. New search directions and proximity measures are proposed based on a kernel function which is not logarithmic barrier nor self-regular for LCPs. We showed that if a strictly feasible starting point is available, then the new large-update primal-dual interior point algorithm for solving LCPs has the polynomial complexity and gives a simple complexity analysis. This proximity function has not been used in the complexity analysis of interior point method (IPM) for LCPs before. [Copyright &y& Elsevier]

Abstract: In this paper we propose a new large-update primal-dual interior point algorithm for P ∗(κ) linear complementarity problems (LCPs). Recently, Peng et al. introduced self-regular barrier functions for primal-dual interior point methods (IPMs) for linear optimization (LO) problems and reduced the gap between the practical behavior of the algorithm and its theoretical worst case complexity. We introduce a new class of kernel functions which is not logarithmic barrier nor self-regular in the complexity analysis of interior point method (IPM) for P ∗(κ) linear complementarity problem (LCP). New search directions and proximity measures are proposed based on the kernel function. We showed that if a strictly feasible starting point is available, then the new large-update primal-dual interior point algorithms for solving P ∗(κ) LCPs have the polynomial complexity which is better than the classical large-update primal-dual algorithm based on the classical logarithmic barrier function. [Copyright &y& Elsevier]

Abstract: In this paper we present a log-barrier method for solving two-stage quadratic stochastic programs. The mathematical model considered here can be used to present several real world applications, including financial and production planning problems. We discuss fundamental properties associated with the proposed algorithm and analyze the convergence and complexity of the algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we propose new large-update path-following interior-point algorithms for -nonlinear complementarity problems (NCPs). We define new classes of parametric kernel functions and based on these functions new search directions and proximity measures are defined. We show that if a strictly feasible starting point is available and the undertaken problem satisfies certain conditions, then new large-update path-following interior-point algorithms for -NCPs have iteration complexity which is currently the best known result for such methods. [Copyright &y& Elsevier]

Abstract: A common feature shared by most practical algorithms in interior point methods is the use of Mehrotra’s predictor–corrector algorithm in [S. Mehrotra, On the implementation of a (primal-dual) interior point method, SIAM Journal on Optimization 2 (1992) 575–601.] where the predictor step is never performed but it is used only to calculate an adaptive update, and thus instead of a predictor and a corrector centering step, a single Newton step is made toward the adaptively chosen target. In this paper we propose a new adaptive single-step large-update primal-dual interior point algorithm with wide neighborhood for linear optimization(LO) problems based on the simple kernel function which is first defined in [Y.Q. Bai, C. Roos, A primal-dual interior-point method based on a new kernel function with linear growth rate, in: Proceedings of Industrial Optimization Symposium and Optimization Day, Nov., 2002]. We show that the algorithm has complexity which is similar to the one in the above-mentioned reference. [Copyright &y& Elsevier]