Abstract
We present a full-Newton step primal-dual infeasible interior-point algorithm based on Darvay’s search directions. These directions are obtained by an equivalent algebraic transformation of the centering equation. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. The starting point in the first iteration of the algorithm depends on a positive number ξ and it is strictly feasible for a perturbed pair, and feasibility steps find strictly feasible iterate for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterate close to the central path of the new perturbed pair. The algorithm finds an ϵ-optimal solution or detects infeasibility of the given problem. The iteration bound coincides with the best known iteration bound for linear optimization problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Achache, M.: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25(1), 97–110 (2006)
Bai, Y.Q., 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)
Bai, Y.Q., Wang, F.Y., Lui, X.W.: A polynomial-time interior-point algorithm for convex quadratic semidefinite optimization. RAIRO-Oper. Res. 44, 251–265 (2010)
Darvay, Z.: New interior point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003)
Gu, G., Mansouri, H., Zangiabadi, M., Bai, Y.Q., Roos, C.: Improved full-Newton step O(nL) infeasible interior-point method for linear optimization. J. Optim. Theory Appl. 145(2), 271–288 (2010)
Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 375–395 (1984)
Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior-point algorithm for linear programming. Math. Program. Ser. A 61(3), 263–280 (1993)
Lustig, I.J.: Feasible issues in a primal-dual interior-point method. Math. Program. 67, 145–162 (1990/1991)
Mansouri, H., Pirhaji, M.: A polynomial interior-point algorithm for monotone linear complementarity problems. J. Optim. Theory Appl. (2012). doi:10.1007/s10957-012-0195-2
Mizuno, S.: Polynomiality of infeasible-interior-point algorithms for linear programming. Math. Program. Ser. A 67(1), 109–119 (1994)
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)
Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton, NJ (2002)
Peng, J., Roos, C., Terlaky, T.: Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities. SIAM J. Optim. 13(1), 179–203 (2002)
Roos, C.: A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110–1136 (2006)
Roos, C., Terlaky, T., Vial, J.-P.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley & Sons, Chichester, UK (1997)
Wang, G.Q., Bai, Y.Q.: A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl. 353, 339–349 (2009)
Wang, G.Q., Bai, Y.Q.: A primal-dual path-following interior-point algorithm for second-order cone optimization with full Nesterov–Todd step. Appl. Math. Comput. 215(3), 1047–1061 (2009)
Wang, G.Q., Bai, Y.Q.: A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 154(3), 966–985 (2012)
Wright, S.J.: Primal-Dual Intrior-Point Methods. SIAM, Philadelphia, USA (1997)
Ye, Y.: Interior Point Algorithms, Theory and Analysis. John Wiley and Sons, Chichester, UK (1997)
Zhang, Y.: On the convergence of a class of infeasible interior point methods for the horizontal linear complementary problem. SIAM J. Optim. 4, 208–227 (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ahmadi, K., Hasani, F. & Kheirfam, B. A Full-Newton Step Infeasible Interior-Point Algorithm Based on Darvay Directions for Linear Optimization. J Math Model Algor 13, 191–208 (2014). https://doi.org/10.1007/s10852-013-9227-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-013-9227-7