All Pages

From Glossary

Jump to: navigation, search


A consistency notion in constraint programming.

Let LaTeX: P = (X, D, C) be a CSP.

  • Given a set of variables LaTeX: Y \subseteq X with LaTeX: |Y| = k -1 , a locally consistent instantiation LaTeX: I on LaTeX: Y is k-consistent iff for any kth variable LaTeX: x_{i_{k}} \in X \setminus Y there exists a value LaTeX: v_{i_{k}} \in D(x_{i_{k}}) such that LaTeX: I \cap \{ (x_{i_k}, v_{i_k}) \} is locally consistent.
  • The CSP LaTeX: P is k-consistent iff for any set LaTeX: Y of LaTeX: k-1 variables, any locally consistent instantiation on LaTeX: Y is k-consistent.

For example, 3-consistency ensures that any instantiation any pair of variables can be extended to an instantiation involving any third variable without violating any constraint. It is equivalent to path consistency. Similarly, 2-consistency is also known as arc consistency.


See n-Opt.

Kantorovich inequality

Let LaTeX: Q be a symmetric, positive definite matrix, with eigenvalues in LaTeX: [a,b], and let LaTeX: x \in \mathbb{R}^n. Then,

\frac{\| x \|^2}{(x^T Q x)(x^T Q^{-1}x)} \le \frac{4 \, a \, b}{(a+b)^2}.

Its significance in mathematical programming is in convergence analysis: it bounds the convergence rate of Cauchy's steepest ascent.

Karmarkar algorithm

An interior point method for linear programming, which began a series of variations (e.g., see affine scaling). The original algorithm applies to the system LaTeX: Ax=0, for LaTeX: x \in S_n, i.e. x is an element of the n-dim. simplex, and assumes LaTeX: Ae=0 (so LaTeX: e/n is a feasible solution). It further assumes the optimal objective value is known to be zero. (All of these assumptions have been relaxed in subsequent developments.)

Here are the basic steps of Karmarkar's (original) algorithm, given LaTeX: x > 0, LaTeX: e^T x=1 and LaTeX: Ax=0.

  1. Form LaTeX: D = \mbox{diag}(x_j) and
B = \begin{bmatrix} AD \\ e \end{bmatrix}
    (assume LaTeX: \mbox{rank}(B)=m+1).
  2. Project: Project LaTeX: Dc to null space of LaTeX: B: LaTeX: c* = [I-B^T(BB^T)^{-1}B]Dc.
  3. Normalize Normalize the ascent direction: LaTeX: d = c* /(\|c*\| \sqrt{n(n-1)}. If c*=0, terminate since the solution is optimal.)
  4. Move Move in projected space to LaTeX: y = e/n - sd, where LaTeX: s is a fixed step size (= 1/4).
  5. Project Project back into x-space: LaTeX: x = Dy /(e^TDy).
The time complexity is LaTeX: O(n^{3.5}L^2 \ln(L)\ln(\ln(L))), where LaTeX: L is a measure of data storage for a given precision. The solution obtained is in the relative interior of the set of optimal solutions.

Kernel of basis

See basis.

Klee-Minty polytope

This is an example to show that the elementary simplex method does not have polynomial time complexity. The polytope is

\left\{ x : 
\left(\sum_{i=1}^{k-1} 2^{k-i+1} x_i \right) + x_k \le 5^k, 
<pre>               \; \mbox{ for } k = 1, 2, \ldots, n, \; x \ge 0 \right\}


\sum_{i=1}^n 2^{n-i} x_i

over this polytope shows the exponential complexity.

Knapsack problem

An integer program of the form,

LaTeX: \max \{c^Tx : x \in \mathbb{Z}^n, \, x \ge 0,\, \mbox{ and } a^Tx \le b \},

where LaTeX: a > 0. The original problem models the maximum value of a knapsack that is limited by volume or weight LaTeX: (b), where LaTeX: x_j is the number of items of type LaTeX: j put into the knapsack at unit return LaTeX: c_j, that uses LaTeX: a_j units per item.

The group knapsack problem has this form, except that it pertains to Gomory's corner polyhedron problem for general integer programming.

The multi-dimensional knapsack problem has more constraints (e.g., volume and weight), LaTeX: Ax <= b, where LaTeX: A >= 0 with LaTeX: Ae > 0 and LaTeX: e^TA > 0.

Kuhn-Tucker conditions

Abbreviated KT and KKT (latter credits Karush, who had the conditions in his earlier thesis).

This is the Lagrange Multiplier Rule, which Kuhn and Tucker published as an extension to allow inequality constraints. They also introduced the notion of a constraint qualification (which had been only the linear independence condition stemming from Lagrange's multiplier theorem). The most important contribution that sets KT apart from similar discoveries is the connection with saddle points that led to Lagrangian duality.

Kuhn-Tucker point

Abbreviated KKT point. A feasible point that satisfies the Kuhn-Tucker conditions.

Personal tools