Continuous Function

Optimization

Duality and KKT Conditions

KKT conditions turn constrained convex optimality into a checkable certificate: feasibility, nonnegative multipliers, complementary slackness, stationarity, and zero duality gap.

status: reviewimportance: criticaldifficulty 4/5math: graduateread: 18mlive demo
Back to OptimizationNext: SVM Margins and Kernels (review)

Concept Structure

Duality and KKT Conditions

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

2prerequisites
1next concepts
1related links

Learner Contract

What this page should let you do.

You are here becauseKKT conditions turn constrained convex optimality into a checkable certificate: feasibility, nonnegative multipliers, complementary slackness, stationarity, and zero duality gap.

This Optimization concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Test the linkManipulate one control and predict the visible change.Then continue to SVM Margins and Kernels (review)

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.
Claims1/1 reviewed
Sources3 cited
Codeattached
Demolive
Reviewed2026-07-02
Updatedpage 2026-07-02

Learning item flow

4/4 sections readyAsk about thisResearch room
ConceptDuality and KKT ConditionsOptimizationEquationDuality and KKT Conditions equation 1Exact equationCodeDuality and KKT Conditions runnable code 1Exact runnable codeDemoDuality and KKT Conditions interactive demoInteractive demoClaimFor differentiable convex problems under strong-duality conditions, K...Exact claim checkSourceConvex OptimizationExact source
ConceptDuality and KKT ConditionsOptimization
3 sources attachedLocal snapshot ready
concept:optimization/duality-kkt-conditions
CodenearbyPredictbefore revealRoomitem handoff
01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.
01

01

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

KKT conditions are often presented like a checklist. That is technically useful, but pedagogically backwards.

The real idea is a certificate. A constrained optimum should come with evidence that no feasible move can do better. In convex optimization, duality gives that evidence as a lower bound on the best possible primal value. If the lower bound meets the value of a feasible point, the point is optimal.

The KKT conditions are the local shape of that certificate:

  • primal feasibility says the proposed point obeys the original constraints;
  • dual feasibility says inequality multipliers are nonnegative prices;
  • complementary slackness says a constraint gets a positive price only when it is tight;
  • stationarity says the objective gradient is balanced by priced constraint normals.

Think of a ball rolling downhill until it hits a wall. If the wall is not touched, its contact force is zero. If the wall is touched, the contact force can be positive. KKT writes that story in symbols.

The lab uses one problem all the way through: move a target point to the closest point inside a half-plane. When the target is already feasible, the constraint is quiet and λ⋆=0\lambda^\star=0. When the target lies outside, the boundary becomes active, the multiplier is positive, and the primal value equals the best dual lower bound.

02

02

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt
Equation 1min⁡xf0(x)subject togi(x)≤0, i=1,…,m,hj(x)=0, j=1,…,p.\min_x f_0(x) \quad\text{subject to}\quad g_i(x)\le 0,\ i=1,\ldots,m, \qquad h_j(x)=0,\ j=1,\ldots,p.Equation 2L(x,λ,ν)=f0(x)+∑i=1mλigi(x)+∑j=1pνjhj(x),λi≥0.\mathcal L(x,\lambda,\nu) = f_0(x)+\sum_{i=1}^m \lambda_i g_i(x)+\sum_{j=1}^p \nu_j h_j(x), \qquad \lambda_i\ge 0.

Start with a differentiable constrained problem in standard form:

min⁡xf0(x)subject togi(x)≤0, i=1,…,m,hj(x)=0, j=1,…,p.\min_x f_0(x) \quad\text{subject to}\quad g_i(x)\le 0,\ i=1,\ldots,m, \qquad h_j(x)=0,\ j=1,\ldots,p.

The Lagrangian is

L(x,λ,ν)=f0(x)+∑i=1mλigi(x)+∑j=1pνjhj(x),λi≥0.\mathcal L(x,\lambda,\nu) = f_0(x)+\sum_{i=1}^m \lambda_i g_i(x)+\sum_{j=1}^p \nu_j h_j(x), \qquad \lambda_i\ge 0.

The dual function minimizes the Lagrangian over the primal variable:

d(λ,ν)=inf⁡xL(x,λ,ν).d(\lambda,\nu)=\inf_x \mathcal L(x,\lambda,\nu).

For every dual feasible (λ,ν)(\lambda,\nu), weak duality gives

d(λ,ν)≤p⋆,d(\lambda,\nu)\le p^\star,

where p⋆p^\star is the primal optimum. So d(λ,ν)d(\lambda,\nu) is a lower-bound certificate. The duality gap for a feasible xx is

f0(x)−d(λ,ν).f_0(x)-d(\lambda,\nu).

When the problem is convex and the usual strong-duality conditions hold, a zero gap certificate is possible. For differentiable convex problems, the KKT conditions are sufficient for optimality:

