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

  • Achache Mohamed Mathematics
DOI: https://doi.org/10.19139/soic.v2i1.21

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
Issue
Vol 2 No 1 (2014)
Section
Research Articles
Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).