Strictly Concave Parametric Programming, Part I: Basic Theory

Abstract

This paper, which is presented in two parts, develops a computational approach to strictly concave parametric programs of the form: Maximize α f₁(x) + (1 − α)f₂(x) subject to concave inequality constraints for each fixed value of α in the unit interval, where f₁ and f₂ are strictly concave and certain additional regularity conditions are satisfied. This class of problems subsumes a corresponding class of vector maximum problems and also, by means of a simple device, provides a deformation method for ordinary concave programming. The approach is based on exploiting the continuity properties of the parametric program so as to efficiently maintain a solution to the associated Kuhn-Tucker conditions as a traverses the unit interval. The same approach can be adapted to much more general parametric programs than the one above. In Part I, a Basic Parametric Procedure is derived and shown to be finite in a certain sense. It forms the basis of various parametric programming algorithms, depending on what special assumptions are made on the functions. In Part II, additional theory is developed that facilitates computational implementation, and one possible general-purpose algorithm for a digital computer is given. An illustrative graphical example is presented and several extensions are indicated.