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 kth 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.