All Pages

From Glossary

Jump to: navigation, search

FTRAN

This applies to the factored system,

LaTeX: E_1 E_2 ... E_n x = b,

where each LaTeX: E_i is an elementary matrix. The recursion is:

LaTeX: 
\begin{array}{rcl}
E_1 x_1 & = & b \\
E_2 x_2 & = & x_1 \\
& \vdots & \\ 
E_n x_n & = & x_{n-1}
\end{array}

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

LaTeX: x(p) = y(p)/v(p), and LaTeX: x(i) = y(i) - v(i)x(p) for LaTeX: i \ne p.

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


Face

A convex subset, say LaTeX: S, of a convex set, say LaTeX: C, such that for any LaTeX: x and LaTeX: y in LaTeX: C

LaTeX: \{(1 - \alpha) x + \alpha y : 0 \le \alpha \le 1 \} \cap \mbox{ri}(S) \neq \emptyset
\Rightarrow x, \; y \in S.

The set LaTeX: C is itself a face of LaTeX: C, and most authors consider the empty set a face. The faces of zero dimension are the extreme points of LaTeX: C. When LaTeX: C is a polyhedron, i.e. LaTeX: \{x : Ax \le b\}, the faces are the subsystems with some inequalities holding with equality: LaTeX: \{x: Bx = c, \; Dx \le d\}, where LaTeX: A = [B \; D] and LaTeX: b = [c^T \; d^T]^T.


Facet

A face of a convex set, not equal to the set, of maximal dimension. If the set is polyhedral, say LaTeX: P = \{x: Ax \le b\}, where the defining inequalities are irredundant, then the facets are in one-to-one correspondence with LaTeX: \{x \in P: A_{i,:} x = b_i\} for LaTeX: i such that the equality is not forced – i.e., there exists LaTeX: x in LaTeX: P for which LaTeX: A_{i,:} x < b_i. Here LaTeX: A_{i,:} is the i-th row of LaTeX: A.


Facet-defining inequality

In integer programming, an inequality, LaTeX: a^Tx \ge b, such that LaTeX: \{x \in P: a^Tx \ge b\} is a facet of the integer polyhedron, LaTeX: P.


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, LaTeX: ax^n, for any LaTeX: a and LaTeX: n, and allowing only the sum operation, we can obtain all polynomials. The polynomial LaTeX: x + 2x^2 + 9x^3 factors into 3 parts.


Factorable program

All functions (objective and constraints) are factorable. An example is the separable program, provided that each of the univariate functions is 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 LaTeX: B in the form, LaTeX: B = F_1 F_2 ... F_k , where LaTeX: F_i are factors. Two forms of interest are: elementary factors, where each LaTeX: F_i is an elementary matrix, and LU decomposition: LaTeX: B=LU, where LaTeX: L is lower triangular and LaTeX: U is upper triangular. (LaTeX: L and LaTeX: U might be factored, notably into elementary matrices, which are lower and upper triangular, resp.) These have inexpensive updates when LaTeX: B changes to an adjacent basis.


Fail first principle

The fail first principle is an idea of what a variable ordering heuristic should attempt to do in tree search. It suggests that the variable to be assigned next should be the one which is most likely to lead to a dead-end. The heuristic aims at proving that the search is in a sub-tree with no feasible solutions as soon as possible.

One way of operationalizing this principle, is to choose the next variable to assigned to be the variable which is the most constrained. The extent to which a variable is constrained can be measured in different ways. One simple measure being the current size of the domain. Under this measure, the variable which has the smallest domain should be assigned next. Another common measure is to select the variable that appears in the largest number of constraints. More sophisticated estimates exist.


Faithfully convex

A convex function is faithfully convex if it is constant along some segment only if it is constant along the whole line containing this segment.


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 LaTeX: E(XY) \ne E(X)E(Y) – viz., the covariance is not zero. Another form of this fallacy is that LaTeX: E(f(X)) \ne f(E(X)) (unless LaTeX: f is linear). In particular, suppose we have

LaTeX: \max f(x; p): g(x; p) \le 0,

where LaTeX: p is a vector of parameters with some uncertainty. The fallacy of averages suggests that it is a mistake to replace LaTeX: p with its expected value for at least 2 reasons: (1) members of LaTeX: p may be correlated, and (2) the average values of LaTeX: f and LaTeX: g need not equal the functional values at the mean.


Farkas lemma

This result gives an alternative system, of which there are many. Farakas' Lemma states that exactly one of the following is consistent,

