A superlinearly convergent projection algorithm for solving the convex inequality problem

The Convex Inequality Problem (CIP), i.e., find x ∈ Rⁿ such that Ax = b, g(x) ≤ 0, where A is an p × n matrix, b is an element of R^m and g(.) : Rⁿ → R^m is a convex function, has been solved by projection algorithms possessing a linear rate of convergence. We propose a projection algorithm that exhibits global and superlinear rate of convergence under reasonable assumptions. Convergence is ensured if the CIP is not empty. A direction of search is found by solving a quadratic programming problem (the projection step). As opposed to previous algorithms no special stepsize procedure is necessary to ensure a superlinear rate of convergence. We suggest a possible application of this algorithm for solving convex constrained Linear Complementarity Problems, i.e., find x ∈ Rⁿ such that x ≥ 0, Ax + B ≥ 0, [x, Ax + b] = 0, g(x) ≤ 0. A is an n × n positive semidefinite matrix and g(.) : Rⁿ → R^m is a convex function.