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.