KKTnõudeid

KKTnõudeid, also known as Karush-Kuhn-Tucker conditions, are a set of first-order necessary conditions for a solution in mathematical optimization to be optimal, provided that the constraint qualification holds. They are a generalization of Lagrange multipliers for problems with inequality constraints.

The KKT conditions apply to constrained optimization problems of the form: minimize f(x) subject to g_i(x) <= 0 for i = 1, ..., m, and h_j(x) = 0 for j = 1, ..., p. The conditions involve introducing Lagrange multipliers for both equality and inequality constraints.

For a problem with only inequality constraints, the KKT conditions state that if x* is a local minimum, then there exist multipliers mu_i >= 0 such that the Lagrangian L(x, mu) = f(x) + sum(mu_i * g_i(x)) is minimized at x*, and the gradient of the Lagrangian with respect to x is zero at x*. Additionally, for each i, either g_i(x*) = 0 (the constraint is active) or mu_i = 0 (the constraint is inactive), a condition known as complementary slackness.

When equality constraints are also present, additional multipliers lambda_j are introduced, and the gradient of the Lagrangian L(x, mu, lambda) = f(x) + sum(mu_i * g_i(x)) + sum(lambda_j * h_j(x)) with respect to x must be zero. The non-negativity of mu_i and the complementary slackness conditions remain for the inequality constraints, while the equality constraints must be satisfied.

The KKT conditions are a fundamental tool in nonlinear programming. If the objective function is convex and the constraints define a convex set, then the KKT conditions are also sufficient for optimality. In general, they are only necessary conditions, meaning that a point satisfying them is not guaranteed to be optimal unless additional conditions, such as convexity, are met.