All Pages

From Glossary

Jump to: navigation, search

Unbounded math program

The objective is not bounded on the feasible region  (from above, if maximizing; from below, if minimizing). Equivalently, there exists a sequence of feasible points, say LaTeX: \textstyle x^k for which LaTeX: \textstyle f(x^k) diverges to infinity (minus infinity if minimizing).

Unconstrained math program

One with no constraints (can still have LaTeX: X be a proper subset of LaTeX: \textstyle \mathbb{R}^n, such as requiring LaTeX: x to be integer-valued.)

Unconstrained optimization

Taken literally, this is an unconstrained mathematical program. However, this phrase is also used in a context that LaTeX: X could contain the strict interior, with constraints of the form LaTeX: g(x) < 0, but the mathematical program behaves as unconstrained. This arises in the context of some algorithm design, as the solution is known to lie in the interior of LaTeX: X, such as with the barrier function. As long as the algorithm has a continuous trajectory, this abuse is ok, but the constraints must be considered if one could jump, as in pattern search.

Unimodal function

Has one mode (usually a maximum, but could mean a minimum, depending on context). If f is defined on the interval LaTeX: [a, b], let LaTeX: x^* be its mode. Then, LaTeX: f strictly increases from LaTeX: a to LaTeX: x^* and strictly decreases from LaTeX: x^* to LaTeX: b (reverse the monotonicity on each side of LaTeX: x^* if the mode is a minimum). (For line search methods, like fibonacci, the mode could occur in an interval, LaTeX: [a^*,b^*], where LaTeX: f strictly increases from LaTeX: a to LaTeX: a^*, is constant (at its global max value) on LaTeX: [a^*,b^*], then strictly decreases on LaTeX: [b^*,b].)

Unimodular matrix

A nonsingular matrix whose determinate has magnitude 1. A square matrix is totally unimodular if every nonsingular submatrix from it is unimodular. This arises in (linear) integer programming because it implies a basic solution to the LP relaxation is integer-valued (given integer-valued right-hand sides), thus obtaining a solution simply by a simplex method. An example of a totally unimodular matrix is the node-arc incidence matrix of a network, so basic solutions of network flows are integer-valued (given integer-valued supplies and demands).

Unitary matrix

A nonsingular matrix whose Hermitian adjoint equals its inverse (same as orthogonal for real-valued matrices).

Univariate optimization

A mathematical program with a single variable.

Upper semi-continuity

(or upper semi-continuous, abbr. usc). Suppose LaTeX: \textstyle \{x^k\} \to x. Of a function, LaTeX: \textstyle \limsup f(x^k) \le f(x). Of a point-to-set map, let LaTeX: \textstyle \mbox{N}_e\lbrack\mbox{S}\rbrack be a neighborhood of the set S. For each e > 0, there exists K such that for all LaTeX: \textstyle k > \mbox{K}, \mbox{A}(x^k) is a subset of LaTeX: \textstyle \mbox{N}_e\lbrack\mbox{A}(x)\rbrack. Here is an example of what can go wrong. Consider the feasibility map with

g(x) =
<pre>(x+\sqrt{2})^2 - 1, & \mbox{if } x < 0 \\
e^{-x}, & \mbox{if } x \ge 0

Note g is continuous and its level set is LaTeX: \textstyle \lbrack -\sqrt{2} - 1, -\sqrt{2} + 1 \rbrack. However, for any

LaTeX: \textstyle b > 0, \{x: g(x) \le b\} = \lbrack - \sqrt{2} - 1 - b, - \sqrt{2} + 1 + b \rbrack \lor \lbrack - \log b, \inf),

which is not bounded. The map fails to be usc at 0 due to the lack of stability of its feasibility region when perturbing its right-hand side (from above).

Upper triangular matrix

A square matrix, LaTeX: A, such that LaTeX: \textstyle \mbox{A}_{i, j} = 0 \mbox{ for } i \ge j.

Utility function

A measure of benefit, used as a maximand in economic models.

Personal tools