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.

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. ${\displaystyle J^{*}}$ denotes a function whose output is the optimal value of the objective function ${\displaystyle f}$. The set ${\displaystyle \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 ${\displaystyle \theta }$.

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^[3]
• If integer variables are present, then the problem is referred to as (multi)parametric mixed-integer programming problem^[4]
• 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.^[5]

Applications[]

The connection between parametric programming and model predictive control established in 2000 has contributed to an increased interest in the topic.^[6][7] 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 chip^[8]). 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[]