gi(x⋆)≤0,primal feasibilityhj(x⋆)=0,primal feasibilityλi⋆≥0,dual feasibilityλi⋆gi(x⋆)=0,complementary slackness∇f0(x⋆)+∑i=1mλi⋆∇gi(x⋆)+∑j=1pνj⋆∇hj(x⋆)=0,stationarity.\begin{aligned} g_i(x^\star)&\le 0, &&\text{primal feasibility}\\ h_j(x^\star)&=0, &&\text{primal feasibility}\\ \lambda_i^\star&\ge 0, &&\text{dual feasibility}\\ \lambda_i^\star g_i(x^\star)&=0, &&\text{complementary slackness}\\ \nabla f_0(x^\star) +\sum_{i=1}^m\lambda_i^\star\nabla g_i(x^\star) +\sum_{j=1}^p\nu_j^\star\nabla h_j(x^\star)&=0, &&\text{stationarity.} \end{aligned}

Now specialize to the demo. Let c∈R2c\in\mathbb R^2 be a target point and solve

min⁡x12∥x−c∥22subject tog(x)=a⊤x−b≤0,\min_x \frac12\|x-c\|_2^2 \quad\text{subject to}\quad g(x)=a^\top x-b\le 0,

where a=(1,1)⊤a=(1,1)^\top and b=1b=1. The feasible set is the half-plane below the line x1+x2=1x_1+x_2=1.

The Lagrangian is

L(x,λ)=12∥x−c∥22+λ(a⊤x−b),λ≥0.\mathcal L(x,\lambda)=\frac12\|x-c\|_2^2+\lambda(a^\top x-b), \qquad \lambda\ge 0.

Stationarity gives

∇xL(x,λ)=x−c+λa=0,x(λ)=c−λa.\nabla_x\mathcal L(x,\lambda)=x-c+\lambda a=0, \qquad x(\lambda)=c-\lambda a.

Substitute this minimizer into the Lagrangian. If v=a⊤c−bv=a^\top c-b and A=a⊤aA=a^\top a, the dual function is

d(λ)=λv−12λ2A,λ≥0.d(\lambda)=\lambda v-\frac12\lambda^2 A, \qquad \lambda\ge 0.

Maximizing this concave parabola over λ≥0\lambda\ge 0 gives

λ⋆=max⁡(0,a⊤c−ba⊤a),x⋆=c−λ⋆a.\lambda^\star=\max\left(0,\frac{a^\top c-b}{a^\top a}\right), \qquad x^\star=c-\lambda^\star a.

If the target is feasible, a⊤c−b≤0a^\top c-b\le 0, then λ⋆=0\lambda^\star=0 and x⋆=cx^\star=c. If the target violates the constraint, λ⋆>0\lambda^\star>0, x⋆x^\star lands exactly on the boundary, and complementary slackness holds because g(x⋆)=0g(x^\star)=0.

03

