Parametric programming: Difference between revisions

Revision as of 18:37, 8 January 2018

Latest revision as of 08:18, 13 December 2024

(20 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Optimization using parameterization}}

{{orphan|date=February 2015}}

'''Parametric programming''' is a type of [[mathematical optimization]], where the [[optimization problem]] is solved as a function of one or multiple [[parameters]].<ref>{{cite book |last1=Gal |first1=Tomas |year=1995 |title=Postoptimal Analyses, Parametric Programming, and Related Topics: Degeneracy, Multicriteria Decision Making, Redundancy |publisher=W. de Gruyter |___location=Berlin |isbn=978-3-11-087120-3 |edition=2nd ed.}}</ref> Developed in parallel to [[sensitivity analysis]], its earliest mention can be found in a [[thesis]] from 1952.<ref>{{cite book |last1=Gal |first1=Tomas |last2=Greenberg |first2=Harvey J. |date=1997 |title=Advances in Sensitivity Analysis and Parametric Programming |publisher=Kluwer Academic Publishers |___location=Boston |doi=10.1007/978-1-4615-6103-3 |isbn=978-0-7923-9917-9 |series=International Series in Operations Research & Management Science |volume=6}}</ref> 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.<ref>{{cite journal |doi=10.1109/ACC.2000.876624|chapter=The explicit solution of model predictive control via multiparametric quadratic programming|title=Proceedings of the 2000 American Control Conference. ACC (IEEE Cat. No.00CH36334)|pages=872|year=2000|last1=Bemporad|first1=A|last2=Morari|first2=M|last3=Dua|first3=V|last4=Pistikopoulos|first4=E.N|isbn=0-7803-5519-9}}</ref><ref>{{cite journal |last1=Bemporad |first1=Alberto |last2=Morari |first2=Manfred |last3=Dua |first3=Vivek |last4=Pistikopoulos |first4=Efstratios N. |title=The explicit linear quadratic regulator for constrained systems |journal=Automatica |date=January 2002 |volume=38 |issue=1 |pages=3–20 |citeseerx=10.1.1.67.2946 |doi=10.1016/S0005-1098(01)00174-1}}</ref>

'''Parametric programming''' is a type of [[mathematical optimization]], where the [[optimization problem]] is solved as a function of one or multiple [[parameters]].<ref>{{cite book |last1=Gal |first1=Tomas |year=1995 |title=Postoptimal Analyses, Parametric Programming, and Related Topics: Degeneracy, Multicriteria Decision Making, Redundancy |publisher=W. de Gruyter |___location=Berlin |isbn=978-3-11-087120-3 |edition=2nd ed.}}</ref> Developed in parallel to [[sensitivity analysis]], its earliest mention can be found in a [[thesis]] from 1952.<ref>{{cite book |last1=Gal |first1=Tomas |last2=Greenberg |first2=Harvey J. |date=1997 |title=Advances in Sensitivity Analysis and Parametric Programming |publisher=Kluwer Academic Publishers |___location=Boston |isbn=978-0-7923-9917-9}}</ref> 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.<ref>{{cite journal |doi=10.1109/ACC.2000.876624|chapter=The explicit solution of model predictive control via multiparametric quadratic programming|title=Proceedings of the 2000 American Control Conference. ACC (IEEE Cat. No.00CH36334)|pages=872|year=2000|last1=Bemporad|first1=A|last2=Morari|first2=M|last3=Dua|first3=V|last4=Pistikopoulos|first4=E.N|isbn=0-7803-5519-9}}</ref><ref>{{cite journal |last1=Bemporad |first1=Alberto |last2=Morari |first2=Manfred |last3=Dua |first3=Vivek |last4=Pistikopoulos |first4=Efstratios N. |title=The explicit linear quadratic regulator for constrained systems |journal=Automatica |date=January 2002 |volume=38 |issue=1 |pages=3–20 |citeseerx=10.1.1.67.2946 |doi=10.1016/S0005-1098(01)00174-1}}</ref>

== Notation ==

Line 8 ⟶ 7:

: <math>

\begin{align}

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{align}

</math>

where <math>x</math> is the optimization variable, <math>\theta</math> are the parameters, <math>f(x,\theta)</math> is the [[objective function]] and <math>g(x,\theta)</math> denote the [[constraint (mathematics)|constraint]]s. <math>J^*</math> denotes a function whose output is the optimal value of the objective function <math>f</math>. The set <math>\Theta</math> 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 <math>\theta</math>.

