Extra:Mathematical programming

From Glossary

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:

Personal tools