LaTeX: Ax = b, \; x \ge 0   (exclusive or)   LaTeX: A^Ty \ge 0, \; b^Ty < 0.

An often used variant is

LaTeX: Ax \ge b   (exclusive or)   LaTeX: A^Ty = 0, \; y \ge 0, \; b^Ty < 0.


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 could 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:

LaTeX: (b, c) \mapsto \{x \in X: g(x) \le 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.

The term feasible doesn't imbue other properties such as convexity or connectedness. For example, a feasible region to a nonlinear program could be LaTeX: \{ x : x^2 \ge 1 \}, which is the disjoint union LaTeX:  \{x : x \ge 1 \} \cap \{x : x \le -1\}.

Feasible direction

Given a feasible point LaTeX: x, a direction vector, say LaTeX: d, is feasible if there exists LaTeX: s > 0 such that LaTeX: x + sd is feasible. The method of feasible directions is designed to choose a feasible direction at each iteration, along which (as LaTeX: s becomes positive) the objective value improves. Such directions exist for continuous mathematical programs (where the line segment LaTeX: [x, x + sd] is feasible for some LaTeX: s > 0) unless LaTeX: 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, LaTeX: [a, b], by evaluating points placed according to a fibonacci sequence, LaTeX: F_N. If there are LaTeX: F_N points in the interval, only LaTeX: N evaluations are needed. In the continuous case, we begin with some interval of uncertainty, LaTeX: [a,b], and we reduce its length to LaTeX: (b-a)/F_N. The ratio, LaTeX: g_n = F_(n-1)/F_n, is the key to the placements.

Here is the method for the continuous case:

  1. Initialization. Let LaTeX: x = a + (1 - g_N)(b-a) and LaTeX: y = a + g_N(b-a). Evaluate LaTeX: f(x) and LaTeX: f(y) and set LaTeX: n=N.
  2. Iteration. If LaTeX: f(x) < f(y), reduce the interval to LaTeX: (x, b] (i.e., set LaTeX: a=x), decrement LaTeX: n to LaTeX: n-1, and set LaTeX: x = y and LaTeX: y = a + g_n(b-a). If LaTeX: f(x) \ge f(y), reduce the interval to LaTeX: [a, y) (i.e., set LaTeX: b=y), decrement LaTeX: n to LaTeX: n-1, and set LaTeX: y = x and LaTeX: x = a + (1-g_n)(b-a).

The fibonacci search method minimizes the maximum number of evaluations needed to reduce the interval of uncertainty to within the prescribed length. For example, it reduces the length of a unit interval LaTeX: [0,1] to 1/10946 = 0.00009136 with only 20 evaluations. In the case of a finite set, fibonacci search finds the maximum value of a unimodal function on 10,946 points with only 20 evaluations, but this can be improved – see lattice search.

For very large LaTeX: N, the placement ratio LaTeX: (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 LaTeX: N is the number of evaluations needed to reduce length of the interval of uncertainty to LaTeX: 1/F_N. For example, with 20 evaluations dichotomous search reduces the interval of uncertainty to LaTeX: 0.0009765 of its original length (with separation value near LaTeX: 0). The most reduction comes from fibonacci search, which is more than an order of magnitude better, at LaTeX: 0.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         0.125            0.25            0.146
       10         0.0112           0.0312          0.0131
       15         0.00101          0.00781         0.00118
       20         0.0000914        0.000976        0.000107 
       25         0.00000824       0.0002441       0.0000096 
    ========================================================================
      


Fibonacci sequence

The numbers satisfying: LaTeX: F_{n+2} = F_{n+1} + F_n, with initial conditions LaTeX: F_0 = F_1 = 1. As shown in the following table, the fibonacci sequence grows rapidly after LaTeX: N=10, and LaTeX: F_N becomes astronomical for LaTeX: N > 50,

         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
      ==============     

Named after the 13th century mathematician who discovered it, this sequence has many interesting properties, notably for an optimal univariate optimization strategy, called fibonacci search.


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:

LaTeX:  
\left[ \begin{array}{ccc}
</p>
<ul><li> & 0 & 0 \\ * & * & 0 \\ * & * & *
</li></ul>
<p>\end{array} \right]
=
\left[ \begin{array}{ccc}
</p>
<ul><li> & 0 & 0 \\ * & 1 & 0 \\ * & 0 & 1
</li></ul>
<p>\end{array} \right]
\left[ \begin{array}{ccc}
1 & 0 & 0 \\ 0 & * & 0 \\ 0 & * & 1
\end{array} \right]
\left[ \begin{array}{ccc}
1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & *
\end{array} \right]

On the other hand, a lower triangular matrix could cause fill-in for some other factorization, such as the Cholesky factorization. A completely dense matrix also has no fill-in since there were no zeroes to begin with. Here is an example of fill-in, taking the original order of rows and columns in the product form:

LaTeX: 
\left[ \begin{array}{ccc}
</p>
<ul><li> & 0 & * \\ * & * & 0 \\ * & * & *
</li></ul>
<p>\end{array} \right]
=
\left[ \begin{array}{ccc}
</p>
<ul><li> & 0 & 0 \\ * & 1 & 0 \\ * & 0 & 1
</li></ul>
<p>\end{array} \right]
\left[ \begin{array}{ccc}
1 & 0 & 0 \\ 0 & * & 0 \\ 0 & * & 1
\end{array} \right]
\left[ \begin{array}{ccc}
1 & 0 & * \\ 0 & 1 & \# \\ 0 & 0 & *
\end{array} \right],

where LaTeX: \# is fill-in.


First-order conditions

This descends from classical optimization, using Taylor's Theorem. For unconstrained optimization, this is simply that LaTeX: \nabla 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 LaTeX: C, regardless of the level as long as the level is positive; otherwise the fixed charge is zero. This is represented by LaTeX: Cv, where LaTeX: v is a binary variable. If LaTeX: v=0, the fixed charge is 0; if LaTeX: v=1, the fixed charge is LaTeX: C. An example is whether to open a plant LaTeX: (v=1) or not LaTeX: (v=0). To apply this fixed charge to the non-negative variable LaTeX: x, the constraint LaTeX: x \le Mv is added to the mathematical program, where LaTeX: M is a very large value, known to exceed any feasible value of LaTeX: x. Then, if LaTeX: v=0 (e.g., not opening the plant that is needed for LaTeX: x > 0), LaTeX: x=0 is forced by the upper bound constraint. If LaTeX: v=1 (e.g., plant is open), LaTeX: x \le Mv is a redundant upper bound. Fixed charge problems are mathematical programs with fixed charges. (See Myths and Counterexamples in Mathematical Programming to avoid a misconception.)


Fixed point

The fixed point of a function, LaTeX: f:X \rightarrow X, is an element LaTeX: x \in X such that LaTeX: f(x)=x. Of a point-to-set map, LaTeX: F:X \rightarrow 2^X, we instead have that LaTeX: x \in F(x). The study of fixed points has been at the foundation of algorithms. Moreover, forcing substructure.


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:

LaTeX: 
\min c^T x : a \ge Ax \ge b, \; x_j \in \{0,1,...,N_j\},

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


Floor

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

LaTeX: \mbox{Floor}(x) = \max \{z: z \in \mathbb{Z}, \; z \le x\}.

Examples: LaTeX: \mbox{Floor}(5)=5, LaTeX: \mbox{Floor}(4.999)=4, LaTeX: \mbox{Floor}(-1.2) = -2. Also, see ceiling.


Flow augmenting path

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

LaTeX: f(x, y) \lt U(x, y)

along all forward arcs, and

LaTeX: f(x, y) \ge L(x, y)

along all backward arcs.

The flow, LaTeX: f<, is a maximum flow from the source to the sink if and only if there is no flow augmenting path relative to LaTeX: f. If there is a flow augmenting path, it can be changed along the path such that total flow increases (by at least 1 if all data are integer).


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.

LaTeX: 
\begin{array}{rcl}
-x -y & = & 0 \\
y - z & = & 0 \\
y & \ge & 0 \\
z & \ge & 0.      
\end{array}


Forward checking

Forward checking is a propagation procedure that guarantees that at each step of the search, all the constraints between already assigned variables and not yet assigned variables are arc consistent.

Formally, let LaTeX:  N = (X, D, C) be a binary constraint network and LaTeX:  Y \subseteq X such that LaTeX:  |D(x_i)| = 1 for all LaTeX:  x_i \in Y. LaTeX: N is forward checking consistent according to the instantiation LaTeX: I on LaTeX: Y iff LaTeX: I is locally consistent and for all LaTeX: x_i \in Y, for all LaTeX: x_j \in X \setminus Y, for all LaTeX: c(x_i, x_j) \in C, LaTeX: c(x_i, x_j) is arc consistent.


Forward substitution

The recursion to solve a nonsingular lower triangular system, LaTeX: Lx=b. It starts with LaTeX: x_1 = b_1 / L_{1,1}, then

LaTeX: 
x_j = \left( b_j - \sum_{i < j} L_{i, j} x_i \right) / L_{j,j}.

for LaTeX: j=2,...,n.


Forward transformation

See FTRAN.


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.


Fractional program

Objective and/or constraint functions are sums of ratios of the form LaTeX: V(x)/D(x), where typically LaTeX: D(x) > 0 over some domain LaTeX: X. The case of one term is special, and the linear fractional program has affine numerator and denominator. The linear 1-term case, LaTeX: (ax+b)/(cx+b) (where LaTeX: cx+b > 0 over the feasible region), is equivalent to solving a parametric linear program:

LaTeX: 
\mbox{opt } (ax+b) - u(cx+b) : x \in X,
where LaTeX: u is the parameter.


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 LaTeX: X is a nonempty polyhedron. Then, if there exists LaTeX: L such that LaTeX: f(x) \ge L for all LaTeX: x \in X, there exists LaTeX: x^* \in X such that LaTeX: f(x^*) \le f(x) for all LaTeX: x \in X.


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 LaTeX: x^* is in LaTeX: \arg\!\max\{f(x): x \in \mathbb{R}^n, \; g(x) \le 0\}, where LaTeX: f and LaTeX: g are in smooth. Then, there exists multipliers LaTeX: (y_0, y) \ge 0, not all zero, such that

LaTeX: 
y_0 \nabla f(x) - y^T \nabla g(x) = 0 \mbox{ and } y^Tg(x) = 0.


Fuzzy CSP

In a fuzzy constraint satisfaction problem each constraint LaTeX: C and instantiation LaTeX: I is assigned a degree of satisfaction LaTeX: sat(C,I), which is a value in the [0,1] real interval indicating the degree that LaTeX: C is satisfied by LaTeX: I. If this value is 1, LaTeX: C is satisfied and if this value is 0, LaTeX: C is violated. In the most common interpretation of fuzzy CSPs, the task is to find an instantiation LaTeX: I for which the minimum of LaTeX: sat(C,I) with LaTeX: C ranging over all the constraints (i.e. the smallest degree of satisfaction for the instantition LaTeX: I) is maximal.


Fuzzy math program

Some (or all) constraints are fuzzified by replacing the level set, LaTeX: G_i = \{x \in X : g_i(x) \le 0\}, with the requirement that LaTeX: u_G_i(x) \ge a_i, where LaTeX: u_G_i is a membership function that is given (or derived from primitive membership functions on the level sets of each LaTeX: g_i, and LaTeX: a_i is a parameter in LaTeX: [0,1] to be set for each instance of the model. Typically (but not necessarily), LaTeX: a_i = 1 means that the constraint must hold, and the lower the value of LaTeX: a_i, the more LaTeX: 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, LaTeX: u_S(x) \ge u_T(x) could mean that it is preferred that LaTeX: x be in LaTeX: S at least as much as it is preferred that LaTeX: x be in LaTeX: T.


Fuzzy set

Given a universe set, LaTeX: X, and a membership function, LaTeX: u : X \rightarrow [0,1], a fuzzy set is a collection of pairs: LaTeX: \{(x, u(x)): x \in X\}. Often, the membership function is subscripted by the set name, say LaTeX: u_S. Generally, for all LaTeX: x \in X, LaTeX: u_{X}(x)=1, and LaTeX: u_{\emptyset}(x)=0. In the context of uncertainty, the value LaTeX: u_{S}(x) is used to model the statement of how possible it is for LaTeX: x to be in LaTeX: S. For this reason, LaTeX: u_S is sometimes called the possibility function of LaTeX: 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 LaTeX: S and LaTeX: T, with membership functions LaTeX: u_S and LaTeX: u_T, resp., are defined by the following:

  • Union: LaTeX: u_{S\vee T}(x) = \max \{u_S(x), u_T(x)\}.
  • Intersection: LaTeX: u_{S\wedge T}(x) = \min \{ u_S(x), u_T(x)\}.
  • Complement: LaTeX: 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 LaTeX: u_S(x) = 1/2, its complement is also LaTeX: 1/2. Thus, LaTeX: u_{S\vee \sim S}(x) = 1/2, despite the fact that LaTeX: S\vee \sim S = X (in ordinary set theory). Similarly, LaTeX: u_{S\wedge \sim S}(x) = 1/2, despite the fact that LaTeX: S\wedge \sim S = \emptyset. This illustrates the fact that LaTeX: u_S need not equal LaTeX: u_T even if LaTeX: 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.


Views
Personal tools