Parametric programming

The branch of mathematical programming concerned with the investigation of optimization problems in which the conditions of feasibility and (or) the objective function depend on one or several deterministic parameters. (Problems in which these parameters are random form the object of stochastic programming.)

In its general form a parametric programming problem consists of maximizing an objective function $ f( x, \lambda ) $ over all $ x = ( x _ {1} \dots x _ {n} ) \in \mathbf R ^ {n} $ subject to constraints

$$ \tag{1 } g _ {i} ( x, \lambda ) \leq b _ {i} ( \lambda ),\ \ i = 1 \dots m, $$

where $ \lambda $ is the vector of parameters, belonging to a given parameter set $ \Lambda \subset \mathbf R ^ {p} $. For any fixed $ \lambda $ this is an ordinary mathematical programming problem. Let $ \Lambda ^ \prime \subset \Lambda $ be the set of those values $ \lambda $ for which this problem is solvable (the solvability set). An optimal solution $ x ^ \star = x _ \lambda ^ \star $ is a function of $ \lambda $ in a natural way. By the solution of a parametric programming problem one means the family $ \{ x _ \lambda ^ \star \} $ for all $ \lambda \in \Lambda ^ \prime $.

The sources of parametric programming problems are fairly diverse. First of all, there is the tendency to reflect a certain arbitrariness with which all or some initial data of a practical optimization problem frequently happen to be defined, or to comprise in a single formulation several versions of a problem (or a whole family of problems depending, for example, on time). Parametric programming is the most adequate way of stating the important problem of stability of solutions of an optimization problem under variations of the initial data. Finally, closely connected with parametric programming problems is the problem of finding the set of Pareto optima in problems of multi-criterion optimization.

If for any fixed $ \lambda $ a parametric programming problem is a linear programming (convex programming, etc.) problem, then one speaks of a linear (or convex, etc.) parametric programming problem.

In general form the analysis of parametric programming problems has the following aims. 1) To find and clarify properties of the solvability sets $ \Lambda ^ \prime $. 2) To find the domains of stability of solutions and to characterize their structure; also, to analyze the behaviour of unstable problems. 3) To characterize the dependence of an optimal value of the objective function on the vector of parameters.

In full generality (that is, for arbitrary objective functions, constraints and domains $ \Lambda $ of variation of the parameters) these problems are very difficult. Fairly well advanced in theoretical and computational respect are only certain classes of problems. This concerns mainly linear parametric programming problems in which either: a) the target function depends linearly on a single scalar parameter $ ( \Lambda = \mathbf R ^ {1} ) $; or b) the right-hand sides of the constraints depend linearly on one parameter; or c) the objective function and right-hand sides of the constraints depend linearly on two independent scalar parameters or on a single parameter; or d) the objective function depends linearly on a vector parameter; or e) the right-hand sides of the constraints depend linearly on a vector parameter. The case when the matrix of constraints of a linear programming problem depends on parameters is very complicated and has so far (1990) not yet been sufficiently well investigated. In the case a), for example, the solutions of the problems 1)–3) above can be characterized as follows. It is required to maximize

$$ \tag{2 } \sum_{j=1}^ { n } ( c _ {j} + \lambda c _ {j} ^ \prime ) x _ {j} $$

under the constraints

$$ \tag{3 } \sum_{j=1}^n a _ {ij} x _ {j} \leq b _ {i} ,\ \ i = 1 \dots m; \ \ x _ {j} \geq 0,\ \ j = 1 \dots n, $$

where $ \lambda \in \Lambda = \mathbf R ^ {1} $. Then there is a partition of $ \Lambda $ into finitely many left-open intervals: $ \Lambda = \cup_{k=1}^ {q} \Lambda ^ {k} $( where $ \Lambda ^ {1} $ is unbounded to the left, $ \Lambda ^ {q} $ is unbounded to the right, and one of them can coincide with $ \Lambda $) such that for all $ \lambda \in \Lambda ^ {k} $ the corresponding linear programming problem is solvable and such that on every interval $ \Lambda ^ {k} $, $ k = 1 \dots q $, it has one and the same basis. The only exceptions can be $ \Lambda ^ {1} $ and $ \Lambda ^ {q} $, on which the objective function (2) may be unbounded. Thus, in a given problem the solvability set $ \Lambda ^ \prime $ is the union of all the $ \Lambda ^ {k} $ with the possible exception of $ \Lambda ^ {1} $ and (or) $ \Lambda ^ {q} $. Next, the optimal value of the objective function on each $ \Lambda ^ {k} $, $ k = 1 \dots q $, is a convex piecewise-linear function of $ \lambda $.

Numerical methods for solving one-parameter problems in linear parametric programming $ ( \Lambda = \mathbf R ^ {1} ) $ are modifications of the simplex method; in the case of a multi-dimensional parameter space one has to use more involved arguments. In recent years, many important results have been obtained in non-linear (especially quadratic and convex) parametric programming.

References

[1]	B. Bank, J. Guddat, D. Klatte, B. Kummer, K. Tammer, "Nonlinear parametric optimization" , Birkhäuser (1983)
[2]	F. Nožička, J. Guddat, H. Hollatz, "Theorie der linearen parametrischen Optimierung" , Akademie Verlag (1974)

Comments

Closely related to parametric programming and the stability analysis of programming problems is sensitivity analysis, i.e. the study of the sensitivity of solutions to changes in the parameters defining the programming problem.

References

[a1]	W. Dinkelbach, "Sensitivätsanalysen und parametrische Programmierung" , Springer (1969)
[a2]	S. Zionts, "Linear and integer programming" , Prentice-Hall (1974)
[a3]	A.M. Geoffrion, "Strictly concave parametric programming I, II" Management Science , 13 (1966/67) pp. 244–253; 359–370