Piecewise-Linear Pathways to the Optimal Solution Set in Linear Programming

Author：

ISSN： 0022-3239

Source： Journal of Optimization Theory and Applications, Vol.93, Iss.3, 1997-06, pp. : 619-634

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

This paper takes a fresh look at the application of quadratic penalty functions to linear programming. Recently, Madsen et al. (Ref. 1) described a continuation algorithm for linear programming based on smoothing a dual l₁-formulation of a linear program with unit bounds. The present paper is prompted by the observation that this is equivalent to applying a quadratic penalty function to the dual of a linear program in standard canonical form, in the sense that both approaches generate continuous, piecewise-linear paths leading to the optimal solution set. These paths lead to new characterizations of optimal solutions in linear programming. An important product of this analysis is a finite penalty algorithm for linear programming closely related to the least-norm algorithm of Mangasarian (Ref. 2) and to the continuation algorithm of Madsen et al. (Ref. 1). The algorithm is implemented, and promising numerical results are given.