检索结果-南通市图书馆

Chinese Quarterly Journal of Mathematics 2015年第4期30卷 475-494页

作者：刘长河尚有林李振国 School of Mathematics and Statistics Henan University of Science and Technology

We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O（r log ε1） iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small examples.

关键词： linear programming symmetric cone Euclidean Jordan algebra interior-point methods Mehrotra-type algorithm polynomial complexity

A SECOND ORDER MEHROTRA-TYPE PREDICTOR-CORRECTOR ALGORITHM FOR SEMIDEFINITE OPTIMIZATION

在线全文

学校读者我要写书评

暂无评论

Journal of Systems Science & complexity 2012年第6期25卷 1108-1121页

作者： Mingwang ZHANG College of Science China Three Gorges University

Abstract Mehrotra-type predictor-corrector algorithm is one of the most effective primal-dual interior- point methods. This paper presents an extension of the recent variant of second order Mehrotra-type predictor-corrector algorithm that was proposed by Salahi, et a1.（2006） for linear optimization. Basedon the NT direction as Newton search direction, it is shown that the iteration-complexity bound of thealgorithm for semidefinite optimization is which is similar to that of the correspondingalgorithm for linear optimization.

关键词： Mehrotra-Type algorithm polynomial complexity predictor-corrector algorithm semidef-inite optimization.

A New Infeasible-Interior-Point Algorithm for Linear Programming over Symmetric Cones

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2017年第3期33卷 771-788页

作者： Chang-he LIU You-lin SHANG Ping HAN School of Mathematics and Statistics Henan University of Science and Technology College of Mathematics and System Science Shandong University of Science and Technology

In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N（ t1, t2, η）, for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O（r1.5 log ε-1） for the Nesterov-Todd （NT） direction, and O（r2 log ε-1） for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε 〉 0 is the required precision. If starting with a feasible point （x0, y0, s0） in N（t1, t2, η）, the complexity bound is O（ √ r log ε-1） for the NT direction, and O（r log ε-1） for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.

关键词： symmetric cone Euclidean Jordan algebra interior-point methods linear programming polynomial complexity

A Kernel Function Based Interior-Point Methods for Solving P_*(κ)-Linear Complementarity Problem

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2010年第9期26卷 1761-1778页

作者： M.Reza PEYGHAMI Keyvan AMINI Department of Mathematics K. N. Toosi University. of Technology School of Mathematics Institute for Research in Fundamental Sciences (IPM) Department of Mathematics Faculty of Sciences Razi University

In this paper, motivated by the complexity results of Interior Point Methods （IPMs） for Linear Optimization （LO） based on kernel functions, we present a polynomial time IPM for solving P.（a）-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.

关键词： Linear complementarity problem interior-point methods large and small update methods polynomial complexity

An Adaptive Infeasible Interior-Point Algorithm for Linear Complementarity Problems

在线全文

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2013年第4期1卷 523-536页

作者： Hossein Mansouri Mohammad Pirhaji Department of Applied Mathematics Faculty of Mathematical SciencesShahrekord UniversityP.O.Box 115ShahrekordIran

Interior-Point Methods(IPMs)not only are the most effective methods in practice but also have polynomial-time *** researchers have proposed IPMs for Linear Optimization(LO)and achieved plentiful *** many cases these methods were extendable for LO to Linear Complementarity Problems(LCPs)*** this paper,motivated by the complexity results for linear optimization based on the study of *** et al.(Mansouri and Zangiabadi in ***.62(2):285–297,2013),we extend their idea for LO to *** proposed algorithm requires two types of full-Newton steps are called,feasibility steps and(ordinary)centering steps,*** each iteration both feasibility and optimality are reduced exactly at the same *** each iteration of the algorithm we use the largest possible barrier parameter valueθwhich lies between the two values 117n and 113n,this makes the algorithm faster convergent for problems having a strictly complementarity solution.

关键词： Linear complementarity problem Infeasible-interior-point-method Central path polynomial complexity

A Class of New Large-Update Primal-Dual Interior-Point Algorithms for P＊（k） Nonlinear Complementarity Problems

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2011年第10期27卷 1979-1994页

作者： Hua Ping CHEN Ming Wang ZHANG College of Science China Three Gorges University Yichang 443002 P. R. China

In this paper we propose a class of new large-update primal-dual interior-point algorithms for P.（k） nonlinear complementarity problem （NCP）, which are based on a class of kernel functions investigated by Bai et al. in their recent work for linear optimization （LO）. The arguments for the algorithms are followed as Peng et al.＇s for P.（n） complementarity problem based on the self-regular functions [Peng, J., Roos, C., Terlaky, T.： Self-Regularity： A New Paradigm for Primal-Dual Interior- Point Algorithms, Princeton University Press, Princeton, 2002]. It is worth mentioning that since this class of kernel functions includes a class of non-self-regular functions as special case, so our algorithms are different from Peng et al.＇s and the corresponding analysis is simpler than theirs. The ultimate goal of the paper is to show that the algorithms based on these functions have favorable polynomial complexity.

