首页 | 本学科首页   官方微博 | 高级检索  
     检索      

一类新的求解P_*(κ)阵线性互补问题的多项式内点算法
引用本文:龚小玉,胡振鹏,王先甲,张明望.一类新的求解P_*(κ)阵线性互补问题的多项式内点算法[J].数学的实践与认识,2011,41(3).
作者姓名:龚小玉  胡振鹏  王先甲  张明望
作者单位:1. 武汉大学,水利水电学院,湖北,武汉,430072;广东石油化工学院,理学院,广东,茂名,525000
2. 武汉大学,水利水电学院,湖北,武汉,430072
3. 武汉大学经济与管理学院,湖北,武汉,430072
4. 三峡大学理学院,湖北,宜昌,443002
基金项目:国家自然科学基金(71071119)
摘    要:利用核函数及其性质,对P_*(k)阵线性互补问题提出了一种新的宽邻域不可行内点算法.对核函数作了一些适当的改进,所以是不同于Peng等人介绍的自正则障碍函数.最后证明了算法具有近似O((1+2k)n3/4log(nμ~0)/ε)多项式复杂性,是优于传统的基于对数障碍函数求解宽邻域内点算法的复杂性.

关 键 词:互补问题  内点算法  多项式复杂性  核函数  宽邻域

A New Class of Polynomial Interior-Point Algorithm for P*(κ) Linear Complementarity Problems
GONG Xiao-yu,HU Zhen-peng,WANG Xian-jia,ZHANG Ming-wang.A New Class of Polynomial Interior-Point Algorithm for P*(κ) Linear Complementarity Problems[J].Mathematics in Practice and Theory,2011,41(3).
Authors:GONG Xiao-yu  HU Zhen-peng  WANG Xian-jia  ZHANG Ming-wang
Institution:GONG Xiao-yu~(1,2),HU Zhen-peng~1,WANG Xian-jia~3,ZHANG Ming-wang~4 (1.School of Water Resources and Hydropower,Huhan University,Wuhan 430072,China) (2.College of Science,Guangdong University of Petrochemical Technology,Maoming 525000,China) (3.School of Political Science and Public Management,Wuhan University,China) (4.College of Science,Three Gorges University,Yichang 443002,China)
Abstract:In this paper,we propose a new large-update interior-point algorithm for P_*(κ) linear complementarity problems based on kernel functions.We improve some mild conditions on the kernel functions and give a new class of kernel functions.so it is different from the self-regular functions introduced by Peng.Finally,we show that the complexity of the algorithm has so far worst case O((1+ 2κ)n~(3/4)log nμ~0/ε),which is better than the classical large-update algorithm based on the classical logarithmic barrier functions.
Keywords:complementarity problem  interior-point algorithm  polynomial-time complexity  kernel function  large-update  
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号