本文对P*(k)线性互补问题设计了一种基于核函数的全-Newton步不可行内点算法,是对Mansouri等人提出的单调线性互补问题全-Newton步不可行内点算法的改进与推广.算法的主迭代由一个可行步和几个中心步构成且可行步采用小步校正.通过建立和应用一些新的技术性结果, 证明了算法的多项式复杂性为O((1+2k)3/2 (log2 log2 64(1+2k))n log max{(x0)T s0, ‖r0‖}/ε),当k=0时,与当前单调线性互补问题的不可行内点算法最好的迭代复杂性界一致.最后, 用 Matlab 数值实验验证了算法的可行性.
Abstract
In this paper a full-Newton step infeasible interior-point algorithm for P*k linear complementarity problems based on a kernel function is presented, the proposed algorithm is an extension of the infeasible interior-point method for monotone linear complementarity introduced by Mansouri.The main iteration of the algorithm consists of a feasibility step with small-update and several centrality steps.By establishing and using some new technical results, the polynomial complexity bound for the algorithm is obtained, namely, O((1+2k)3/2 (log2 log2 64(1+2k))n log max{(x0)T s0, ‖r0‖}/ε), which coincides with the currently best iteration bound for infeasible interior-point methods of monotone linear complementarity problems when k = 0.Finally, some preliminarily numerical results are presented to verify the feasibility of the proposed algorithm.
关键词
线性互补问题 /
不可行内点算法 /
全-Newton步 /
多项式复杂性 /
核函数
{{custom_keyword}} /
Key words
linear complementarity problem /
infeasible interior-point algorithms /
full- Newton step /
polynomial complexity /
kernel function
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Amini K., Peyghami M.R., An interior point method for linear programming based on a class of kernel functions, Southeast Asian Bull.Math., 2005, 17(1): 139-153.
[2] Bai Y.Q., Ghami M.E., Roos C., A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM J.Optim., 2004, 15(1): 101-128.
[3] Cho G.M., A new large-update interior point algorithm for P*(k) linear complementarity problems, J. Comput.Appl.Math., 2008, 216(1): 265-278.
[4] Kojima M., Megiddo N., Noma T., et al., A Unified Approach to Interior-point Algorithms for Linear Complementarity Problems, In: Lecture Notes in Computer Science, Springer, Berlin, 1991, 538: 7-17.
[5] Liu Z.Y., Sun W.Y., An infeasible interior-point algorithm with full-Newton step for linear optimization, Numer.Algorithms, 2007, 46(2): 173-188.
[6] Liu Z.Y., Sun W.Y., A full-Newton step infeasible interior-point algorithm for linear programming based on a kernel function, Appl.Math.& Optim., 2009, 60(2): 237-251.
[7] Mansouri H., Roos C., Simplified O(nL) infeasible interior-point algorithm for linear optimization using full-Newton step, Optim.Methods Softw., 2007, 22(3): 519-530.
[8] Mansouri H., Zangiabadi M., Pirhaji M., A full-Newton step O(n) infeasible-interior-point algorithm for linear complementarity problems, Nonlinear Anal.Real., 2011, 12(1): 545-561.
[9] Potra F.A., An O(nL) infeasible interior-point algorithm for LCP with quadratic convergence, Ann.Oper. Res., 1996, 62: 81-102.
[10] Peng J.M., Roos C., Terlaky T., Self-regular functions and new search directions for linear and semi-definite optimization, Math.Program., 2002, 93(1): 129-171.
[11] Roos C., Terlaky T., Vial J.P., Theory and Algorithms for Linear Optimization, An Interior Approach, John Wiley & Sons, Chichester, 1997.
[12] Roos C., A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM J.Optim., 2006, 16(4): 1110-1136.
[13] Salahi M., Peyghami M.R., Terlaky T., New complexity analysis of IIPMs for linear optimization based on a specific self-regular function, Eur.J.Oper.Res., 2008, 186(2): 466-485.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
湖北省自然科学基金资助项目(2008CDZ047)
{{custom_fund}}