In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barr...In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large-and small-update methods are derived, namely, O（nlog（n/c）） and O（√nlog（n/ε））. This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other pri- mal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions.展开更多
We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite terminat...We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite termination technique, is bounded above by O( n1.5). The random LP problem is Todd’s probabilistic model with the standard Gauss distribution.展开更多
A new deterministic formulation,called the conditional expectation formulation,is proposed for dynamic stochastic programming problems in order to overcome some disadvantages of existing deterministic formulations.We ...A new deterministic formulation,called the conditional expectation formulation,is proposed for dynamic stochastic programming problems in order to overcome some disadvantages of existing deterministic formulations.We then check the impact of the new deterministic formulation and other two deterministic formulations on the corresponding problem size,nonzero elements and solution time by solving some typical dynamic stochastic programming problems with different interior point algorithms.Numerical results show the advantage and application of the new deterministic formulation.展开更多
基金Supported by the Natural Science Foundation of Hubei Province (2008CDZD47)
文摘In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large-and small-update methods are derived, namely, O（nlog（n/c）） and O（√nlog（n/ε））. This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other pri- mal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions.
文摘We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite termination technique, is bounded above by O( n1.5). The random LP problem is Todd’s probabilistic model with the standard Gauss distribution.
基金This research was partially supported by the Natural Science Research Foundation of Shaanxi Province(2001SL09)
文摘A new deterministic formulation,called the conditional expectation formulation,is proposed for dynamic stochastic programming problems in order to overcome some disadvantages of existing deterministic formulations.We then check the impact of the new deterministic formulation and other two deterministic formulations on the corresponding problem size,nonzero elements and solution time by solving some typical dynamic stochastic programming problems with different interior point algorithms.Numerical results show the advantage and application of the new deterministic formulation.
