A weighted full-Newton step primal-dual interior point algorithm for convex quadratic optimization

  • Achache Mohamed Mathematics

Abstract

In this paper a new weighted short-step primal-dual interior point algorithm to solve convex quadratic optimization (CQO) problems. The algorithm uses at each interior iteration afull-Newton step and the strategy of the central to obtain an epsilon-optimal solution of CQO. The algorithm yields the best currently best known theoretical complexity bound namely O(\sqrt(n) log n/epsilon).

References

M. Achache and R. Khebchache: A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP. Afrika Matematika. Online (2013).

M. Achache: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math., 25:(2006), pp.97-110.

M. Achache: A weighted path-following method for the linear complementarity problem. Universitatis Babes.Bolyai.Series Informatica (49) (1): (2004), pp.61-73.

Zs. Darvay: A weighted-path-following method for linear optimization. Studia Univ. Babes-Bolyai, Informatica. Vol XLVII. N◦2. (2002).

J. Ding and T.Y. Li: An algorithm based on weighted logarithmic barrier functions for linear complementarity problems. Arabian Journal for Science and Engineering,15 (4): (1990), pp.679-685.

B. Jansen, C. Roos, T. Terlaky and J.Ph. Vial: Primal-dual target-following algorithms for linear programming. Report 93-107. Delft University of Technology. (1993)

C. Roos, T. Terlaky, and J.Ph. Vial: Theory and algorithms for linear optimization. An interior point approach. John-Wiley and Sons, Chichester, UK. (1997).

G.Q. Wang, Y. J. Yue, and X.Z. Cai: A weighted path-following method for monotone horizontal linear complementarity problem. Fuzzy information and engineering. 54 (2009), pp.479-487.

S.J. Wright: Primal-dual interior point methods. Copyright by SIAM. (1997).

Published
2014-02-22
How to Cite
Mohamed, A. (2014). A weighted full-Newton step primal-dual interior point algorithm for convex quadratic optimization. Statistics, Optimization & Information Computing, 2(1), 21-32. https://doi.org/10.19139/soic.v2i1.21
Section
Research Articles