AN INFEASIBLE INTERIOR-POINT ALGORITHM FOR SOLVING PRIMAL AND DUAL GEOMETRIC PROGRAMS

In this paper an algorithm is presented for solving the classical posy nomial geometric programming dual pair of problems simultaneously. The approach is by means of a primal-dual infeasible algorithm developed simultaneously for (i) the dual geometric program after logarithmic tr ansformation of its objective function, and (ii) its Lagrangian dual p rogram, Under rather general assumptions, the mechanism defines a prim al-dual infeasible path from a specially constructed, perturbed Karush -Kuhn-Tucker system. Subfeasible solutions, as described by Duffin in 1956, are generated for each program whose primal and dual objective f unction values converge to the respective primal and dual program valu es, The basic technique is one of a predictor-corrector type involving Newton's method applied to the perturbed KKT system, coupled with eff ective techniques for choosing iterate directions and step lengths, We also discuss implementation issues and some sparse matrix factorizati ons that take advantage of the very special structure of the Hessian m atrix of the logarithmically transformed dual objective function. Our computational results on 19 of the most challenging GP problems found in the literature are encouraging. The performance indicates that the algorithm is effective regardless of the degree of difficulty, which i s a generally accepted measure in geometric programming.