Face. A convex subset, say S, of a convex set, say C, such that [x, y] in C and [x, y] /\ ri(S) not empty imply x, y are in S. C, itself, is a face of C, and most authors consider the empty set a face. The faces of zero dimension are the extreme points of C. When C is a polyhedron, {x: Ax <= b}, the faces are the subsystems with some inequalities holding with equality: {x: Bx = c, Dx <= d}, where A = [B D] and b = [c' d']'.

Facet. A face of a convex set, not equal to the set, of maximal dimension. If the set is polyhedral, say P = {x: Ax <= b}, where the defining inequalities are irredundant, the facets are in 1-1 correspondence with {x in P: A(i,.)x = b_i} for i such that the equality is not forced – i.e., there exists x in P for which A(i,.)x < b_i.

Facet-defining inequality. In integer programming, an inequality, ax >= b, such that {x in IP: ax >= b} is a facet of the integer polyhedron, IP.

Facility location problem. Find a location (say x-y coordinates) that minimizes a weighted sum of distances to each of several locations. An example is to locate a hospital or school to serve a community defined by population centers. Originally considered by Fermat in the 17th century, there are now many variations of this problem. One variation is the location of an obnoxious facility, such as a garbage dump. In that case the objective is to maximize total (weighted) distance from the given points (there are constraints, such as cost, that require the location to be within some distance of the points).

Factorable function. This has a recursive definition, relative to a collection of elementary operations (e.g., sum, product) on other factorable functions, starting with some set of primitive functions. For example, starting with the power functions, ax^n, for any a and n, and allowing only the sum operation, we can obtain all polynomials. The polynomial x + 2x^2 + 9x^3 factors into 3 parts.

Factorable program. All functions (objective and constraints) are factorable. An example is the separable program, if each of the univariate functions are factorable. Another is the geometric program, where each posynomial is factorable.

Factored form of basis. Originally for linear programming, this pertains to writing a basis B in the form, B = F_1 F_2 ... F_k, where F_i are factors. Two forms of interest are: elementary factors, where each Fi is an elementary matrix, and LU decomposition: B=LU, where L is lower triangular and U is upper triangular. (L and U might be factored, notably into elementary matrices, which are lower and upper triangular, resp.) These have inexpensive updates when B changes to an adjacent basis.

Fallacy of Averages. Imagine standing with one foot on a keg of ice and the other in a fire. Your average body temperature may be fine, but the extremes will kill you! The fallacy of averages is the fallacious results you may get when replacing data with their expected values. Formally, the fallacy is stated as E(XY) not= E(X)E(Y) – viz., the covariance is not zero. Another form of this fallacy is that E(f(X)) not= f(E(X)) (unless f is linear). In particular, suppose we have

Farkas' lemma. See it in the list of alternative systems.

Fathom. Arises in directed tree search. A node is fathomed if it is determined that no completion from this point could produce a better solution than one already obtained. This could happen by bounding the objective, or it can happen by determining there is no feasible solution with the partial specifications corresponding to the node.

Feasibility map. The point-to-set map that maps a right-hand side to a feasible region: (b, c)-->{x in X: g(x) <= b, h(x) = c}.

Feasible. A point is feasible if it satisfies all constraints. The feasible region (or feasibility region) is the set of all feasible points. A mathematical program is feasible if its feasible region is not empty.

Feasible direction. Given a feasible point x, a direction vector, say d, is feasible if there exists s > 0 such that x+sd is feasible. The method of feasible directions is designed to choose a feasible direction at each iteration, along which (as s becomes positive) the objective value improves. Such directions exist for continuous mathematical programs (where the line segment [x, x+sd] is feasible for some s > 0) unless x is a local optimum. (Note: with nonlinear constraints, there is typically no feasible direction according to this (classical) definition. See the generalized reduced gradient method.)

Fermat-Weber problem. See facility location problem. .

Fibonacci search. This finds the maximum of a unimodal function on an interval, [a, b], by evaluating points placed according to a fibonacci sequence, {F_N}. If there are F_N points in the interval, only N evaluations are needed. In the continuous case, we begin with some interval of uncertainty, [a,b], and we reduce its length to (b-a)/F_N. The ratio, g_n = F_(n-1)/F_n, is the key to the placements.

Here is the method for the continuous case:
1. Initialization. Let x = a + (1 - g_N)(b-a) and y = a + g_N(b-a). Evaluate f(x) and f(y) and set n=N.
2. Iteration. If f(x) < f(y), reduce the interval to (x, b] (i.e., set a=x), decrement n to n-1, and set x = y and y = a + g_n(b-a). If f(x) >= f(y), reduce the interval to [a, y) (i.e., set b=y), decrement n to n-1, and set y = x and x = a + (1-g_n)(b-a).

