A PATH-FOLLOWING ALGORITHM FOR LINEAR-PROGRAMMING USING QUADRATIC ANDLOGARITHMIC PENALTY-FUNCTIONS

Motivated by a recent work of Setiono, a path-following algorithm for linear programming using both logarithmic and quadratic penalty functi ons is proposed. In the algorithm, a logarithmic and a quadratic penal ty is placed on, respectively, the nonnegativity constraints and an ar bitrary subset of the equality constraints; Newton's method is applied to solve the penalized problem, and after each Newton step the penalt y parameters are decreased. This algorithm maintains neither primal no r dual feasibility and does not require a Phase I. It is shown that if the initial iterate is chosen appropriately and the penalty parameter s are decreased to zero in a particular way, then the algorithm is lin early convergent. Numerical results are also presented suggesting that the algorithm may be competitive with interior point algorithms in pr actice, requiring typically between 30-45 iterations to accurately sol ve each Netlib problem tested.