This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O（n log...This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O（n log（n /ε））iterations are required for getting ε-solution of the problem at hand,which coincides with the best-known bound for infeasible interior-point algorithms.展开更多
Many problems in mathematical programming can be modelled as semidefinite programming. The success of interior point algorithms for large-scale linear programming has prompted researchers to develop these algorithms t...Many problems in mathematical programming can be modelled as semidefinite programming. The success of interior point algorithms for large-scale linear programming has prompted researchers to develop these algorithms to the semidefinite programming (SDP) case. In this paper, we extend Roos’s projective method for linear programming to SDP. The method is path-following and based on the useof a multiplicative barrier function. The iteration bound depends on the choice ofthe exponent μ in the numerator of the barrier function. The analysis in this paper resembles the one of the approximate center method for linear programming, as proposed by Rocs and Vial [14].展开更多
基金Supported by the National Natural Science Foundation of China(71071119)
文摘This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O（n log（n /ε））iterations are required for getting ε-solution of the problem at hand,which coincides with the best-known bound for infeasible interior-point algorithms.
文摘Many problems in mathematical programming can be modelled as semidefinite programming. The success of interior point algorithms for large-scale linear programming has prompted researchers to develop these algorithms to the semidefinite programming (SDP) case. In this paper, we extend Roos’s projective method for linear programming to SDP. The method is path-following and based on the useof a multiplicative barrier function. The iteration bound depends on the choice ofthe exponent μ in the numerator of the barrier function. The analysis in this paper resembles the one of the approximate center method for linear programming, as proposed by Rocs and Vial [14].