For very large N, the placement ratio (g_N) approaches the golden mean, and the method approaches the golden section search. Here is a comparison of interval reduction lengths for fibonacci, golden section and dichotomous search methods. In each case N is the number of evaluations needed to reduce length of the interval of uncertainty to 1/F_N. For example, with 20 evaluations dichotomous search reduces the interval of uncertainty to .0009765 of its original length (with separation value near 0). The most reduction comes from fibonacci search, which is more than an order of magnitude better, at .0000914. Golden section is close (and gets closer as N gets larger).

    Evaluations  Fibonacci      Dichotomous      Golden section
        N          1/F_N        1/2|_N/2_|       1/(1.618)(N-1) 
    ============================================================
        5         .125            .25              .146
       10         .0112           .0312            .0131
       15         .00101          .00781           .00118
       20         .0000914        .000976          .000107 
       25         .00000824       .0002441         .0000096 
    =============================================================
      

         N    F_N
       ==============
         0      1
         1      1
         2      2
         3      3
         4      5
         5      8
         6     13
         7     21
         8     34
         9     55
        10     89
        20  10946
        50    2.0E10
       100    5.7E20
      ==============     

Fill-in. Arises in the context of sparse matrices subjected to certain operations. In particular, a basis may be factored in a product of elementary matrices to represent Gaussian elimination. The nonzeroes that appear in positions that were not in the original matrix are called fill-in coefficients. An example of a matrix that has no fill-in for this factorization is one that is lower triangular. In that case the factors appear as:

         _     _     _     _  _     _  _     _
        | * 0 0 |   | * 0 0 || 1 0 0 || 1 0 0 |
        | * * 0 | = | * 1 0 || 0 * 0 || 0 1 0 |
        |_* * *_|   |_* 0 1_||_0 * 1_||_0 0 *_|

         _     _     _     _  _     _  _     _
        | * 0 * |   | * 0 0 || 1 0 0 || 1 0 * |
        | * * 0 | = | * 1 0 || 0 * 0 || 0 1 # |
        |_* * *_|   |_* 0 1_||_0 * 1_||_0 0 *_|

First-order conditions. This descends from classical optimization, using Taylor's Theorem. For unconstrained optimization, this is simply that grad_f(x*)=0. (In variational calculus, it is the Euler-Lagrange equation.) For constrained optimization, the first-order conditions of a regular mathematical program is given by the Lagrange Multiplier Rule.

Fixed charge. A cost that is some value, say C, regardless of the level as long as the level is positive; otherwise the fixed charge is zero. This is represented by Cv, where v is a binary variable. When v=0, the fixed charge is 0; when v=1, the fixed charge is C. An example is whether to open a plant (v=1) or not (v=0). To apply this fixed charge to the non-negative variable x, the constraint x <= Mv is added to the mathematical program, where M is a very large value, known to exceed any feasible value of x. Then, if v=0 (e.g., not opening the plant that is needed for x > 0), x=0 is forced by the upper bound constraint. If v=1 (e.g., plant is open), x <= Mv is a redundant upper bound. Fixed charge problems are mathematical programs with fixed charges. (See Myth MIP-3 to avoid misconception.)

Fixed point. Of a function, f:X-->X, f(x)=x. Of a point-to-set map, F:X-->2^X, x is in F(x). The study of fixed points has been at the foundation of algorithms. Moreover, particular fixed point theorems have direct application in mathematical programming.

Fixed variable. A variable whose value is fixed, either explicitly or implicitly. Explicit fixing arises for convenience of scenario design, particularly in linear programming, and during an algorithm's progression, particularly in integer programming. Implicit fixing occurs from a forcing substructure.

Fleet mix problem. To determine how many of each type of aircraft should be in a fleet to meet demands and minimize total cost. Here is an integer linear program model:

where N_j = number of aircraft of type j available; A_ij = capacity of aircraft type j for mission i; a_i = least number of missions of type i that must be flown; b_i = greatest number of missions of type i that must be flown. The variables are x_j = number of aircraft of type j in the fleet, and c_j is its maintenance cost. If the aircraft must be purchased, binary variables are introduced, as x_j - N_j y_j <= 0, with a fixed charge, fy, in the objective (f > 0). There could be additional constraints, such as a budget on total purchases (fy <= f₀) or on total maintenance (gx <= g₀).

Floor. This is the integer round-down of a value, x:

Floor(x) = max{z: z integer, z <= x}.

Flow augmenting path. This arises in the Ford-Fulkerson labeling algorithm to find a maximum flow in a network with arc flow bounds, L,U Given a flow, f, from a source to a sink, a flow augmenting path, relative to f, is a path from that source to sink such that

f(x, y) < U(x, y) along all forward arcs;   f(x, y) > L(x, y) along all backward arcs.

Forced equality. This is an inequality constraint that must hold with equality in every feasible solution.

Forcing substructure. A subsystem of the constraints and the variables in them that forces some value. For example, the following system is a forcing substructure because each variable, which is required to be non-negative, is forced to be zero.

               -x - y     = 0
                    y - z = 0       

Forward substitution. The recursion to solve a nonsingular lower triangular system, Lx=b. It starts with x(1) = b(n)/U(1,1), then

