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 t...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.展开更多
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 direc...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 direction.When 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 algorithms.When 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 SCP.To 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.展开更多
In this paper,we present an infeasible-interior-point algorithm,based on a new wide neighborhood for symmetric cone programming.We treat the classical Newton direction as the sum of two other directions,and equip them...In this paper,we present an infeasible-interior-point algorithm,based on a new wide neighborhood for symmetric cone programming.We treat the classical Newton direction as the sum of two other directions,and equip them with different step sizes.We prove the complexity bound of the new algorithm for the Nesterov-Todd(NT)direction,and the xs and sx directions.The complexity bounds obtained here are the same as small neighborhood infeasible-interior-point algorithms over symmetric cones.展开更多
The Douglas–Peaceman–Rachford–Varga operator splitting methods are a class ofefficient methods for finding a zero of the sum of two maximal monotone operatorsin a real Hilbert space;however, they are sometimes diff...The Douglas–Peaceman–Rachford–Varga operator splitting methods are a class ofefficient methods for finding a zero of the sum of two maximal monotone operatorsin a real Hilbert space;however, they are sometimes difficult or even impossible tosolve the subproblems exactly. In this paper, we suggest an inexact version in whichsome relative error criterion is discussed. The corresponding convergence propertiesare established, and some preliminary numerical experiments are reported to illustrateits efficiency.展开更多
基金Supported by the National Natural Science Foundation of China(No.11471102)the Key Basic Research Foundation of the Higher Education Institutions of Henan Province(No.16A110012)
文摘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.
基金the National Natural Science Foundation of China(No.11471102)the Key Basic Research Foundation of the Higher Education Institutions of Henan Province(No.16A110012)。
文摘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 direction.When 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 algorithms.When 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 SCP.To 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.
基金the National Natural Science Foundation of China(Nos.11471102,11426091,and 61179040)the Natural Science Foundation of Henan University of Science and Technology(No.2014QN039)Key Basic Research Foundation of the Higher Education Institutions of Henan Province(No.16A110012).
文摘In this paper,we present an infeasible-interior-point algorithm,based on a new wide neighborhood for symmetric cone programming.We treat the classical Newton direction as the sum of two other directions,and equip them with different step sizes.We prove the complexity bound of the new algorithm for the Nesterov-Todd(NT)direction,and the xs and sx directions.The complexity bounds obtained here are the same as small neighborhood infeasible-interior-point algorithms over symmetric cones.
基金This work was partially supported by the National Natural Science Foundations of China(Nos.11471102 and 11701150)the Key Basic Research Foundation of the Higher Education Institutions of Henan Province(No.16A110012).
文摘The Douglas–Peaceman–Rachford–Varga operator splitting methods are a class ofefficient methods for finding a zero of the sum of two maximal monotone operatorsin a real Hilbert space;however, they are sometimes difficult or even impossible tosolve the subproblems exactly. In this paper, we suggest an inexact version in whichsome relative error criterion is discussed. The corresponding convergence propertiesare established, and some preliminary numerical experiments are reported to illustrateits efficiency.
