The optimality conditions for a constrained local optimum are called the Karush Kuhn Tucker (KKT) conditions and they play an important role in constrained optimization theory and algorithm development. The KKT conditions for optimality are a set of necessary conditions for a solution to be optimal in a mathematical optimization problem. They are necessary and sufficient conditions for a local minimum in nonlinear programming problems. The KKT conditions consist of the following elements:

For an optimization problem:

$$\min_x f(x)$$ $$\mathrm{subject\;to}\quad g_i(x)-b_i \ge 0 \quad i=1,\ldots,k$$ $$\quad\quad\quad\quad\quad g_i(x)-b_i = 0 \quad i=k+1,\ldots,m$$

There are four KKT conditions for optimal primal `(x)` and dual `(\lambda)` variables. The asterisk (*) denotes optimal values.

1. Primal Feasibility: All constraints must be satisfied.

$$g_i(x^*)-b_i \mathrm{\;is\;feasible}$$

2. No Feasible Descent: No possible objective improvement at the solution.

$$\nabla f(x^*)-\sum_{i=1}^m \lambda_i^* \nabla g_i\left(x^*\right)=0$$

3. Complementarity: The product of the Lagrange multipliers and the corresponding variables must be zero.

$$\lambda_i^* \left( g_i(x^*)-b_i \right) = 0$$

4. Dual Feasibility: The Lagrange multipliers associated with constraints have to be non-negative (zero or positive).

$$\lambda_i^* \ge 0$$

The feasibility condition (1) applies to both equality and inequality constraints and is simply a statement that the constraints must not be violated at optimal conditions. The gradient condition (2) ensures that there is no feasible direction that could potentially improve the objective function. The last two conditions (3 and 4) are only required with inequality constraints and enforce a positive Lagrange multiplier when the constraint is active (=0) and a zero Lagrange multiplier when the constraint is inactive (>0).

• Karush-Kuhn-Tucker and Lagrange Multiplier Homework

Part 1: Tutorial on the KKT Conditions

This 5 minute introductory video reviews the 4 KKT conditions and applies them to solve a simple quadratic programming (QP) problem with:

• 1 Quadratic objective function
• 2 Linear equality constraints
• 3 Variables (x₁, x₂, x₃)

Download the following worksheet on KKT conditions. The video below reviews the solution to this worksheet.

• KKT Conditions Worksheet 1
• KKT Conditions Worksheet 1 Solution

Part 2: KKT Conditions with Inequality Constraints

This next 5 minute introductory is similar to the previous one but solves a problem with inequality constraints instead of equality constraints. The problem is a simple quadratic programming (QP) problem with:

• 1 Quadratic objective function
• 2 Linear inequality constraints
• 3 Variables (x₁, x₂, x₃)

Download the following worksheet on KKT conditions with inequality constraints. The video below reviews the solution to this worksheet.

• KKT Conditions Worksheet 2
• KKT Conditions Worksheet 2 Solution

Part 3: KKT Exercise with both Inequality and Equality Constraints

This 5 minute exercise is similar to the previous ones but solves a problem with both equality and inequality constraints.

Download the following worksheet on KKT conditions with inequality and equality constraints. The video below reviews the solution to this worksheet.

• KKT Conditions Worksheet 3
• KKT Conditions Worksheet 3 Solution

Part 4: Application Exercise for the Optimal Volume of a Tank

This 5 minute exercise covers an application to a tank volume optimization. In this case, we specify the final Lagrange multiplier of $8/ft³.

Download the following worksheet on this application of the KKT conditions. The video below reviews the solution to this worksheet.

• KKT Conditions Worksheet 4
• KKT Conditions Worksheet 4 Solution

Part 5: KKT Conditions for Dynamic Optimization

This assignment can be completed in groups of two. Additional guidelines on individual, collaborative, and group assignments are provided under the Expectations link.

Generative AI Learning

Use these prompts to test your understanding after working the KKT worksheets. Direct the AI - it may check and question, but write the KKT conditions by hand yourself; that skill is the point.

Discussion Questions

1. A classmate says "the Lagrange multipliers are just bookkeeping variables with no physical meaning." Use the tank volume application on this page to argue the opposite: what are the units of a multiplier there, and what design decision could its value drive?
2. For a problem with 3 inequality constraints, the case-by-case KKT analysis has up to 8 active-set combinations. Solvers cannot enumerate 2^100 cases for 100 constraints - so what do SQP and interior point methods each do instead?
3. Why can a point satisfy all KKT conditions and still be a local maximum or saddle? What extra information (second-order condition, or convexity of the problem) settles it?
4. If an optimizer returns a solution where an inequality constraint is active but its multiplier is essentially zero, what does that degenerate case tell you about the problem - would relaxing that constraint help?

What to Turn In

Submit a short report (PDF, 1-2 pages) that curates your results into a demonstration of what you learned. You may use Generative AI to help write the report, but the derivations and case analyses must be your own. Answer these questions:

1. For one assigned problem, show the full KKT analysis: Lagrangian, the cases you enumerated, why you discarded the failing cases, and the optimum with its multipliers.
2. From the grader prompt: did the AI's verification pass your solution? If not, which condition failed, and what was your fix?
3. Interpret each nonzero multiplier at your optimum as a shadow price with units. Which constraint is most valuable to relax, and by how much would the objective improve per unit?
4. Verify your hand optimum numerically (GEKKO or scipy) and compare the solver's multipliers with yours.
5. From the quiz prompt: one question you missed and the corrected answer.