Parametric programming

Parametric programming is a type of mathematical optimization, where the optimization problem is solved as a function of one or multiple parameters.[1] Developed in parallel to sensitivity analysis, its earliest mention can be found in a thesis from 1952.[2] Since then, there have been considerable developments for the cases of multiple parameters, presence of integer variables as well as nonlinearities. In particular the connection between parametric programming and model predictive control established in 2000 has contributed to an increased interest in the topic.[3][4]

Notation

In general, the following optimization problem is considered

${\displaystyle {\begin{aligned}J^{*}(\theta )={}\min _{x\in \mathbb {R} ^{n}}\ &f(x,\theta )\\{\text{subject to}}\ &g(x,\theta )\leq 0.\\\theta \in \Theta \subset \mathbb {R} ^{m}\end{aligned}}}$

where ${\displaystyle x}$ is the optimization variable, ${\displaystyle \theta }$ are the parameters, ${\displaystyle f(x,\theta )}$ is the objective function and ${\displaystyle g(x,\theta )}$ denote the constraints. The set ${\displaystyle \Theta }$ is generally referred to as parameter space.

Classification

Depending on the nature of ${\displaystyle f(x,\theta )}$ and ${\displaystyle g(x,\theta )}$ and whether the optimization problem features integer variables, parametric programming problems are classified into different sub-classes:

• If more than one parameter is present, i.e. ${\displaystyle m>1}$, then it is often referred to as multiparametric programming problem[5]
• If integer variables are present, then the problem is referred to as (multi)parametric mixed-integer programming problem[6]
• If constraints are affine, then additional classifications depending to nature of the objective function in (multi)parametric (mixed-integer) linear, quadratic and nonlinear programming problems is performed. Note that this generally assumes the constraints to be affine.[7]

References

1. Gal, Tomas (1995). Postoptimal Analyses, Parametric Programming, and Related Topics: Degeneracy, Multicriteria Decision Making, Redundancy (2nd ed.). Berlin: W. de Gruyter. ISBN 978-3-11-087120-3.
2. Gal, Tomas; Greenberg, Harvey J. (1997). Advances in Sensitivity Analysis and Parametric Programming. International Series in Operations Research & Management Science. 6. Boston: Kluwer Academic Publishers. doi:10.1007/978-1-4615-6103-3. ISBN 978-0-7923-9917-9.
3. Bemporad, Alberto; Morari, Manfred; Dua, Vivek; Pistikopoulos, Efstratios N. (2000). "The explicit solution of model predictive control via multiparametric quadratic programming". Proceedings of the 2000 American Control Conference. p. 872. doi:10.1109/ACC.2000.876624. ISBN 0-7803-5519-9.
4. Bemporad, Alberto; Morari, Manfred; Dua, Vivek; Pistikopoulos, Efstratios N. (January 2002). "The explicit linear quadratic regulator for constrained systems". Automatica. 38 (1): 3–20. CiteSeerX 10.1.1.67.2946. doi:10.1016/S0005-1098(01)00174-1.
5. Gal, Tomas; Nedoma, Josef (1972). "Multiparametric Linear Programming". Management Science. 18 (7): 406–422. doi:10.1287/mnsc.18.7.406. JSTOR 2629358.
6. Dua, Vivek; Pistikopoulos, Efstratios N. (October 1999). "Algorithms for the Solution of Multiparametric Mixed-Integer Nonlinear Optimization Problems". Industrial & Engineering Chemistry Research. 38 (10): 3976–3987. doi:10.1021/ie980792u.
7. Pistikopoulos, Efstratios N.; Georgiadis, Michael C.; Dua, Vivek (2007). Multi-parametric Programming Theory, Algorithms and Applications. Weinheim: Wiley-VCH. doi:10.1002/9783527631216. ISBN 9783527316915.