Karush–Kuhn–Tucker (KKT) Conditions

The Stationarity condition requires that the gradient of the Lagrangian function must be zero at the optimal point. This means the objective function's gradient is a linear combination of the gradients of the active constraints.

• Mathematical Form: ∇f(x*) + Σ λ_i ∇g_i(x*) + Σ μ_j ∇h_j(x*) = 0
• Interpretation: At the optimum, you cannot improve the objective by moving in any feasible direction without violating a constraint. The Lagrange multipliers (λ, μ) act as 'force vectors' balancing the objective's pull against the constraints.

Primal Feasibility ensures the candidate solution satisfies all the original constraints of the optimization problem. This is a fundamental requirement for any valid solution.

• For Inequality Constraints: g_i(x*) ≤ 0 for all i.
• For Equality Constraints: h_j(x*) = 0 for all j.
• Purpose: This condition guarantees the solution lies within the problem's defined feasible region. A point violating primal feasibility is not a candidate for an optimum, regardless of its objective value.

Dual Feasibility imposes sign restrictions on the Lagrange multipliers (λ) associated with inequality constraints. This condition is critical for the economic interpretation of the multipliers as shadow prices.

• Mathematical Form: λ_i ≥ 0 for all i (for constraints of the form g_i(x) ≤ 0).
• Interpretation: A non-negative λ_i indicates that relaxing the i-th inequality constraint (making it easier to satisfy) cannot worsen the optimal objective value. A multiplier of zero means the constraint is inactive (not binding) at the optimum.

Complementary Slackness is the condition that links primal feasibility and dual feasibility. It states that for each inequality constraint, either the constraint is tight (active) or its corresponding Lagrange multiplier is zero.

• Mathematical Form: λ_i * g_i(x*) = 0 for all i.
• Implication: This creates a binary relationship:
  • If g_i(x*) < 0 (constraint is inactive), then λ_i must be 0.
  • If λ_i > 0, then g_i(x*) must be 0 (constraint is active).
• This condition is what distinguishes handling inequalities from equalities.

A Constraint Qualification (CQ) is a regularity condition imposed on the constraints at the candidate point that ensures the KKT conditions are necessary for optimality. Without a valid CQ, a point may be optimal without satisfying the KKT conditions.

Common qualifications include:

• Linear Independence Constraint Qualification (LICQ): The gradients of all active constraints are linearly independent.
• Mangasarian-Fromovitz Constraint Qualification (MFCQ): A slightly weaker condition than LICQ.
• Slater's Condition: For convex problems, requires a strictly feasible point for all inequality constraints.

The Lagrangian Function is the scalar function constructed by augmenting the original objective with the constraints, weighted by their Lagrange multipliers. It is the central object from which the KKT conditions are derived.

• Definition: L(x, λ, μ) = f(x) + Σ λ_i g_i(x) + Σ μ_j h_j(x)
• Role: The stationarity condition is found by taking the gradient of L with respect to the primal variables (x) and setting it to zero. The multipliers (λ, μ) are the dual variables, and solving the KKT conditions often involves finding the saddle point of the Lagrangian.

Nonlinear Programming (NLP) is the mathematical discipline of optimizing an objective function subject to constraints, where the function or constraints are nonlinear. It is the foundational problem class for which the KKT conditions provide necessary optimality criteria.

• Core Problem: Minimize f(x) subject to g_i(x) ≤ 0 and h_j(x) = 0.
• Relation to KKT: The KKT conditions are the first-order necessary conditions for a local optimum in NLP, provided constraint qualifications hold.
• Robotics Application: Trajectory optimization is fundamentally an NLP problem, where the objective is to minimize energy or jerk, and constraints enforce dynamics, obstacle avoidance, and joint limits.

A Lagrange multiplier is a scalar variable used in optimization to incorporate a constraint into the objective function, forming the Lagrangian. In the KKT framework, a multiplier (λ or μ) is associated with each constraint.

• Role in KKT: The KKT conditions generalize the method of Lagrange multipliers to handle inequality constraints (g(x) ≤ 0).
• Complementary Slackness: For an inequality constraint, its multiplier must be non-negative (μ ≥ 0), and the product μ * g(x) = 0. This means inactive constraints (where g(x) < 0) have a multiplier of zero.
• Interpretation: The magnitude of the multiplier indicates the sensitivity of the optimal cost to a tightening of that constraint.

A constraint qualification (CQ) is a regularity condition imposed on the constraints of an optimization problem that ensures the KKT conditions are necessary for optimality. Without a valid CQ, a point may be optimal without satisfying KKT.

• Common CQs: The Linear Independence Constraint Qualification (LICQ) and the Mangasarian-Fromovitz Constraint Qualification (MFCQ).
• LICQ in Robotics: Requires that the gradients of all active constraints (both equality and binding inequalities) are linearly independent. This often holds for well-formulated trajectory problems but can fail at singular configurations.
• Practical Implication: Solvers assume a CQ holds; violation can lead to numerical failure or incorrect certification of optimality.

Sequential Quadratic Programming (SQP) is a powerful iterative method for solving nonlinear programming problems. It repeatedly solves quadratic programming (QP) subproblems that approximate the original NLP.

• Mechanism: Each iteration linearizes the constraints and approximates the Lagrangian's Hessian to form a QP. Solving this QP yields a search direction.
• Connection to KKT: Each QP subproblem's solution satisfies its own KKT conditions. The overall SQP algorithm converges to a point satisfying the KKT conditions for the original NLP.
• Industry Use: A workhorse algorithm in trajectory optimization solvers like SNOPT and IPOPT (which uses an interior-point variant).

In optimization, duality associates a primal problem (minimization) with a dual problem (maximization). The Lagrangian dual function is formed by minimizing the Lagrangian over the primal variables.

• Dual Problem: Maximize the dual function subject to dual constraints (multiplier non-negativity).
• KKT & Strong Duality: At the optimum, under constraint qualifications, the primal and dual optimal values coincide (strong duality). The optimal primal and dual variables together satisfy the KKT conditions.
• Application Insight: The dual variables (KKT multipliers) provide a certificate of optimality and valuable sensitivity analysis, showing how much the optimal cost would increase if a constraint were tightened.

Interior-point methods (IPMs) are a class of algorithms for solving convex and nonlinear optimization problems. They approach the optimum by traversing the interior of the feasible region, using a barrier function to handle inequalities.

• Barrier Function: Transforms inequality constraints g(x) ≤ 0 into a logarithmic penalty -μ * Σ log(-g_i(x)) added to the objective, where μ > 0 is a barrier parameter.
• Path to KKT: As μ → 0, the sequence of solutions to the barrier problems converges to a solution satisfying the original problem's KKT conditions.
• Robotics Relevance: IPOPT (Interior Point OPTimizer) is a widely used open-source solver for large-scale trajectory optimization problems, directly computing KKT points.