Mathematical Programming Glossary - U
Mathematical Programming Glossary - U
Unbounded mathematical 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 {x^k} for which {f(x^k)} diverges to infinity (minus infinity if minimizing).

Unconstrained mathematical program. One with no constraints (can still have X be a proper subset of R^n, such as requiring 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 X could contain the strict interior, with constraints of the form 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 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 [a, b], let x* be its mode. Then, f strictly increases from a to x* and strictly decreases from x* to b (reverse the monotonicity on each side of x* if the mode is a minimum). (For line search methods, like fibonacci, the mode could occur in an interval, [a*,b*], where f strictly increases from a to a*, is constant (at its global max value) on [a*,b*], then strictly decreases on [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 {x^k}-->x. Of a function, lim sup f(x^k) <= f(x). Of a point-to-set map, let N_e[S] be a neighborhood of the set S. For each e > 0, there exists K such that for all k > K, A(x^k) is a subset of N_e[A(x)]. Here is an example of what can go wrong. Consider the feasibility map with

                _
               | (x+sqrt(2))^2 - 1  if x < 0
        g(x) = |
               |_ exp{-x}           if x >= 0    
Note g is continuous and its level set is [-sqrt(2)-1, -sqrt(2)+1]. However, for any b > 0, {x: g(x) <= b} = [-sqrt(2)-1-b, -sqrt(2)+1+b] \/ [-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, A, such that A(i, j)=0 for i >= j.

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

 


Notation


Send questions and comments to icsMPGlossary@mail.informs.org.
View the INFORMS Computing Society's Editorial Board
Copyright© 1996 – 2014, Mathematical Programming Glossary, by the INFORMS Computing Society