Mathematical Programming Glossary

Mathematical Programming Glossary - J

Jacobian. For a transformation, y=f(x), such that f is differentiable, the jacobian is the determinant, |grad_f(x)|. Historically, the number of y-variables equals the number of x-variables, say n, so grad_f(x) is n by n. Today, the jacobian is sometimes defined as the matrix, grad_f(x), allowing the number of functions to be less than the number of variables.

Jamming. Slow convergence, perhaps to a non-solution point -- see zigzag phenomenon.

Jeroslow formula. This arises in mixed integer linear programming as an extension of Gomory functions. Consider the following standard form

MILP: max cx + dy: Ax + Dy = b, (x, y) >= 0, x in Zⁿ,

where rank(D)=m (= number of rows). Let {B^k} be the set of bases of D such that there exists {u^k} to satisfy the dual conditions: u^k B >= d and u^k B^k = d^k. Let |_v_| denote the floor (or round-down) function, and define |_v_|_k = B^k |_[(B^k)^-1]v_|. Let V_k be the set of integer linear combinations of vectors spanned by a dual feasible basis, B^k:

V_k = {v: [(B^k)^-1]v is in Z^m}.

Let V = /\V_k, and define

U_k = {v in V_k: [(B^k)^-1]v >= 0, and 0 << [(B^k)^-1]u <= [(B^k)^-1]v implies u is not in V},

where 0 << w means 0 <= w and w not = 0. Let G be a Gomory function on R^m. A Jeroslow formula (or function) for given D is:

J(v) = max_k max{G(w) + u^k(v - w): w in V, |_v_|_k - w in U_k}.

Jensen's Inequality. Let f be convex on X, and let x be a random variable with expected value, E(x). Then, E(f(x)) >= f(E(x)). For example, let X=R and f(x) = x². Suppose x is normally distributed with mean zero and standard deviation = s. Then, E(f(x)) = E(x²) = s² >= 0 = E(x) = f(E(x)).

Job scheduling/sequencing. See scheduling jobs and sequencing problems.