Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields ...Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.展开更多
In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functio...In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.展开更多
Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with si...Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.展开更多
基金Supported by National Natural Science Foundation of China (Grant Nos.10771133 and 70871082)Shanghai Leading Academic Discipline Project (Grant No.S30104)
文摘Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.
基金Project supported by Dutch Organization for Scientific Research(Grant No .613 .000 .010)
文摘In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.
基金Project supported by the National Natural Science Foundation of China （Grant No. 10117733）, the Shanghai Leading Academic Discipline Project （Grant No.J50101）, and the Foundation of Scientific Research for Selecting and Cultivating Young Excellent University Teachers in Shanghai （Grant No.06XPYQ52）
文摘Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.
