# Extra:Mathematical programming

Jump to: navigation, search

# Mathematical Programming

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: