Implicit Function Theorem. Suppose h:R^n-->R^m, where n > m, and h is in C^1. Further, suppose we can partition the variables, x = (y, z), such that y is m-dimensional with grad_y[h(x)] nonsingular at x = (y*, z*). Then, there exists e > 0 for which there is an implicit function, f, on the neighborhood, N_e(z*) = {z: ||z-z*|| < e} such that h(f(z), z)=0 for all z in N_e(z*). Further, f is in C^1 with grad_f(z*) = -grad_y[h(x)]^-1 grad_z[h(z)]. (Here are examples...need graphics browser).

Implied equality. An inequality constraint, g(x) <= 0, such that g(x)=0 for all feasible x.

Inactive constraint. A constraint that is not active (at a point).

Incidence matrix. A matrix, say M, that represents the incidence of edges or arcs to nodes in a graph or network. In the undirected case, M is binary valued: if edge k has endpoints i and j, M(i,k)=M(j,k)=1 and M(r,k)=0 for r not= i, j. In the directed case, the entry -1 indicates the tail: if the arc is directed from i to j, M(i,k)=-1 and M(j,k)=1.

Inconsistent. A system of inequalities and/or equations for which there is no feasible solution.

Independent set. Given a graph, G=[V,E], an independent set (also called a stable set) is a subgraph induced by a subset of vertices, S, plus all edges with both endpoints in S, such that no two nodes in the subgraph are adjacent. A maximal independent set is one such that adding any node causes the subgraph to violate independence -- the added node is adjacent to some node already in the set. Given weights, {w(v)} for v in V, the weight of an independent set, S, is the sum of the weights in S. The maximum independent set problem is to find an independent set of maximum weight. This is equivalent to finding a minimum weight vertex cover, say C, since V\C is an independent set. (One can also refer to an independent set of arcs (or edges) as a subgraph with no two arcs (or edges) adjacent.)

Indicator function. Its value is 0 or infinity, according to whether a point is in a (given) set or not.

Inequality. A relation of the form g(x) <= 0 or g(x) >= 0. This appears in the standard form as constraints. With equality allowed, these are called weak inequalities; strict inequalities are g(x) < 0 and g(x) > 0.

Here are particular inequalities in this glossary:
• Cauchy-Schwarz
• Hadamard
• Hölder
• Jensen
• Kantorovich
• Minkowski
• Triangle

Also see variational inequality.

Inequality of degree k. An inequality, usually linear, with k variables. This arises in integer programming, where the variables are binary. In particular, an inequality of degree 2 can represent a precedence constraint, and it has special computational advantages in the node packing problem.

Infeasible. Not feasible.

Inference dual. See it in the list of particular duals.

Infimum (abbr. Inf). The greatest lower bound on a (real-valued) function over (a subset of) its domain. If f is unbounded from below, Inf{f} = -infinity, and if the domain is empty, Inf{f} = infinity. Otherwise, suppose L is any lower bound: f(x) >= L for all x in X. L is a greatest lower bound if, for any e > 0, there exists x in the domain for which f(x) <= L+e. (That is, we can get arbitrarily close to L in the range of f.) Note that the infimum is always defined, and its range is in the extended reals. It is the minimum, if it is attained by some point in its domain.

Infinite [dimensional] program. A mathematical program with an infinite number of variables and constraints (also see semi-infinite program). Generally, this is approached as an abstract program.

Inner approximation. This solves a mathematical program by a sequence of approximations whose feasible regions are contained in the original feasible region. One example is the use of a barrier penalty method. Another example is polyhedral annexation.

Integer equivalent aggregation. Reduction of a system of linear algebraic equations with non-negative integer solutions to a single equation, which is a linear combination of the equations of the system and has the same set of non-negative integer solutions. For example, consider the system: S = {(x,y,z) in {0,1}^3: x + y = 1 and y + z = 1}. By simply adding the equations, we have the equivalent description: S = {(x,y,z) in {0,1}^3: x + 2y + z = 2}. Both sets consist of two points: (0,1,0) and (1,0,1).

Integer polyhedron. The convex hull of the feasible region of a linear IP: {x in Z^n+: Ax >= b}.

Integer program (IP). The variables are required to be integer-valued. Historically, this term implied the mathematical program was otherwise linear, so one often qualifies a nonlinear integer program vs. a linear IP. Also see mixed integer program and combinatorial program.

Integer rounding. Rounding a non-integer solution to an integer neighbor. (This will generally not yield an optimal solution to an integer program -- see Myth MIP-1.)

Interior (point) method. A family of algorithms that stays in the strict interior of the feasible region, such as a barrier function. The term grew from Karmarkar's algorithm to solve a linear program. In that case, the resulting solution (if it exists) is strictly complementary, which defines the (unique) optimal partition.

Interior penalty function. Same as barrier function.

Interior solution. An optimal solution to a mathematical program that is in the relative interior of its set of optimal solutions. This arises in interior methods, and relates to the strict complementarity of the solution.

Interpolation. The idea of estimating some value between two values. In LP, an interpolation estimate of the optimal objective value, say z(ab+(1-a)b'), is az(b) + (1-a)z(b').

Intersection cut. See convexity cut.

Inventory balance equation. The constraint that says that the amount of inventory in the next time period must equal the current inventory plus what is produced or purchased minus what is lost or sold. Let y(t) = inventory at the beginning of period t, with y(0) given. Then, the inventory equation is:

The language used is for the inventory control in the production scheduling problem, but this has become a standard system of equations that appears in many mathematical programs. Thus, the meaning of the variables can be very different. One example is the steel beam assortment problem.

Inventory control problem. See production scheduling problem.

Inverse problem. Given a point in the decision space, find parameter values that render it optimal. For example, suppose we have an LP: min{cx: Ax=b, x >= 0}. Let B be a basis from A, and we ask for the values of (b, c) for which this basis is optimal. This has a simple solution. Let A = [B N] and partition c and x conformally, so Ax = Bx_B + Nx_N and cx = c_Bx_B + c_Nx_N. Then, the set of (b, c) for which the associated basic solution is optimal is the following cone:

The problem can be combinatorial. We might want to minimize ||c–c*|| for some norm for c's are costs on the arcs or edges of a network. The solution at hand might be a spanning tree or a TSP tour. We might also impose constraints on c directly, such as simple bounds.

The general inverse problem may thus be stated:

There are variations, such as when only a partial solution is given. An example is a partial TSP tour or some partial scheduling of jobs, and we ask for cost values for which there is an optimal solution that contains these subsets.

Involutionary property. Of a transformation, it means something is its own inverse. In linear programming, the dual of the dual is the primal.

Irreducible inconsistent subsystem (IIS). A subsystem of inequalities and equations that is inconsistent, and every proper subsystem is consistent.

Irredundant. A system of constraints is said to be irredundant if it contains no redundant constraint.

Isoperimetric problem. Among all closed plane curves with a given perimeter find one that maximizes the area. This is also known as Queen Dido's problem and serves as a classical problem for variational calculus. Its significance in mathematical programming is that it led to Lagrange's multiplier theorem. Restricting shapes to rectangles, the problem is: Max{xy: x+y=p, x, y >= 0}, where 2p is the perimeter. For x, y > 0 and multiplier u, Lagrange's multiplier conditions requires y-u=0 and x-u=0, so x=y, which means the solution is the square.

Isoquant. Same as Contour.

Isotonic function (f: X–>R^m). Order preserving:   for any x,y in X,

x > y –> f(x) > f(y)   and   x < y –> f(x) < f(y).