IJPAM: Volume 77, No. 3 (2012)

SHORT-STEP PRIMAL-DUAL TARGET-FOLLOWING
ALGORITHMS FOR THE CONVEXE
QUADRATIQUE PROBLEMS

H. Roumili
Laboratory LMFN
University of Setif
Setif, 19000, ALGERIA


Abstract. In this paper we propose a method for convex quadratic programming with the property that starting from an initial feasible point, it generates iterates that simultaneously get closer to optimality and closer to centrality. The iterates follow so-called targets, that are updated with Short-steps. Newton's method is used to find an iterate close to a target. We propose an algorithm with the best theoretical polynomial complexity namely O($\sqrt{n}$log( $\frac{n}{\varepsilon }))$, iteration bound. For its numerical performances some strategies are used. Finally, we have tested this algorithm on some convexe quadratique problems.

Received: November 25, 2011

AMS Subject Classification: 65K05, 90C20, 90C51

Key Words and Phrases: interior points methods, convex quadratic programming, short-step method, primal-dual target following algorithm, polynomial complexity

Download paper from here.


Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2012
Volume: 77
Issue: 3