03

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt
Runnable code 1import numpy as np a = np.array([1.0, 1.0]) b = 1.0 def kkt_certificate(c): c = np.array(c, d...python
import numpy as np

a = np.array([1.0, 1.0])
b = 1.0

def kkt_certificate(c):
    c = np.array(c, dtype=float)
    violation = a @ c - b
    lambda_star = max(0.0, violation / (a @ a))
    x_star = c - lambda_star * a

    slack = a @ x_star - b
    grad_f = x_star - c
    stationarity = grad_f + lambda_star * a
    primal = 0.5 * np.linalg.norm(x_star - c) ** 2

    dual = lambda_star * violation - 0.5 * lambda_star**2 * (a @ a)
    gap = primal - dual

    return x_star, lambda_star, slack, stationarity, gap

for c in ([1.25, 1.10], [0.25, 0.35]):
    x, lam, slack, residual, gap = kkt_certificate(c)
    print("target:", c)
    print("x*:", np.round(x, 3), "lambda:", round(lam, 3))
    print("slack:", round(slack, 6))
    print("stationarity residual:", round(np.linalg.norm(residual), 6))
    print("duality gap:", round(gap, 6), "\n")

The code mirrors the math. The multiplier is positive only when the target violates the half-plane. The stationarity residual and duality gap are zero for the KKT certificate.

04

04

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

The lab asks you to predict the certificate before the numbers are revealed. Decide whether the active-constraint, inactive-constraint, or invalid-negative-multiplier story matches the current target.

Live Concept Demo

Explore Duality and KKT Conditions

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 4/5graduatecode-aligned
Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Duality and KKT Conditions should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

KKT conditions turn constrained convex optimality into a checkable certificate: feasibility, nonnegative multipliers, complementary slackness, stationarity, and zero duality gap.

Prediction open01 / Intuition
Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Duality and KKT Conditions should make visible.

Visual Inquiry

Make the image answer a mathematical question

KKT conditions turn constrained convex optimality into a checkable certificate: feasibility, nonnegative multipliers, complementary slackness, stationarity, and zero duality gap.

4/4 stages readyLive demo connected
Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Duality and KKT Conditions easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

book · 2004Convex OptimizationBoyd and Vandenberghe

Supports Lagrange dual functions, weak and strong duality, Slater's condition, duality gaps, complementary slackness, and KKT optimality conditions.

Open source
book · 2020Mathematics for Machine LearningDeisenroth, Faisal, and Ong

Supports constrained optimization, primal/dual language, strong duality in convex optimization, and the SVM duality bridge.

Open source
course-notes · 2009CS229 Section Notes: Convex Optimization OverviewChuong B. Do, Stanford CS229

Supports Lagrangian dual variables, weak/strong duality, Slater-style constraint qualifications, complementary slackness, active constraints, KKT conditions, and SVM motivation.

Open source

Claim Review

KKT conditions turn constrained convex optimality into a checkable certificate: feasibility, nonnegative multipliers, complementary slackness, stationarity, and zero duality gap.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources3 references

boyd-2004-convex-optimization-duality-kkt, deisenroth-2020-mml-duality-kkt, cs229-cvxopt2-kkt

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedFor differentiable convex problems under strong-duality conditions, KKT conditions certify optimality; complementary slackness identifies active inequalities, and the duality gap is a primal-dual certificate.Claim metadata: source checked

The sources support the Lagrangian, dual function as a lower-bound certificate, zero duality gap under convex strong-duality assumptions, complementary slackness, and the KKT feasibility/stationarity conditions.

Sources: Convex Optimization, Mathematics for Machine Learning, CS229 Section Notes: Convex Optimization OverviewThis page teaches a smooth convex toy with one affine inequality. It does not prove every constraint qualification, cover nonsmooth/subgradient KKT, solve nonconvex KKT sufficiency, or derive the SVM dual.A bounded review summary is present; still check caveats and exact reference scope.

Checked Boyd/Vandenberghe chapter 5 for Lagrange dual functions, weak/strong duality, Slater's condition, duality gaps, complementary slackness, and KKT necessity/sufficiency for differentiable convex problems; MML chapter 7 for ML-oriented constrained optimization and strong-duality framing; and Stanford CS229 convex optimization notes for KKT conditions, active constraints, and the SVM support-vector motivation. GPT Pro publication critique remains pending because 127.0.0.1:51672 refused connection.

Reviewer: codex-local-source-review; reviewed 2026-07-02
source-span-boyd-2004-convex-optimization-duality-kktsource-span-deisenroth-2020-mml-duality-kktsource-span-cs229-cvxopt2-kktEquation 1Equation 2Runnable code 1Interactive demo

Source support candidates

book 2004Convex Optimization

Supports Lagrange dual functions, weak and strong duality, Slater's condition, duality gaps, complementary slackness, and KKT optimality conditions.

book 2020Mathematics for Machine Learning

Supports constrained optimization, primal/dual language, strong duality in convex optimization, and the SVM duality bridge.

course-notes 2009CS229 Section Notes: Convex Optimization Overview

Supports Lagrangian dual variables, weak/strong duality, Slater-style constraint qualifications, complementary slackness, active constraints, KKT conditions, and SVM motivation.

Mechanism checks

Equation 1
min⁡xf0(x)subject togi(x)≤0, i=1,…,m,hj(x)=0, j=1,…,p.\min_x f_0(x) \quad\text{subject to}\quad g_i(x)\le 0,\ i=1,\ldots,m, \qquad h_j(x)=0,\ j=1,\ldots,p.
Equation 2
L(x,λ,ν)=f0(x)+∑i=1mλigi(x)+∑j=1pνjhj(x),λi≥0.\mathcal L(x,\lambda,\nu) = f_0(x)+\sum_{i=1}^m \lambda_i g_i(x)+\sum_{j=1}^p \nu_j h_j(x), \qquad \lambda_i\ge 0.
Runnable code 1import numpy as np a = np.array([1.0, 1.0]) b = 1.0 def kkt_certificate(c): c = np.array(c, d...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

KKT conditions turn constrained convex optimality into a checkable certificate: feasibility, nonnegative multipliers, complementary slackness, stationarity, and zero duality gap.

Readiness0/3 checks ready
Predict

Before touching the demo, predict one visible change that should happen in Duality and KKT Conditions.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Grounded research drawerClose
ConceptDuality and KKT ConditionsOptimization
Runnable code comparisonDuality and KKT Conditions runnable code 1a = np.array([1.0, 1.0])Prediction before revealDuality and KKT Conditions interactive demoManipulate one control and predict the visible change.
Grounded room questionWhat is the smallest example that makes Duality and KKT Conditions click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.
Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptOptimization

Duality and KKT Conditions

Attached question

What is the smallest example that makes Duality and KKT Conditions click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action
Local action draft

This draft stays in this browser, attached to the selected learning item.

No local draft saved.
Evidence to inspect
  • References to inspect: attached references on this page.
  • Definition, prerequisite, and contrast concept links
  • The equation or runnable code that makes the concept operational
  • One demo state that shows the invariant instead of a slogan
What would resolve this
  • The learner can state the mechanism in their own words
  • The learner can name the prerequisite that would repair confusion
  • The learner can predict how the mechanism changes under one perturbation
Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Duality and KKT Conditions Selected item key: recorded for copy. Context: Optimization Page anchor: recorded for copy. Open question: What is the smallest example that makes Duality and KKT Conditions click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context
concept/concept-notebook/optimization/duality-kkt-conditions concept:optimization/duality-kkt-conditions