# All Pages

### From Glossary

Economic order quantity |

Abbreviated EOQ. This is the level of inventory to order that minimizes the sum of holding and ordering costs. The inventory function, , is the following periodic sawtooth function, where is the time between orders, and is the ordering quantity:

where is the rate of demand (inventory units per time units), and for . The inventory becomes zero at , which requires a new order of units. The model is thus:

where is the holding cost (currency per time units), so is the average holding cost, and is the fixed cost of ordering, so is the average ordering cost. The solution is , which yields the Economic Order Quantity (EOQ): . See the more general production scheduling problem.

Edge-finding |

The edge-finding rule is a constraint propagation technique that consists of deducing whether an activity can, cannot, or must be executed before or after a set of activities that all (including ) require the same resource. Two types of conclusions can then be drawn: new ordering relations (“edges” in the graph representing the possible orderings of activities) and new time-bounds (i.e., tightening of the earliest and latest start and end times of activities).

An edge-finding algorithm is a procedure that performs all such deductions.

Effective domain |

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

Efficient frontier |

The collection of efficient points, see multiple objectives.

Eigenvalue |

If a (scalar) value, , satisfies for some vector, , it is an eigenvalue of the matrix , and is an eigenvector. In mathematical programming this arises in the context of convergence analysis, where 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".

Element constraint |

is a global constraint that is true iff a variable is the th element of an array . More specifically, it involves a 1-dimensional variable array , an integer variable and variable , where , typically written as "element(X,y,z)".

Elementary matrix |

A matrix formed by performing a single row operation on the identity matrix. These arise in linear programming, particularly for the product form of the basis: , where each is an elementary matrix.

Elementary simplex method |

See simplex method.

Elementary vector |

Let be a subspace of . For , let denote its support set: . Then, is an elementary vector of if there does not exist such that and . This extends to where is not a subspace, such as the collection of non-negative vectors in, in which case is the set of coordinates with positive value. This is of particular importance in defining the optimal partition of an LP solution.

Ellipsoid |

An ellipsoid centered at is the set

where is a symmetric, positive definite matrix.

Ellipsoid method |

This algorithm seeks to solve by iterations that begin with and , where is a measure of the smallest datum that can be represented -- i.e., is a solution if, and only if, it satisfies . If the current iterate, , does not satisfy this, a new pair is defined by choosing one of the violated inequalities, say . Then, let , and apply the following rules:

By treating the objective as a constraint, say and/or , 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 (where the matrix is ). For example, consider :

Then, is in the elliptope for if,
and only if, , i.e. it is diagonally
dominate (note the dimension is 1). An elliptope is also called a
set of *correlation matrices*.

Epigraph |

This is the region on or above the graph of a function :

Equilibrium basis |

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

Equivalent CSPs |

Consider two constraint satisfaction problems and and a sequence of their common variables. We say that and are *equivalent w.r.t* if

- for every solution to a solution to exists that coincides with on the variables in X, and
- for every solution to a solution to exists that coincides with on the variables in X.

Euclidean norm |

See norm.

Euler-Lagrange equation |

This is a necessary condition for to solve the classical problem in variational calculus:

where .

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 Optimization, 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 |

A penalty function is exact if there exists a finite parameter value such that its maximum is a solution to the original mathematical program.

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 linear programming, these are the only sources of non-existence. In nonlinear programming, 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 linear programming, see theorems of the alternative.

Expanding subspace theorem |

Let be the subspace spanned by vectors , which are Q-conjugate. Let be any initial point in , and let be generated by these conjugate directions with optimal line search:

Then, minimizes on the affine set, .

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.

Extended reals |

Typically denoted by , this is the set of real numbers augmented with positive and negative infinity, i.e.

Extensional constraint |

*extensional*fashion by specifying a

*table*that summarizes all allowed (or in an alternative formulation, all disallowed) combinations of assignments to the variables in .

For instance, the extensional constraint expresses the intensional constraint where and can take values .

Also called a table constraint.

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 over and let in order to approach the solution to

If, during the penalty iterations, for some finite , then solves the original mathematical program. Otherwise, the idea is that approaches the feasibility condition, , as gets large (though this need not happen without assumptions on and ).

Extrapolation |

The idea of estimating a value by extending information at hand outside its immediate range. In linear programming, an extrapolation estimate of the optimal objective value uses dual price as a slope: . For a sequence , an extrapolation is an estimate of a limit point.

Extreme point |

A point in the closure of a set, say , that is not the midpoint of any open line segment with end points in closure of . Equivalently, is an extreme point of a closed set, , if there do not exist for which . When is a polyhedron of the standard form, , with of full row rank, we have one of the fundamental theorems of linear programming that underlies the simplex method:

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

Extreme ray |

An extreme ray of a closed set is a ray in that cannot be expressed as a (simple) sum of other rays in . For example, the axes,
, are extreme rays of the non-negative vectors in
. The ray , however, is the sum of
the axes since . The
recession direction of an extreme ray is sometimes called an
*extreme direction*.

Extreme value |

An extremum (pl. extrema). A minimum or maximum.

Categories: Constraint Programming | Nonlinear Programming | Linear Programming | Constraint Programming | Linear Algebra & Geometry | Linear Programming | Linear Algebra & Geometry | Linear Algebra & Geometry | Linear Programming | Linear Algebra & Geometry | Linear Programming | Constraint Programming | Linear Algebra & Geometry | Nonlinear Programming | Nonlinear Programming | Nonlinear Programming | Nonlinear Programming | Nonlinear Programming | Nonlinear Programming | Nonlinear Programming | Constraint Programming | Nonlinear Programming | Linear Algebra & Geometry | Linear Algebra & Geometry | Nonlinear Programming