== Classification ==

Depending on the nature of <math>f(x,\theta)</math> and <math>g(x,\theta)</math> 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. <math>m > 1</math>, then it is often referred to as multiparametric programming problem<ref>{{cite journal|last1=Gal|first1=Tomas|last2=Nedoma|first2=Josef|title=Multiparametric Linear Programming|journal=Management Science|date=1972|volume=18|issue=7|pages=406–422|jstor=2629358|doi=10.1287/mnsc.18.7.406}}</ref>

* If integer variables are present, then the problem is referred to as (multi)parametric mixed-integer programming problem<ref>{{cite journal|last1=Dua|first1=Vivek|last2=Pistikopoulos|first2=Efstratios N.|title=Algorithms for the Solution of Multiparametric Mixed-Integer Nonlinear Optimization Problems|journal=Industrial & Engineering Chemistry Research|date=October 1999|volume=38|issue=10|pages=3976–3987|doi=10.1021/ie980792u}}</ref>

* If constraints are [[Affine transformation|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.<ref>{{cite book|last1=Pistikopoulos, |first1=Efstratios N.; |last2=Georgiadis, |first2=Michael C.; |last3=Dua, |first3=Vivek |date=2007 |title=Multi-parametric programming:Programming Theory, algorithmsAlgorithms and applications. Weinheim,Applications |publisher=Wiley-VCH, 2007|___location=Weinheim |doi=10.1002/9783527631216 |isbn=9783527316915 }}</ref>

== Applications ==

=== In control theory generally and in process industries ===

The connection between parametric programming and [[model predictive control]] for [[process manufacturing]], established in 2000, has contributed to an increased interest in the topic.<ref>{{cite book |last1=Bemporad |first1=Alberto |last2=Morari |first2=Manfred |last3=Dua |first3=Vivek |last4=Pistikopoulos |first4=Efstratios N. |year=2000 |chapter=The explicit solution of model predictive control via multiparametric quadratic programming |title=Proceedings of the 2000 American Control Conference |pages=872 |doi=10.1109/ACC.2000.876624 |isbn=0-7803-5519-9 |s2cid=1068816 }}</ref><ref>{{cite journal |last1=Bemporad |first1=Alberto |last2=Morari |first2=Manfred |last3=Dua |first3=Vivek |last4=Pistikopoulos |first4=Efstratios N. |title=The explicit linear quadratic regulator for constrained systems |journal=Automatica |date=January 2002 |volume=38 |issue=1 |pages=3–20 |citeseerx=10.1.1.67.2946 |doi=10.1016/S0005-1098(01)00174-1}}</ref> 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<ref>[https://www.researchgate.net/publication/223477621_MPC_on_a_chip-Recent_advances_on_the_application_of_multi-parametric_model-based_control MPC on a chip—Recent advances on the application of multi-parametric model-based control | Request PDF<!-- Bot generated title -->]</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.{{Citation needed|date=February 2023}}

=== In CNC programming ===

Parametric programming in the context of CNC ([[numerical control|computer numerical control]]) is defining part-cutting cycles in terms of variables with reassignable values rather than via hardcoded/hardwired instances. An [[wikt:archetype#Noun|archetypically simple]] example is writing a [[G-code]] program to machine a family of [[washer (hardware)|washers]]: there is often no need to write 15 programs for 15 members of the family with various hole diameters, outer diameters, thicknesses, and materials, when it is practical instead to write 1 program that calls various variables and reads their current values from a table of assignments. The program then instructs the machine slides and spindles to move to various positions at various velocities, accordingly, addressing not only the sizes of the part (i.e., OD, ID, thickness) but also even the [[speeds and feeds]] needed for any given material (e.g., low-carbon steel, high-carbon steel; stainless steel of whichever grade; bronze, brass, or aluminum of whichever grade; polymer of whichever type). Custom Macros are often used in such programming.<ref name="Lynch-2023-05-12">{{cite web |last1=Lynch |first1=Mike |date=2023-05-12 |title=5 Reasons Why You Should Know How to Write Custom Macros. Custom macros enhance what can be done in G-code programs, giving users the ability to code operations that were previously not possible |url=https://www.mmsonline.com/articles/5-reasons-why-you-should-know-how-to-write-custom-macros |website=www.mmsonline.com |access-date=2023-05-20 |language=en }}</ref>

==References==

{{reflist}}

[[Category:MathematicalOptimization optimizationalgorithms and methods]]