All Pages

From Glossary

K-consistency

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.

K-opt

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,

$LaTeX: \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$ .

Form $LaTeX: D = \mbox{diag}(x_j)$ and $LaTeX: B = \begin{bmatrix} AD \\ e \end{bmatrix}$ (assume $LaTeX: \mbox{rank}(B)=m+1$ ).
Project: Project $LaTeX: Dc$ to null space of $LaTeX: B$ : $LaTeX: c* = [I-B^T(BB^T)^{-1}B]Dc.$
Normalize Normalize the ascent direction: $LaTeX: d = c* /(\|c*\| \sqrt{n(n-1)}.$ If c*=0, terminate since the solution is optimal.)
Move Move in projected space to $LaTeX: y = e/n - sd$ , where $LaTeX: s$ is a fixed step size (= 1/4).
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

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

Maximizing

$LaTeX: \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.

Retrieved from "https://glossary.informs.org/ver2/mpgwiki/index.php?title=Special:StackAll"