Parametric Programming

Parametric programming is a type of mathematical optimization, where the optimization problem is solved as a function of one or multiple parameters. Developed in parallel to sensitivity analysis, its earliest mention can be found in a thesis from 1952. Since then, there have been considerable developments for the cases of multiple parameters, presence of integer variables as well as nonlinearities.

Notation

In general, the following optimization problem is considered

: $\begin J^*(\theta) = & \min_ f(x,\theta) \\ & \text g(x,\theta)\leq 0.\\ & \theta \in \Theta \subset \mathbb R^m \end$

where $x$ is the optimization variable, $\theta$ are the parameters, $f(x,\theta)$ is the objective function and $g(x,\theta)$ denote the constraints. $J^*$ denotes a function whose output is the optimal value of the objective function $f$. The set $\Theta$ is generally referred to as parameter space.

The optimal value (i.e. result of solving the optimization problem) is obtained by evaluating the function with an argument $\theta$.

Classification

Depending on the nature of $f(x,\theta)$ and $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. $m > 1$, then it is often referred to as multiparametric programming problem
* If integer variables are present, then the problem is referred to as (multi)parametric mixed-integer programming problem
* 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.

Applications

The connection between parametric programming and model predictive control established in 2000 has contributed to an increased interest in the topic. Parametric programming supplies the idea that optimization problems can be parametrized as functions that can be evaluated (similar to a lookup table). This in turns allows the optimization algorithms in optimal controllers to be implemented as pre-computed (off-line) mathematical functions, which may in some cases be simpler and faster to evaluate than solving a full optimization problem on-line. This also opens up the possibility of creating optimal controllers on chips (MPC on chipMPC on a chip—Recent advances on the application of multi-parametric model-based control , Request PDF
/ref>). However, the off-line parametrization of optimal solutions runs into the curse of dimensionality as the number of possible solutions grows with the dimensionality and number of constraints in the problem.

References

{{reflist

Optimization algorithms and methods