Kelley's Cutting Plane Method solves convex programming problems by iteratively refining a polyhedral approximation of the feasible region. The algorithm: (1) starts with an initial linear approximation; (2) solves the LP relaxation; (3) if the solution is feasible for the original problem, it's optimal; (4) otherwise, adds a cutting plane (linear constraint) that separates the current solution from the feasible region; (5) repeats until convergence. The method is particularly effective for problems with complicated convex constraints that can be separated. Modern variants include bundle methods and level methods used in large-scale optimization.

The KKT conditions are necessary conditions for optimality in nonlinear programming with inequality and equality constraints. For problem: min f(x) subject to g(x) ≤ 0, h(x) = 0, at optimal point x*: (1) Stationarity: ∇f(x*) + Σλᵢ∇gᵢ(x*) + Σμⱼ∇hⱼ(x*) = 0; (2) Primal feasibility: g(x*) ≤ 0, h(x*) = 0; (3) Dual feasibility: λᵢ ≥ 0; (4) Complementary slackness: λᵢgᵢ(x*) = 0. Under constraint qualification (LICQ, MFCQ), KKT conditions are necessary. For convex problems, they are also sufficient. The multipliers λᵢ, μⱼ represent shadow prices. KKT conditions generalize Lagrange multipliers to inequality constraints and are fundamental to nonlinear optimization theory and algorithms.

The Knapsack Problem is a classic combinatorial optimization problem: given n items with weights wᵢ and values vᵢ, and a knapsack with capacity W, select items to maximize total value without exceeding capacity. Formally: maximize Σvᵢxᵢ subject to Σwᵢxᵢ ≤ W, where xᵢ ∈ {0,1}. Variants include: 0/1 knapsack (items cannot be divided), fractional knapsack (items can be divided), multiple knapsack, and multidimensional knapsack. Solution methods include dynamic programming, branch and bound, and greedy algorithms (for fractional version).