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 s...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.展开更多
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-cor...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.展开更多
In Zhang’s recent works,a second-order Mehrotra-type predictor-corrector algorithm for linear optimization was extended to semidefinite optimization and derived that the algorithm for semidefinite optimization had3/2...In Zhang’s recent works,a second-order Mehrotra-type predictor-corrector algorithm for linear optimization was extended to semidefinite optimization and derived that the algorithm for semidefinite optimization had3/2 0 T 0O（nlog（X）gS/e）iteration complexity based on the NT direction as Newton search direction.In this paper,we extend the second-order Mehrotra-type predictor-corrector algorithm for linear optimization to semidefinite optimization and discuss the polynomial convergence of the algorithm by modifying the corrector direction and new iterates.It is proved that the iteration complexity is reduced to0 0O（nlog XgS/e）,which coincides with the currently best iteration bound of Mehrotra-type predictor-corrector algorithm for semidefinite optimization.展开更多
It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_＊（κ） linear complementarity problems.This paper presents an extension of t...It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_＊（κ） linear complementarity problems.This paper presents an extension of the recent variant of Mehrotra＇s second order algorithm for linear optimijation.It is shown that the iteration-complexity bound of the algorithm is O（4κ ＋ 3）√14κ ＋ 5 nlog（x0）Ts0/ε,which is similar to that of the corresponding algorithm for linear optimization.展开更多
基金Supported by the National Natural Science Foundation of China(11471102,61301229)Supported by the Natural Science Foundation of Henan University of Science and Technology(2014QN039)
文摘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.
基金supported by Natural Science Foundation of Hubei Province under Grant No.2008CDZ047
文摘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.
基金Supported by the National Natural Science Foundation of China(71471102)
文摘In Zhang’s recent works,a second-order Mehrotra-type predictor-corrector algorithm for linear optimization was extended to semidefinite optimization and derived that the algorithm for semidefinite optimization had3/2 0 T 0O（nlog（X）gS/e）iteration complexity based on the NT direction as Newton search direction.In this paper,we extend the second-order Mehrotra-type predictor-corrector algorithm for linear optimization to semidefinite optimization and discuss the polynomial convergence of the algorithm by modifying the corrector direction and new iterates.It is proved that the iteration complexity is reduced to0 0O（nlog XgS/e）,which coincides with the currently best iteration bound of Mehrotra-type predictor-corrector algorithm for semidefinite optimization.
基金supported by the Natural Science Foundation of Hubei Province of China(2008CDZ047)
文摘It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_＊（κ） linear complementarity problems.This paper presents an extension of the recent variant of Mehrotra＇s second order algorithm for linear optimijation.It is shown that the iteration-complexity bound of the algorithm is O（4κ ＋ 3）√14κ ＋ 5 nlog（x0）Ts0/ε,which is similar to that of the corresponding algorithm for linear optimization.
