P*(κ)}线性互补问题的满Newton步不可行内点算法

数学物理学报 ›› 2013, Vol. 33 ›› Issue (4): 746-758.

P_*(κ)}线性互补问题的满Newton步不可行内点算法

朱丹花|张明望

三峡大学理学院湖北宜昌 443002

收稿日期:2011-09-20 修回日期:2013-01-28 出版日期:2013-08-25 发布日期:2013-08-25
基金资助:
湖北省自然科学基金(2008CDZ047)和湖北省教育厅自然科学研究项目(Q20111208)资助

A New Full-Newton Infeasible Interior-point Algorithm for P_*(κ) Linear Complementarity Problem

ZHU Dan-Hua, ZHANG Ming-Wang

College of Science, China Three Gorges University, Hubei Yichang 443002

Received:2011-09-20 Revised:2013-01-28 Online:2013-08-25 Published:2013-08-25
Supported by:
湖北省自然科学基金(2008CDZ047)和湖北省教育厅自然科学研究项目(Q20111208)资助

摘要/Abstract

摘要：

对P_*(κ)线性互补问题(LCP)提出了一种新的不可行内点算法,新算法是Mansouri等人最近对单调LCP提出的满Newton步不可行内点算法的改进和推广.通过在收敛分析中建立一些新的技术性结果,克服了P_*(κ)~LCP的非单调性给收敛分析带来的困难, 证明了新算法的迭代复杂性为O((1+4κ)²nlogmax{(x⁰)^Ts⁰, ||r⁰||/ε)).

关键词: P_*(κ)线性互补问题, 不可行内点算法, 满Newton步, 项式复杂性

Abstract:

This paper presents a new infeasible interior-point algorithm for P_*(κ) linear complementarity problems(LCP), which is an extension and improvement of a full-Newton step infeasible interior-point algorithm for monotone LCP proposed by Hansouri et al recently. With the non-monotone of the P_*(κ) LCP, we introduce some new technical results and
prove that the algorithm has iteration complexity with O((1+4κ)²nlogmax{(x⁰)^Ts⁰, ||r⁰||/ε)).

Key words: P_*(κ) linear complementarity problem, Infeasible interior-point methods, Full-Newton step, Polynomial complexity

中图分类号:

90C33

朱丹花, 张明望. P_*(κ)}线性互补问题的满Newton步不可行内点算法[J]. 数学物理学报, 2013, 33(4): 746-758.

ZHU Dan-Hua, ZHANG Ming-Wang. A New Full-Newton Infeasible Interior-point Algorithm for P_*(κ) Linear Complementarity Problem[J]. Acta mathematica scientia,Series A, 2013, 33(4): 746-758.