×

A full-Newton step infeasible interior-point algorithm for linear programming based on a kernel function. (English) Zbl 1206.90084

Summary: This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of C. Roos [SIAM J. Optim. 16, No. 4, 1110–1136 (2006; Zbl 1131.90029)]. The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce a feasibility step. For a parameter \(p \in [0,1]\), a polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, \(O(n \log n/\varepsilon )\).

MSC:

90C05 Linear programming
90C51 Interior-point methods

Citations:

Zbl 1131.90029
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amini, K., Peyghami, M.R.: An interior point method for linear programming based on a class of kernel functions. Southeast Asian Bull. Math. 17(1), 139–153 (2005) · Zbl 1070.90131
[2] Bai, Y., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15(1), 101–128 (2004) · Zbl 1077.90038 · doi:10.1137/S1052623403423114
[3] Liu, Z., Sun, W.: An infeasible interior-point algorithm with full-Newton step for linear optimization. Numer. Algorithms 46(2), 173–188 (2007) · Zbl 1133.65033 · doi:10.1007/s11075-007-9135-x
[4] Liu, Z., Sun, W.: A full-Newton step infeasible interior-point algorithm for linear programming based on a special self-regular proximity. Working paper
[5] Mansouri, H., Roos, C.: Simplified O(nL) infeasible interior-point algorithm for linear optimization using full-Newton step. Optim. Methods Softw. 22(3), 519–530 (2007) · Zbl 1186.90077 · doi:10.1080/10556780600816692
[6] Mizuno, S.: Polynomiality of infeasible-interior-point algorithms for linear programming. Math. Program. 67(1), 109–119 (1994) · Zbl 0828.90086 · doi:10.1007/BF01582216
[7] Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93(1), 129–171 (2002) · Zbl 1007.90037 · doi:10.1007/s101070200296
[8] Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. An Interior Approach. Wiley, Chichester (1997) · Zbl 0954.65041
[9] Roos, C.: A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110–1136 (2006) · Zbl 1131.90029 · doi:10.1137/050623917
[10] Salahi, M., Peyghami, M.R., Terlaky, T.: New complexity analysis of IIPMs for linear optimization based on a specific self-regular function. Eur. J. Oper. Res. 186(2), 466–485 (2008) · Zbl 1175.90291 · doi:10.1016/j.ejor.2007.02.008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.