关键词： Large-update method interior-point algorithm nonlinear complementarity problem non- self-regular function polynomial complexity

A CORRECTOR-PREDICTOR ARC SEARCH INTERIOR-POINT ALGORITHM FOR SYMMETRIC OPTIMIZATION

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Acta Mathematica Scientia 2018年第4期38卷 1269-1284页

作者： M.PIRHAJI M.ZANGIABADI H.MANSOURI Department of Applied Mathematics Faculty of Mathematical Sciences Shahrekord University

In this paper, a corrector-predictor interior-point algorithm is proposed for sym- metric optimization. The algorithm approximates the central path by an ellipse, follows the ellipsoidal approximation of the central-path step by step and generates a sequence of iter- ates in a wide neighborhood of the central-path. Using the machinery of Euclidean Jordan algebra and the commutative class of search directions, the convergence analysis of the algo- rithm is shown and it is proved that the algorithm has the complexity bound O （√τL） for the well-known Nesterov-Todd search direction and O （τL） for the xs and sx search directions.

关键词： symmetric optimization ellipsoidal approximation wide neighborhood interior-point methods polynomial complexity

An O(rL)Infeasible Interior-point Algorithm for Symmetric Cone LCP via CHKS Function

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2009年第4期25卷 593-606页

作者： Zi-yan Luo Nai-hua Xiu Department of Mathematics School of Science Beijing Jiaotong University Beijing 100044 China Department of Mathematics School of Science Beijing Jiaotong University Key Laboratory of Communication and Information System (Beijing Jiaotong University) Beijing Municipal Commission of Education Beijing 100044 China

In this paper, we propose a theoretical framework of an infeasible interior-point algorithm for solving monotone linear cornplementarity problems over symmetric cones （SCLCP）. The new algorithm gets Newton-like directions from the Chen-Harker-Kanzow-Smale （CHKS） smoothing equation of the SCLCP. It possesses the following features： The starting point is easily chosen; one approximate Newton step is computed and accepted at each iteration; the iterative point with unit stepsize automatically remains in the neighborhood of central path; the iterative sequence is bounded and possesses （9（rL） polynomial-time complexity under the monotonicity and solvability of the SCLCP.

关键词： Infeasible interior-point algorithm symmetric cone linear complementarity problem monotonicity polynomial complexity

polynomial-time verification of diagnosability of fuzzy discrete event systems

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2014年第6期57卷 274-283页

作者： LIU FuChun School of Computers Guangdong University of Technology

A fuzzy approach to perform diagnosis of fuzzy discrete event systems(FDESs)is proposed by constructing diagnosers,which may more effectively cope with the problems of vagueness and fuzziness arising from failure diagnosis of fuzzy ***,the complexity of constructing this kind of diagnosers is exponential in the state space and the number of fuzzy events of the *** this paper,we present an algorithm for verifying the diagnosability of FDESs based on the construction of a nondeterministic automaton called F-verifier instead of *** the construction of F-verifiers and the verification of diagnosability of FDESs can be realized with a polynomial-time complexity.

关键词： discrete event systems fuzzy finite automata failure diagnosis polynomial complexity

polynomial Convergence of Primal-Dual Path-Following Algorithms for Symmetric Cone Programming Based on Wide Neighborhoods and a New Class of Directions

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2017年第3期5卷 333-346页

作者： Chang-He Liu Yuan-Yuan Huang You-Lin Shang School of Mathematics and Statistics Henan University of Science and TechnologyLuoyang 471023HenanChina

This paper presents a class of primal-dual path-following interior-point algorithms for symmetric cone programming(SCP)based on wide neighborhoods and new directions with a parameterθ.When the parameterθ=1,the direction is exactly the classical Newton *** the parameterθis independent of the rank of the associated Euclidean Jordan algebra,the algorithm terminates in at most O(κr logε−1)iterations,which coincides with the best known iteration bound for the classical wide neighborhood *** the parameterθ=√n/βτand Nesterov–Todd search direction is used,the algorithm has O(√r logε−1)iteration complexity,the best iteration complexity obtained so far by any interior-point method for solving *** our knowledge,this is the first time that a class of interior-point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed over symmetric cone.

关键词： Path-following interior-point algorithm Wide neighborhood Symmetric cone programming Euclidean Jordan algebra polynomial complexity