Extra:Mathematical programming

From Glossary

A mathematical program is an optimization problem of the form:

$LaTeX: \max \{ f(x) : x \in X, \; g(x) \le 0, \; h(x) = 0 \}$

where $LaTeX: \textstyle X$ is a subset of $LaTeX: \mathbb{R}^n$ and is in the domain of $LaTeX: f$ , $LaTeX: g$ and $LaTeX: h$ , which map into real spaces. The relations, $LaTeX: x \in X$ , $LaTeX: g(x) \le 0$ , and $LaTeX: h(x) = 0$ are called constraints, and $LaTeX: f$ is called the objective function.

There are forms that deviate from this paradigm, and it is typically a modeling issue to find an equivalent standard form. Important examples are as follows:

A point $LaTeX: x$ is feasible if it is in $LaTeX: X$ and satisfies the constraints: $LaTeX: g(x) \le 0$ , and $LaTeX: h(x) = 0$ . A point $LaTeX: x^*$ is optimal if it is feasible and if the value of the objective function is not less than that of any other feasible solution: $LaTeX: f(x^*) \ge f(x)$ for all feasible $LaTeX: x$ . The sense of optimization is presented here as maximization, but it could just as well be minimization, with the appropriate change in the meaning of optimal solution: $LaTeX: f(x^*) \le f(x)$ for all feasible $LaTeX: x$ .

A mathematical program is often extended to indicate a family of mathematical programs over a parameter space, say $LaTeX: P$ . This merely involves extending the domain of the functions, $LaTeX: f$ , $LaTeX: g$ and $LaTeX: h$ , and we use the semi-colon to separate the decision variables from the parameters.

$LaTeX: \max \{ f(x,p) : x \in X, \; g(x,p) \le 0, \; h(x,p) = 0 \}.$

We could also have $LaTeX: X$ depend on $LaTeX: p$ , but the above form generally suffices.

Mathematical programming is the study or use of the mathematical program. It includes any or all of the following:

Theorems about the form of a solution, including whether one exists;
Algorithms to seek a solution or ascertain that none exists;
Formulation of problems into mathematical programs, including understanding the quality of one formulation in comparison with another;
Analysis of results, including debugging situations, such as infeasible or anomalous values;
Theorems about the model structure, including properties pertaining to feasibility, redundancy and/or implied relations (such theorems could be to support analysis of results or design of algorithms);
Theorems about approximation arising from imperfections of model forms, levels of aggregation, computational error, and other deviations;
Developments in connection with other disciplines, such as a computing environment.

One taxonomy for mathematical programming is by its defining ingredients:

Retrieved from "http://glossary.computing.society.informs.org/ver2/mpgwiki/index.php/Extra:Mathematical_programming"

Extra:Mathematical programming

From Glossary

Views

Personal tools

Search