Forward transformation (abbr. FTRAN). This applies to the factored system, [E_1 E_2 ... E_n]x = b, where each E_i is an elementary matrix. The recursion is:

E_1 x_1 = b

E_2 x_2 = x_1

...

E_n x_n = x_(n-1)

In the end, x = x_n is the solution. Each elementary system is solved as follows. For notational convenience, suppose the system is Ex = y, and v is the distinguished p-th column of E. Then,

This is what is done in the (revised) simplex method, and each elementary solution is a pivot operation.

Forward triangularization. An algorithm to rearrange a matrix by recursively assigning a singleton row to the front (with its only column, as its pivot). The recursion applies to the submatrix defined by omitting the assigned row and column (and reducing other row counts accordingly). This results in a lower triangular rearrangement if, and only if, such a rearrangement exists.

Fourier-Motzkin elimination. A procedure by which a variable is eliminated in a system of linear inequalities. The remaining inequalities, which include some new ones, has a solution if, and only if, the original system has a solution. Eventually, this reduces to one variable or an inconsistency is determined during the elimination. The one variable can be assigned any value in its range, then a backtracking procedure can be executed to obtain values of the other variables, which were eliminated. Originally presented by Fourier in 1826, Motzkin analyzed it in 1933 in light of new developments of the theory of linear inequalities to solve linear programs. Its computational complexity is exponential, and it gave way to the simplex method.

Frank-Wolfe Theorem. If a quadratic function is bounded from below on a nonempty polyhedron, it attains a minimum there. In mathematical notation, we are given that X is a nonempty polyhedron. Then, if there exists L such that f(x)>=L for all x in X, there exists x* in X such that f(x*)<=f(x) for all x in X.

Fractional program. Objective and/or constraint functions are sums of ratios of the form V(x)/D(x), where it is usually assumed that D(x) > 0 over X. The case of one term is special, and the linear fractional program has affine numerator and denominator. The linear 1-term case, (ax+b)/(cx+b) (where cx+b > 0 over the feasible region), is equivalent to solving a parametric linear program:  opt (ax+b) – u(cx+b): x in X, where u is the parameter.

Free variable. A variable with no (explicit) sign restriction. (The term is generally used in linear programming because the standard form has x >= 0.)

Fritz John conditions. These extend Carathéodory's conditions to deal with inequality constraints:

Suppose x* is in argmax{f(x): x in R^n, g(x) <= 0}, where f and g are in C^1. Then, there exists multipliers (y0, y) >= 0, not all zero, such that y0 grad_f(x) - y grad_g(x) = 0 and yg(x) = 0.

Fuzzy mathematical program. Some (or all) constraints are fuzzified by replacing the level set, G_i={x in X: g_i(x) <= 0}, with the requirement that u_G_i(x) >= a_i, where u_G_i is a membership function that is given (or derived from primitive membership functions on the level sets of each g_i), and a_i is a parameter in [0,1] to be set for each instance of the model. Typically (but not necessarily), a_i = 1 means that the constraint must hold, and the lower the value of a_i, the more x's are admitted. (This appears similar to the chance-constraint model of stochastic programming, but it is more closely related to goal programming.) While fuzzy sets are used to represent uncertainty, they can also be used to represent preferences – e.g., a requirement, u_S(x) >= u_T(x) could mean that it is preferred that x be in S at least as much as it is preferred that x be in T.

Fuzzy set. Given a universe set, X, and a membership function, u:X-->[0,1], a fuzzy set is a collection of pairs: {(x, u(x)): x in X}. Often, the membership function is subscripted by the set name, say u_S. Generally, for all x in X, u_X(x)=1, and u_Ø(x)=0. In the context of uncertainty, the value u_S(x) is used to model the statement of how possible it is for x to be in S. For this reason, u_S is sometimes called the possibility function of S. What we consider the usual set (without a membership function) is called a crisp set in fuzzy mathematics.

Fuzzy set operations, say on fuzzy sets S and T, with membership functions u_S and u_T, resp., are defined by the following:

• Union: u_[S\/T](x) = Max{u_S(x), u_T(x)}.

• Intersection: u_[S/\T](x) = Min{u_S(x), u_T(x)}.

• Complement: u_~S(x) = 1 - u_S(x).

One must be careful when using fuzzy sets to represent uncertainty (which is not the only type of interpretation – see fuzzy mathematical program). In particular, if u_S(x) = 1/2, its complement is also 1/2. Thus, u_[S\/~S](x) = 1/2, despite the fact that S\/~S = X (in ordinary set theory). Similarly, u_[S/\~S](x) = 1/2, despite the fact that S/\~S = Ø. This illustrates the fact that u_S need not equal u_T even if S=T as crisp sets.

While the fuzzy set is fundamental for fuzzy mathematical programming, other concepts in fuzzy mathematics also apply, such as fuzzy arithmetic, fuzzy graphs and fuzzy logic.