# All Pages

### From Glossary

K-consistency |

A consistency notion in constraint programming.

Let be a CSP.

- Given a set of variables with , a locally consistent instantiation on is
*k-consistent*iff for any*k*th variable there exists a value such that is locally consistent. - The CSP is
*k-consistent*iff for any set of variables, any locally consistent instantiation on 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 be a symmetric, positive definite matrix, with eigenvalues in , and let . Then,

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 , for , i.e. x is an element of the n-dim. simplex, and assumes (so 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 , and .

- Form and
*Project:*Project to null space of :*Normalize*Normalize the ascent direction: If c*=0, terminate since the solution is optimal.)*Move*Move in projected space to , where is a fixed step size (= 1/4).*Project*Project back into x-space: .

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

Maximizing

over this polytope shows the exponential complexity.

Knapsack problem |

An integer program of the form,

where . The original problem models the maximum value of a knapsack that is limited by volume or weight , where is the number of items of type put into the knapsack at unit return , that uses 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),
, where with and .

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.