A computational study of the homogeneous algorithm for large-scale convex optimization.

Erling D. Andersen and Yinyu Ye.

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) \cite{ANDERSEN:95:A}. The algorithm is a single phase interior-point type method, it nevertheless either yields an approximate optimal solution or detects possible infeasibility of the problem. In this paper we specialize the algorithm to solution of general smooth convex optimization problems that also possess nonlinear equality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.


Publications from Department of Management no. 3/1996, Odense University, Denmark.