单调线性互补问题基于核函数的满-Newton步不可行内点算法

J4 ›› 2012, Vol. 47 ›› Issue (10): 81-88.

单调线性互补问题基于核函数的满-Newton步不可行内点算法

陈月姣,张明望*

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

收稿日期:2011-08-21 出版日期:2012-11-20 发布日期:2012-10-26
通讯作者: 张明望(1959- ),男,教授,主要研究方向为最优化理论及应用. Email:zmwang@ctgu.edu.cn
作者简介:陈月姣(1987- ),女,硕士,主要研究方向为最优化理论及应用. Email:mlchenyuejiao@163.com
基金资助:
湖北省自然科学基金资助项目(2008CDZ047)

A full-newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a kernel function

CHEN Yue-jiao, ZHANG Ming-wang*

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

Received:2011-08-21 Online:2012-11-20 Published:2012-10-26

摘要/Abstract

摘要：

针对单调线性互补问题设计了一种基于核函数的满Newton步不可行内点算法,算法的主迭代由一个可行步和几个中心步构成。通过建立和应用一些新的分析工具,证明了算法的多项式复杂性为Onlogmax｛(x0)Ts0,‖r0‖｝n,这与当前单调线性互补问题的不可行内点算法最好的迭代界一致。

关键词: 单调线性互补问题;不可行内点算法;满-Newton步;核函数;多项式复杂性

Abstract:

A full-newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a kernel function was presented. The main iteration of the algorithm consists of a feasibility step and several centrality steps. By using some new analysis tools, the polynomial complexity bound for the algorithm was obtained, namely, Onlogmax｛(x0)Ts0,‖r0‖｝n, which is consistent with the currently best iteration bound for infeasible interior-point methods of monotone linear complementarity.

Key words: linear complementarity problem; infeasible interior point algorithm; full-newton step; kernel function; polynomial complexity

陈月姣,张明望*. 单调线性互补问题基于核函数的满-Newton步不可行内点算法[J]. J4, 2012, 47(10): 81-88.

CHEN Yue-jiao, ZHANG Ming-wang*. A full-newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a kernel function[J]. J4, 2012, 47(10): 81-88.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed