Haar condition. See randomized program.

Hadamard inequality. det(A) <= ||A_.1|| ... ||A_.n||, where A is n x n and the norms are L_2.

Half-line. {th: t >= 0}, where h is in R^n such that h not= 0 (some state ||h||=1, without loss in generality). Note the half-line is rooted at the origin -- see ray for translation.

Halfspace. Consider the hyperplane, {x in R^n: a'x = b} (where a is in R^n\{0}). This partitions R^n into two (closed) half spaces: {x: a'x <= b} and {x: a'x >= b}. The two associated open halfspaces are {x: a'x < b} and {x: a'x > b}.

Hausdorff metric. This metric arises in normed spaces, giving a measure of distance between two (point) sets, S and T. Given a norm, let d be the distance function between a point and a set:

d(x, T) = inf{||x-y||: y in T} and d(S, y) = inf{||x-y||: x in S}.

D(S, T) = sup{d(x, T): x in S} and D(T, S) = sup{d(S, y): y in T}.

h(S, T) = max{D(S, T), D(T, S)} = max{1, 2} = 2.

Hessenberg matrix. An upper Hessenberg matrix is a square matrix with A(i, j)=0 for i > j+1. A lower Hessenberg matrix is one whose transpose is upper Hessenberg.

Hessian. The matrix of second partial derivatives of a function (assumed to be twice differentiable). This is often denoted H_f(x), where f is the function and x is a point in its domain.

Heuristic. In mathematical programming, this usually means a procedure that seeks an optimal solution but does not guarantee it will find one, even if one exists. It is often used in contrast to an algorithm, so branch and bound would not be considered a heuristic in this sense. In AI, however, a heuristic is an algorithm (with some guarantees) that uses a heuristic function to estimate the "cost" of branching from a given node to a leaf of the search tree. (Also, in AI, the usual rules of node selection in branch and bound can be determined by the choice of heuristic function: best-first, breadth-first, or depth-first search.)

Heuristic function. This is used to guide the search, as a human would do. In this sense, it is a rule of thumb. Formally, in AI, a heuristic function is defined on the state of a search tree and is used in the evaluation of nodes for expansion in what is sometimes called a best-first directed tree search strategy.

Heuristic search. In mathematical programming, this is any (purposeful) search procedure to seek a solution to a global optimization problem, notably to combinatorial programs. In AI, this is a (partially) informed search (vs. blind search), using a heuristic function for guidance.

Two types of (blind) search methods are:

1. Breadth-first: expanding a node of least depth;
2. Depth-first: expanding a node of greatest depth (requiring backtracking).

A specific class of local heuristic search algorithms is the greedy algorithm. Another type is the n-Opt for the TSP.

Here are heuristic search strategies that are based on some biological metaphor:

1. Ant colony optimization, based on how ants solve problems;
2. Genetic algorithm, based on genetics and evolution;
3. Neural networks, based on how the brain functions;
4. Simulated annealing, based on thermodynamics;
5. Tabu search, based on memory-response;
6. Target analysis, based on learning.

Hirsch conjecture. If the basis of one basic feasible solution differs from another by k columns, there exists k feasible pivots to go from the first to the second. This was eventually shown to be false for general polyhedra and is an open problem for bounded polyhedra. It was posed by Warren M. Hirsch in 1957.

Hölder's inequality. ||x y||_1 <= ||x||_p ||y||_q, where ||.||_k denotes the L_k norm, p > 1, and 1/p + 1/q = 1. Equality holds if, and only if, |x|^p = a|y|^q for some scalar, a. (Note: this is the Cauchy-Schwartz inequality if p = q = 2.)

Homogeneous function. Of degree p: f(ax) = (a^p)f(x) for all a. It is positively homogeneous if we restrict a > 0. When the degree is not specified (even by context), it is generally assumed to be 1. For example, x is homogeneous, xy + x² is homogeneous of degree 2, x + x² is not homogeneous, and xy/(x+y) is positively homogeneous on R²++.

Homotopy. A continuous transformation from one mapping to another. One example is the convex combination: tf(x) + (1-t)F(x). As t varies from 0 to 1, the function changes continuously from F to f.

Hungarian method. An algorithm to solve the standard assignment problem (presented by H. Kuhn in 1955). Let C be the n×n cost matrix.

    
                         Job 
                    _ 1  2  3  4  5 _ 
                   |                 | 
                   |  1  2  3  4  7  | 1
                   |  7  4  2  6  5  | 2
               C = |  2  4  3  1  4  | 3
                   |  2  3  1  2  3  | 4
                   |  5  4  3  2  4  | 5
                   |_               _| 

    
                    _ 1  2  3  4  5 _ 
                   |                 | 
                   |  0  1  2  3  6  | 1
                   |  5  2  0  4  3  | 2
                   |  1  3  2  0  3  | 3
                   |  1  2  0  1  2  | 4
                   |  3  2  1  0  2  | 5
                   |_               _| 

    
                    _ 1  2  3  4  5 _ 
                   |        |  |  |  | 
                   |--0--0--2--3--5--| 1
                   |  5  1  0  4  1  | 2
                   |  1  2  2  0  1  | 3
                   |  1  1  0  1  0  | 4
                   |  3  1  1  0  0  | 5
                   |_       |  |  | _| 

    
                    _ 1  2  3  4  5 _ 
                   |                 | 
                   |  0* 0  4  5  7  | 1
                   |  4  0* 0  4  1  | 2
                   |  0  2  2  0* 1  | 3
                   |  0  0  0* 1  0  | 4
                   |  2  0  1  0  0* | 5
                   |_               _|