
Mathematical Programming Glossary  U
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 integervalued (given integervalued righthand sides), thus obtaining a solution simply by a simplex method. An example of a totally unimodular matrix is the nodearc incidence matrix of a network, so basic solutions of network flows are integervalued (given integervalued supplies and demands). Unitary matrix. A nonsingular matrix whose Hermitian adjoint equals its inverse (same as orthogonal for realvalued matrices). Univariate optimization. A mathematical program with a single variable. Upper semicontinuity. (or upper semicontinuous, abbr. usc). Suppose {x^k}>x. Of a function, lim sup f(x^k) <= f(x). Of a pointtoset 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 >= 0Note 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)1b, 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 righthand 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.
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 