Economic order quantity (EOQ). This is the level of inventory to order that minimizes the sum of holding and ordering costs. The inventory function, I(t), is the following periodic sawtooth function, where T = time between orders, and Q = ordering quantity:

I(t) = Q - dt   for   0 <= t <= T,

min ½ hdT + K/T,

Effective domain. The domain of a function for which its value is finite.

Efficient frontier. See multiple objectives.

Eigenvalue and eigenvector. If a (scalar) value, t, satisfies Ax = tx for some vector, x not= 0, it is an eigenvalue of the matrix A, and x is an eigenvector. In mathematical programming this arises in the context of convergence analysis, where A is the hessian of some merit function, such as the objective or Lagrangian.

Elastic program. Same as Phase I, the artificial variables are called elastic with the idea that the constraints can "stretch".

Elementary matrix. One that differs from the identity matrix in one column (or row). It arises in linear programming, particularly for the product form of the basis: B = E_1 E_2 ... E_m, where each E_i is an elementary matrix.

Elementary simplex method. See simplex method.

Elementary vector. Let V be a subspace of R^n. For v in S, let S(v) denote its support set: {j: v_j <> 0}. Then, v is an elementary vector of V if there does not exist v' in V such that v' not= 0 and S(v') is a subset of S(v). This extends to where V is not a subspace, such as R^n+, in which case S(v) is the set of coordinates with positive value. This is of particular importance in defining the optimal partition of an LP solution.

Ellipsoid. Centered at c, this is the set

Ellipsoid method. This algorithm seeks to solve Ax <= b by iterations that begin with x=0 and Q=diag(2^-L), where L is a measure of the smallest datum that can be represented -- i.e., x is a solution if, and only if, it satisfies Ax <= b + 2^-L. If the current iterate, x, does not satisfy this, a new pair (x', Q') is defined by choosing one of the violated inequalities, say A_i.x > b_i. Then, let v = A_i.', and apply the following rules:

1. x' = x - Qv / (n+1)sqrt(v'Qv)

2. Q' = n^2/(n^2 - 1) [Q - 2[vv'] / (n+1)(v'Qv)]

By treating the objective as a constraint, say cx <= cx* - e and/or cx >= cx* + e, the ellipsoid method can be used to solve a linear program. Its significance is that it was the first algorithm for linear programming shown to have polynomial time complexity.

Elliptope. This arises in semi-definite programming. It is the set of all real, square symmetric matrices whose diagonal entries are all equal to one and whose eigenvalues are all non-negative. The dimension of the set is n(n-1)/2 (where the matrix is n×n). For example, consider n=2:

 
               .-    -.
               | 1  a |
           M = |      |
               | a  1 |
               |_    _| 

Epigraph (abbr. epi{f,X}). {(x, z): x in X, z >= f(x)} = region on or above the graph of f.

Equilibrium basis. In LP, this is a basis that is optimal in both the primal and the dual. It arises in compatibility theory and degeneracy graphs.

Euclidean norm. See norm.

Euler-Lagrange equation. These are necessary conditions for y to solve the classical problem in variational calculus:

                         _x 
                        | 
               dF/dy' = | (dF/dy) dx  +  c.
                        |   
                       _|x0     

(Sorry for the sad looking integral, but such is an ASCII world.)

Evolutionary algorithm. This is a term that applies to any metaheuristic based on some biological metaphor that is a dynamical system whose evolution rules have a stochastic component. In particular, it includes genetic algorithms, scatter search, Particle Swarm Opimization, and some neural networks. It emerged as a unification of related computational methods, including cellular automata, which was conceived by Ulam and von Neumann in the 1940s. This unification is not universal. Some researchers cling to the GA metaphor, but say that evolutionary algorithms have more operators; some say that the GA population is composed of bit strings, whereas evolutionary algorithms can have a broader range of population structures. It is the concept of evolution dynamics, which is population-based and stochastic, that distinguishes this class of algorithms from other methods of global optimization. Evolutionary computation uses the evolutionary algorithm as its foundation; typically, it is massively parallel.

Exact penalty function. See penalty function.

Existence of solution. This pertains to whether a mathematical program has a solution. One source of non-existence is that the feasible region is empty. Another is that it is unbounded, and it is possible to have a sequence of feasible points whose objective value diverges. In LP, these are the only sources of non-existence. In NLP, however, we can have asymptotes such that the objective is bounded but cannot achieve its infimum or supremum. See the Bolzano-Weierstrass theorem, which is fundamental. For LP, see theorems of the alternative

Expanding Subspace Theorem. Let S_k be the subspace spanned by vectors {d^k}, which are Q-conjugate. Let x^0 be any initial point in R^n, and let {x^k} be generated by these conjugate directions with optimal line search:

Explicitly quasiconcave function. Negative is explicitly quasiconvex.

Explicitly quasiconvex function. A quasiconvex function that is also strictly quasiconvex. Its main property is that it rules out flat portions that cause the closure condition to fail. (Every convex function is explicitly quasiconvex.)

Exponent matrix. Powers of variables in posynomials in a geometric program.

Exterior penalty function. A penalty function in which the associated algorithm generates infeasible points, approaching feasibility in the limit towards a solution. An example is to maximize f(x) - u h(x)^2: x in X and let u-->inf in order to approach the solution to Max{f(x): x in X, h(x)=0}. If, during the penalty iterations, h(x*)=0 for some finite u, x* solves the original mathematical program. Otherwise, the idea is that x*(u) approaches the feasibility condition, h(x*)=0, as u gets large (though this need not happen without assumptions on f and h).

Extrapolation. The idea of estimating a value by extending information at hand outside its immediate range. In LP, an extrapolation estimate of the optimal objective value uses dual price (y) as a slope: z^(b + h) = z(b) + yh. For a sequence {x^k}, an extrapolation is an estimate of a limit point.

Extreme point. A point in the closure of a set, say S, that is not the midpoint of any open line segment with end points in cl(S). Equivalently, x is an extreme point of a closed set, S, if there do not exist y, z in S\{x} for which x = (y + z)/2. When S is a polyhedron of the standard form, S={x: Ax=b, x >= 0}, with A of full row rank, we have one of the fundamental theorems of linear programming that underlies the simplex method:

x is an extreme point of the feasible region if, and only if, x is a basic feasible solution.

Extreme ray of a closed set S. A ray in S that cannot be expressed as a (simple) sum of other rays in S. For example, the axes, {te_j: t >= 0}, are extreme rays of R^n+. The ray {te: t >= 0}, however, is the sum of the axes since (t,...,t) = te_1 + ... + te_n. The recession direction of an extreme ray is sometimes called an extreme direction.

Extreme value (or extremum, pl. extrema). Minimum or maximum.