کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
471516 698638 2007 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity of large-update interior point algorithm for P∗(κ)P∗(κ) linear complementarity problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Complexity of large-update interior point algorithm for P∗(κ)P∗(κ) linear complementarity problems
چکیده انگلیسی

In this paper we propose a new large-update primal–dual interior point algorithm for P∗(κ)P∗(κ) linear complementarity problems (LCPs). We extend Bai et al.’s primal–dual interior point algorithm for linear optimization (LO) problems to P∗(κ)P∗(κ) LCPs with generalized kernel functions. New search directions and proximity functions are proposed based on a simple kernel function which is neither a logarithmic barrier nor a self-regular. We show that if a strictly feasible starting point is available, then the new large-update primal–dual interior point algorithms for solving P∗(κ)P∗(κ) LCPs have O((1+2κ)nlognμ0ε) polynomial complexity which is similar to the polynomial complexity obtained for LO and give a simple complexity analysis. This proximity function has not been used in the complexity analysis of interior point method (IPM) for P∗(κ)P∗(κ) LCPs before.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Mathematics with Applications - Volume 53, Issue 6, March 2007, Pages 948–960
نویسندگان
, , ,