Abstract
In this paper, we present a primal-dual interior point algorithm for linearly constrained convex optimization (LCCO). The algorithm uses only full-Newton step to update iterates with an appropriate proximity measure for controlling feasible iterations near the central path during the solution process. The favorable polynomial complexity bound for the algorithm with short-step method is obtained, namely \(O(\sqrt {n}\log \frac {n}{\epsilon })\) which is as good as the linear and convex quadratic optimization analogue. Numerical results are reported to show the efficiency of the algorithm.
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, 97–110 (2006)
Achache, M., Goutali, M.: A primal-dual interior point algorithm for convex quadratic programs. Studia Univ. Babes-Bolyai. Ser. Inform. LVII(1), 48–58 (2012)
Darvay, Z.: New interior-point algorithms in linear programming. J. Adv. Model. optim. 5(1), 51–92 (2003)
Darvay, Z.: A predictor-corrector algorithm for linearly constrained convex optimization. Studia Univ. Babes-Bolyai. Ser. Inform. LIV(2), 121–138 (2009)
Grana Drummond, L.M., Svaiter, B.F.: On well definedness of the central path. J. Optim. Theory Appl. 102(N2), 223–237 (1999)
Peng, J., Roos, C., Terlaky, T.: New complexity analysis of the primal-dual Newton method for linear optimization. Ann. Oper. Res. 49, 23–39 (2000)
Roos, C., Terlaky, T., Vial, J.Ph.: Theory and Algorithms for linear optimization. An interior Point Approach. John-Wiley Sons, Chichester (1997)
Ye, Y.: Interior point algorithms. Theory and Analysis. John-Wiley Sons, Chichester (1997)
Zhang, M, Bai, Y., Wang, G.: A new primal-dual path-following interior-point algorithm for linearly constrained convex optimization. J. Shanghai Univ. 12(6), 475–780 (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Achache, M., Goutali, M. Complexity analysis and numerical implementation of a full-Newton step interior-point algorithm for LCCO. Numer Algor 70, 393–405 (2015). https://doi.org/10.1007/s11075-014-9955-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-014-9955-4
Keywords
- Linearly constrained convex optimization
- Interior point methods
- Short-step primal-dual algorithms
- Complexity of algorithms