KKT conditions
- PDF / 1,175,211 Bytes
- 5 Pages / 595.32 x 790.92 pts Page_size
- 51 Downloads / 227 Views
KKT CONDITIONS
An algorithm devied by N. Kannarkar for solving a
See Karush-Kuhn-Tucker conditions; Nonlinear programming; Quadratic programming.
linear-programming problem by generating a sequence of points that lie in the strict interior of the problem's solution space and that converges to an optimal solution. Kannarkar's algorithm, and its many variations, have been shown to be polynomialtime algorithms that solve large-scale linear-programming problems in a computationally efficient manner. See Interior point methods; Polynomial-time algorithm.
KARUSH-KUHN-TUCKER (KKT) CONDITIONS The Karush-Kuhn-Tucker (KKT) conditions are necessary conditions that a solution to a general nonlinear programming problem must satisfy, provided that the problem constraints satisfy a regularity condition called constraint qualification. If the problem is one in which the constraint set (i.e., solution space) is convex and the maximizing (minimizing) objective function is concave (convex), the KKT conditions are suffifient. Applied to a linear-programming problem, the KKT conditions yield the complementary slackness conditions of the primal and dual problems. See Nonlinear programming.
KLEE-MINTY PROBLEM The Klee-Minty problem is a linear-programming problem designed to demonstrate that a problem exists that would require the simplex algorithm to generate all extreme point solutions before finding the optimal. This problem demonstrated that, although the simplex algorithm (under a nondegeneracy assumption) would find an optimal solution in a finite number of iterations, the number of iterations can increase exponentially. Thus, the simplex method is not a polynomially bounded algorithm. One form of the Klee-Minty problem, which defines a slightly perturbed hypercube, is the following: Minimize
-
xd
subject to x 1
~
X1:::;
-£X 1 fX1
0 1
+ x2 ~ 0 + x2:::; 1
+ xd ~ 0 fXd-1 + xd:::; 1
-EXd-1
Xj ~
0
KENDALL'S NOTATION
with 0
ci, b) usually taken to be positive integers. The name is due to interpreting the problem as one in which a camper has a knapsack which can carry up to b pounds. The camper has a choice of packing up to n items, with xi = 1 if the item is packed and xi = 0 if the item is not packed. ltemj weighs ai pounds. Each item has a "value" ci to the camper if it is packed.
Data Loading...
