Interior-point algorithm for linear optimization based on a new kernel function |
| |
Authors: | Donghai Chen Mingwang Zhang Weihua Li |
| |
Affiliation: | CHEN Donghai, ZHANG Mingwang, LI Weihua College of Science, China Three Gorges University, Yichang 443002, Hubei, China |
| |
Abstract: | 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/ɛ)) and O(?n log(n/e))O(sqrt n log (n/varepsilon )). 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 primal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions. |
| |
Keywords: | linear optimization interior-point algorithms primal-dual methods kernel function polynomial complexity |
本文献已被 CNKI SpringerLink 等数据库收录! |
|