Mathematical Foundations for Machine Learning

Quadratic Programming and the KKT Conditions

Published: 2026-07-11

Level: postgraduate

Audience: Postgraduate students in Machine Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Lagrange Multipliers & Constrained Optimization — covered in Lecture 12.
Convexity, Hessian & Critical Points — covered in Lecture 10.
Gradient Descent & Convexity — covered in Lecture 11.
PCA as Constrained Optimization — covered in Lecture 16.

Quadratic Programming and the KKT Conditions

18.1 Unconstrained vs Constrained Optimization

Hook. You already know how to find the lowest point of a function. take the derivative, set it to zero, check the second derivative. But what if you're not allowed to go everywhere? What if a wall blocks half the landscape? How do you find the best point you are allowed to reach. And how do you prove it really is the best?

18.1.1 The Marble-on-a-Surface Analogy

Intuition. Imagine a curved surface like a stretched rubber sheet with hills and valleys. You roll a marble from one side. It moves freely, rolling downhill wherever gravity takes it. And eventually settles at the lowest point. the minimum.

That is unconstrained optimization. The marble has no limits. No walls, no fences, no restrictions. The entire surface is open for exploration.

Now erect a wall. a solid fence that blocks off half the surface. The marble cannot cross it. The only region the marble can explore is the side the wall allows. This is constrained optimization.

In the constrained setting, the marble will stop at some point along the wall. or somewhere before it. But it can never go past the wall. The question becomes. how do you know the point where the marble stopped is truly the minimum? How do you verify optimality when a constraint is present?

Where the analogy breaks. A real marble has momentum and might bounce or overshoot. Optimization algorithms don't bounce. they search deliberately. Also, real walls are hard boundaries. But some optimization constraints are "soft". you pay a penalty for crossing rather than being forbidden entirely. We will see both types.

18.1.2 From Maxima-Minima to Constrained Optimization

In unconstrained optimization, you already have the toolkit. For a function like $f (x) = x^{2} - 4 x^{3} + 3 x - 6$ , you take the first derivative, set it to zero. And get the critical points. The second derivative test then classifies each one. positive $\to$ local minimum, negative $\to$ local maximum, zero $\to$ inconclusive (need higher-order tests).

Formalize. Constrained optimization extends this framework. You are no longer free to pick any point. A feasible region. the set of points that satisfy all constraints. restricts where you can search. The optimal solution must lie inside (or on the boundary of) this feasible region.

The KKT conditions (Karush-Kuhn-Tucker) are the constrained analogue of the derivative-equals-zero test. They are four conditions that, together, tell you whether a candidate point inside the feasible region is optimal. The first KKT condition. stationarity. is exactly the same idea as setting the gradient to zero. You have been doing this all along when you solved Lagrangian problems in earlier lectures. The name "KKT" just formalizes the collection of four systematic tests.

Worked example. Why unconstrained isn't enough. Minimize $f (x) = (x - 5)^{2}$ . The unconstrained minimum is at $x = 5$ , where the parabola bottoms out at $f (5) = 0$ . Now add the constraint $x \leq 2$ . The unconstrained answer $x = 5$ is illegal. it lies beyond the wall. The constrained minimum is $x = 2$ , where $f (2) = 9$ . The derivative alone cannot tell you this. you need constraint-handling logic (the KKT conditions, which we develop next).

Sense-check. The function is rising as you move away from $x = 5$ in either direction. Since the constraint forbids values greater than 2. And the function is decreasing from 5 down to 2, the best you can legally do is $x = 2$ .

Assumptions &. Scope. The KKT framework applies to problems with differentiable objective and constraint functions. If your problem has non-differentiable pieces (step functions, absolute values), the standard KKT conditions need modification (subgradients). Also, KKT provides necessary conditions for optimality in general problems. But they are enough only when the problem is convex. We cover convexity and Slater's condition in Section 18.3.

Scope. KKT conditions work for both equality and inequality constraints. They handle any number of constraints. The computational cost grows with the number of constraints and variables. But the theory itself is general.

Visual Intuition

Picture a 2D graph with $x$ on the horizontal axis and $f (x)$ on the vertical axis. The unconstrained problem draws a parabolic curve whose minimum sits at $x = 5$ . Now draw a vertical dashed line at $x = 2$ . this is the constraint "wall." The feasible region is everything to the left of (and including) this line. The constrained minimum is where the parabola meets the wall. the point $(2, 9)$ . The marble rolled down from $x = 5$ but hit the wall at $x = 2$ and stopped.

Pitfalls.

Forgetting to check the boundary. A common mistake is to run the unconstrained optimization (set derivative to zero), get a candidate. And stop. If that candidate violates a constraint, it is invalid. Always verify that every candidate satisfies all constraints.

Confusing necessary with enough. KKT conditions are necessary. if a point is optimal (under mild regularity), it satisfies KKT. But satisfying KKT does not automatically prove optimality unless the problem is convex. We explore this distinction in Section 18.3.

Ignoring multiple constraints. When a problem has several constraints, they jointly carve out the feasible region. A point might satisfy one constraint and violate another. Check every constraint.

Misidentifying the feasible region. For a constraint like $x_{1} + x_{2} \geq 1$ , the feasible region is the half-plane above the line $x_{1} + x_{2} = 1$ , not below it. Draw the region before solving.

Recap. Unconstrained optimization finds minima by setting the gradient to zero. Constrained optimization adds walls. restrictions on where you can search. KKT conditions generalize the gradient-zero test to constrained problems. The next concept (Section 18.2) formalizes these four conditions and shows you exactly how to use them.

Real-World & Domain Connection

Constrained optimization appears everywhere engineering decisions meet resource limits. A factory minimizes production cost subject to a minimum output requirement (constraint). A logistics company finds the shortest delivery route subject to vehicle capacity and driver-hour limits. In machine learning, SVM training is a constrained quadratic optimization. maximize the margin subject to correct classification of every data point. Portfolio optimization in finance minimizes risk (variance) subject to a minimum expected return constraint. In every case, the KKT framework (or its computational cousins) is what makes the solution verifiable.

18.2 The KKT Conditions

Hook. You have a function to minimize. But you are restricted by rules. inequalities that say "you cannot go past this line." The old derivative-equals-zero test is blind to walls. You need a set of conditions that tells you. For any candidate point, whether that point is the best the rules allow. That set is the KKT conditions.

18.2.1 Definition and Explanation

Intuition + Analogy. Think of balancing forces. Imagine you are leaning against a solid wall. Gravity pulls you downhill. that is the objective function trying to reduce its value. The wall pushes back. that is the constraint saying "you shall not pass." At the exact point where you stop, the force you exert on the wall exactly equals the force the wall exerts on you. The forces balance.

The Karush-Kuhn-Tucker conditions capture this balance mathematically. They are four tests that a point must pass to be optimal. They are necessary. any optimal point (under mild regularity) satisfies them. Under the right extra conditions (convexity, Slater's condition), they are also enough. any point satisfying them is optimal.

18.2.2 Symbol Registry

Before looking at the four conditions, here are the symbols we will use. Each one gets a name, a plain-language meaning. And its mathematical domain.

Symbol	Meaning	Type	Domain
$f (x)$	Objective function to minimize	scalar	$R^{n} \to R$
$g (x)$	Inequality constraint function	scalar	$R^{n} \to R$
$λ$	Lagrange multiplier (penalty/force)	scalar	$λ \geq 0$
$x$	Decision variable vector	vector	$R^{n}$
$\nabla f$	Gradient of objective	vector	$R^{n}$
$\nabla g$	Gradient of constraint	vector	$R^{n}$
$L (x, λ)$	Lagrangian. $L = f (x) + λ g (x)$	scalar	$R^{n + 1} \to R$

18.2.3 The Four Conditions

Condition 1 -- Stationarity

Formalize. Stationarity. The gradient of the Lagrangian must vanish at the optimum. In single-constraint form:

\nabla f (x) + λ \nabla g (x) = 0

Equivalently. $\nabla f (x) = - λ \nabla g (x)$ . The two gradient vectors point in exactly opposite directions. The objective's gradient says "go that way to decrease." The constraint's gradient says "push back with strength $λ$ to stay feasible." When they cancel to zero, there is no direction you can move that improves the objective and stays feasible.

This is the same step you have been doing all along. write the Lagrangian $L = f (x) + λ g (x)$ , take its gradient with respect to $x$ . And set it to zero. The only new part is the name.

Condition 2 -- Primal Feasibility

The constraint must hold. The point must be inside (or on the boundary of) the allowed region.

g (x) \leq 0

If your constraint says $x_{1} + x_{2} \leq 4$ , then $x_{1} + x_{2} = 5$ is illegal. Primal feasibility means. test every original constraint. All must pass.

Condition 3 -- Dual Feasibility

The Lagrange multiplier cannot be negative.

λ \geq 0

The multiplier is a penalty for violating the constraint. A negative multiplier would reward violation. That makes no sense physically. the wall pushes back. it does not pull you through. If you are safely inside the feasible region, $λ = 0$ (the wall exerts no force). If you are on the boundary, $λ \geq 0$ (the wall pushes).

Condition 4 -- Complementary Slackness

The most important condition. The product of the multiplier and the constraint must be zero.

λ \cdot g (x) = 0

This single equation creates exactly two meaningful scenarios:

Case A. Constraint inactive ( $λ = 0$ ). The wall is far away. You are safely inside the feasible region. So $g (x) < 0$ . The multiplier is zero. no force from the wall. The optimum here is the same as the unconstrained optimum.

Case B. Constraint active ( $g (x) = 0$ ). You are exactly on the wall. The constraint value is zero because you are on the boundary. The multiplier $λ$ can be any non-negative number. The wall is pushing. But the product $λ \cdot 0 = 0$ vanishes. The penalty contributes nothing at the optimum.

A hypothetical Case C. you are far from the wall ( $g (x) < 0$ ) but feel a ghost force ( $λ > 0$ ). is ruled out. The product $λ \cdot g (x) = 0$ forbids it.

Worked Example. Spotting the cases. Minimize $f (x) = x^{2}$ subject to $x \geq - 2$ . Rewrite the constraint. $- x - 2 \leq 0$ . So $g (x) = - x - 2$ . The Lagrangian is $L = x^{2} + λ (- x - 2)$ .

Stationarity. $2 x - λ = 0 ⟹ λ = 2 x$ .

Complementary slackness. $λ (- x - 2) = 0$ .

Case A ( $λ = 0$ ). Then $2 x = 0 ⟹ x = 0$ . Check primal feasibility. $- 0 - 2 = - 2 \leq 0$ . Valid. Dual feasibility. $λ = 0 \geq 0$ . Valid. The point $(x = 0, λ = 0)$ works.
Case B ( $- x - 2 = 0$ ). Then $x = - 2$ . Stationarity gives $λ = 2 (- 2) = - 4$ . But dual feasibility requires $λ \geq 0$ . Invalid.

Result: The optimal point is $x = 0$ , inside the feasible region (since $0 \geq - 2$ ), with the constraint inactive. Sense-check. $f (0) = 0$ is indeed the minimum of $x^{2}$ . And $x = 0$ satisfies $x \geq - 2$ .

Visual Intuition

Picture a 2D plot. The objective $f (x)$ is a U-shaped parabola. The constraint $g (x) \leq 0$ defines a half-line on the x-axis. The feasible region is everything to the left of the constraint boundary. Draw the gradient vector $\nabla f$ at a candidate point. it points toward lower values. Draw $- λ \nabla g$ . it points perpendicularly outward from the constraint boundary. At optimality, these two arrows are equal and opposite. If the point is inside the feasible region, the constraint arrow has zero length ( $λ = 0$ ). If the point is on the boundary, both arrows have positive length and balance perfectly.

Assumptions &. Scope.

Differentiability. KKT requires $f$ and $g$ to be differentiable at the candidate point. Non-smooth problems (with absolute values, max functions) need subgradient generalizations.
Regularity. A technical condition called constraint qualification must hold at the optimal point. The simplest version. the gradients of active constraints must be linearly independent. Without it, KKT may fail even at an optimum. Slater's condition (Section 18.3) is one way to guarantee regularity for convex problems.
Necessary vs enough. KKT conditions are necessary for optimality under regularity. They are enough (proving the point is optimal) only when the problem is convex.

Pitfalls.

Forgetting to check all four conditions. Students often stop after stationarity. But a point satisfying $\nabla L = 0$ might violate primal feasibility or dual feasibility. All four must pass.

Using the wrong sign convention. The standard form is $f (x) + λ g (x)$ with $g (x) \leq 0$ . If your constraint is $h (x) \geq 0$ , convert it. multiply by $- 1$ to get $- h (x) \leq 0$ . Do not just flip the sign of $λ$ .

Confusing complementary slackness with " $λ$ and $g (x)$ cannot both be positive." They can both be positive in Case A/B individually. it is the product that must be zero. In Case B, $λ > 0$ and $g (x) = 0$ . So the product is zero. Both being positive simultaneously is Case C, which the product forbids.

Trying to prove sufficiency without convexity. KKT alone does not prove optimality on non-convex surfaces. You also need convexity or Slater's condition.

18.2.4 Student Questions and Answers

Q: Is complementary slackness an more validation on top of KKT. Or is it one of the four conditions?

A: It is one of the four conditions. the fourth one. The four conditions are. stationarity ( $\nabla L = 0$ ), primal feasibility ( $g (x) \leq 0$ ), dual feasibility ( $λ \geq 0$ ). And complementary slackness ( $λ \cdot g (x) = 0$ ). All four are part of the KKT framework.

Q: When we use the gradient of the Lagrangian to start solving. does not that already cover stationarity?

A: Yes. Taking $\nabla L = 0$ is stationarity. You then verify the remaining three conditions at the point you found. primal feasibility, dual feasibility. And complementary slackness. The stationarity step finds candidates. the other three test whether those candidates are actually valid.

Recap. The KKT conditions are four tests. stationarity, primal feasibility, dual feasibility, complementary slackness. that together characterize optimality in constrained problems. Stationarity generalizes the derivative-zero test. The remaining three handle the constraint logic. Next, we examine Slater's condition (Section 18.3), the extra requirement that makes KKT enough and not just necessary.

Real-World & Domain Connection

KKT conditions underpin virtually every constrained optimization solver in engineering and finance. When an airline schedules crew and aircraft subject to FAA rest requirements, the solver internally verifies KKT at the candidate schedule. When a hedge fund constructs a minimum-variance portfolio subject to a return target, the optimal weights satisfy KKT. In machine learning, the SVM dual formulation derives directly from KKT conditions applied to the primal. the stationarity condition gives $w = \sum α_{i} y_{i} x_{i}$ . And complementary slackness tells us which data points become support vectors.

18.3 Slater's Condition

Hook. The KKT conditions tell you a point might be optimal. they are necessary. But how do you know for sure? What if multiple points all pass KKT. And you cannot tell which one is actually the global minimum? Slater's condition is the extra check that upgrades KKT from "necessary" to "enough."

18.3.1 Definition and Motivation

Intuition + Analogy. Imagine a curved bowl. the kind you eat soup from. Drop a marble anywhere. It will always roll to the same bottom. The bowl has exactly one lowest point. Now imagine a flat tray. If you tilt it just right, a marble could stop anywhere. there is no single lowest point.

Slater's condition is a test that tells you whether your feasible region plus objective function behaves like a bowl (curved, unique minimum) or like a flat tray (linear, potentially many minima). The test is simple. find one point that lies strictly inside the feasible region. not on any constraint boundary. If you can find such a point. And your problem is convex, then KKT conditions alone guarantee optimality. The surface has curvature. There is only one minimum.

18.3.2 Why It Matters

Formalize. A constrained optimization problem is convex when the objective $f (x)$ is a convex function and the feasible set (all $x$ satisfying $g_{i} (x) \leq 0$ ) is a convex set. For such problems, Slater's condition states:

If there exists at least one point $x_{0}$ such that $g_{i} (x_{0}) < 0$ for every inequality constraint (the point is strictly inside, not on any boundary), then the KKT conditions are enough for optimality.

In other words. find a strictly interior point $\to$ KKT gives the global minimum. No interior point $\to$ you could be on a flat surface where KKT holds at many points. And you cannot pick a unique optimum.

Worked Example. Testing Slater's condition. Consider the problem. minimize $(x - 2)^{2} + (y - 2)^{2}$ subject to $x + y \leq 5$ and $x \geq 0, y \geq 0$ .

The objective is convex (it is a paraboloid. a 3D bowl).
The constraints are linear (convex).

Now find a strictly interior point. Try $(x, y) = (1, 1)$ :

$x + y = 2 < 5$ ✓ (strictly inside the first constraint)
$x = 1 > 0$ ✓, $y = 1 > 0$ ✓ (strictly inside the non-negativity constraints)

Since all inequality constraints are strictly satisfied at $(1, 1)$ , Slater's condition holds. Any point satisfying KKT is the unique global minimum.

Counterexample. When Slater fails. Minimize $x^{2}$ subject to $x^{2} \leq 0$ . The only feasible point is $x = 0$ . There is no strictly interior point. every feasible point is on the boundary. KKT holds at $x = 0$ (directly). And in this case $x = 0$ is the minimum. But in more complex problems of this shape, you cannot rely on KKT alone to guarantee sufficiency.

Sense-check. The existence of an interior point proves the feasible region has some "volume". it is not a degenerate flat set. This volume, combined with convexity, forces a unique optimum.

Visual Intuition

Picture a 3D bowl (the objective) and a flat plane slicing through it (the constraint). The feasible region is the part of the bowl below the plane. The "strictly interior point" is a point below the plane, not touching it. On a curved bowl, the lowest point in the sliced region is unique. On a flat surface (linear objective with linear constraints), every point at the same level has the same objective value. there is no unique minimum. Slater's condition confirms you are working with a bowl, not a tray.

Assumptions &. Scope.

Convexity required. Slater's condition applies to convex problems. If the problem is non-convex, KKT conditions (even with Slater) do not guarantee global optimality. they only give candidate local minima.
Only for inequality constraints. The interior point must strictly satisfy all inequality constraints ( $g_{i} (x) < 0$ ). Equality constraints ( $h_{i} (x) = 0$ ) are always on the boundary by definition. Slater's condition for problems with equality constraints requires a modified statement.
Constraint qualification. Slater's condition is itself a constraint qualification. it guarantees that the KKT conditions are valid (i.e., the Lagrange multipliers exist at the optimum).

Pitfalls.

Searching for an interior point after finding the KKT point. The order does not matter. But the interior point must exist. The professor emphasizes. the interior point does not need to satisfy KKT. It just needs to exist somewhere in the feasible region to prove the surface is curved.

Confusing Slater with a redundant check. Students sometimes ask, "If we already found a KKT point, why bother with Slater?" Because on a flat surface, KKT can hold at infinitely many points, none of which is a unique global minimum. Slater confirms uniqueness.

Misunderstanding "inside." "Strictly inside" means $g_{i} (x) < 0$ for every inequality constraint. Being exactly on one constraint boundary ( $g_{i} (x) = 0$ ) means you are NOT strictly inside. In 3D, an interior point sits within the volume of the feasible region, not on its surface.

Thinking Slater's condition is hard to check. For the QP problems in this course, Slater's condition is almost always directly satisfied. Find any point that satisfies all constraints strictly. the origin, a midpoint, a small random vector. If none exists, the problem is degenerate (like a line or a single point).

18.3.3 Student Questions and Answers

Q: Several students asked. For Slater's condition, we just need to find a point inside the feasible region. And that automatically proves all four KKT conditions? Why do we need Slater if we are already finding the optimal point with KKT?

A: Slater's condition tells you about the shape of the surface, not the value of the KKT point. Finding a point strictly inside the feasible region confirms you are working with a curved (convex) surface, not a flat one. On a flat surface. like a line. KKT conditions might hold at many points simultaneously. Slater's condition eliminates that ambiguity. If a strictly interior feasible point exists, the surface has curvature, the convex problem has a unique minimum. And whatever point satisfies KKT must be that minimum.

Q: In the visual example of the bowl with the pink point inside. how can any point other than the optimal point satisfy KKT conditions inside a curved surface?

A: It cannot. That is precisely the point. If the surface is a curved bowl. convex and quadratic. there is only one minimum. If KKT conditions hold at some point. And you can find any point strictly inside the feasible region (confirming curvature), then the KKT point is guaranteed to be the unique global minimum. The interior point does not need to satisfy KKT. it just needs to exist.

Q: By "point inside the surface," do you mean the point should be surrounded by surface? On a 3D plane, a point would just be on the surface.

A: On a 3D bowl surface, points can be inside. Think of the pink dot sitting within the volume of the bowl, not touching the rim. If the surface is a flat plane (linear), there is no "inside". every point is on the boundary. Having an interior point confirms curvature. Without one, you could be on a linear surface where multiple points satisfy KKT.

Recap. Slater's condition is the "green light" that upgrades KKT from necessary to enough. Find one point strictly inside the feasible region in a convex problem. And any KKT-satisfying point is the global optimum. If no interior point exists, the problem may be degenerate. Next (Section 18.4), we dive deeper into complementary slackness. the most practically important KKT condition. and explore its two cases through a wall analogy that maps directly to SVM support vectors.

Real-World & Domain Connection

Slater's condition is the theoretical guarantee behind every convex solver's claim of global optimality. In SVM training, Slater's condition holds directly for linearly separable data. there is always a region strictly between the two margin hyperplanes where no data point sits. This guarantees that the dual SVM solution equals the primal, making the kernel trick mathematically valid. In portfolio optimization, the covariance matrix $Q$ is positive definite by construction. And budget constraints ( $\sum w_{i} = 1$ ) always admit interior points (equal-weight portfolios). So Slater's condition holds and the QP solution is globally optimal.

18.4 Complementary Slackness -- The Wall Analogy

Hook. Of the four KKT conditions, complementary slackness is the one that actually does the heavy lifting when you solve problems by hand. It splits every constraint into exactly two cases. active or inactive. and those two cases are the engine behind every KKT solution you will ever write. It is also the mathematical reason SVMs only care about a handful of data points.

18.4.1 Two Cases That Matter

Intuition + Analogy. You are standing in a room with one wall. The wall represents a constraint. you cannot go past it. Now think about the force the wall exerts on you:

If you are leaning against the wall (Case A), the wall pushes back. You feel a real force. If you moved even a millimeter, you would be through the wall. illegal. Here the constraint is active. And the force (the Lagrange multiplier $λ$ ) is positive.

If you are standing in the middle of the room (Case B), the wall is far away. It exerts zero force on you. You can move in any direction without worrying about it. Here the constraint is inactive. And the multiplier $λ$ is zero.

A ghost scenario (Case C). standing in the middle of the room yet feeling a force from a wall you are not touching. makes no physical sense. The math rules it out. $λ \cdot g (x) = 0$ means this product must vanish.

Symbol Registry

Symbol	Meaning	Type	Domain
$λ$	Lagrange multiplier (force from wall)	scalar	$λ \geq 0$
$g (x)$	Constraint function at point $x$	scalar	$g (x) \leq 0$
$α_{i}$	SVM multiplier for data point $i$	scalar	$α_{i} \geq 0$
$y_{i}$	Class label for data point $i$	scalar	$y_{i} \in {- 1, + 1}$

Formalize. The complementary slackness condition is:

λ \cdot g (x) = 0

This single equation forces exactly two scenarios at the optimum:

Case A. Constraint active ( $g (x) = 0$ ). You are exactly on the boundary. The constraint is tight. The multiplier $λ$ may be positive. the wall pushes back. The product is zero because $0 \times λ = 0$ .

Case B. Constraint inactive ( $λ = 0$ ). You are safely inside the feasible region. The wall exerts no force. The product is zero because $λ \times g (x) = 0 \times (negative number) = 0$ .

Both cases produce $λ \cdot g (x) = 0$ . The condition is satisfied in either scenario. The condition does NOT say " $λ$ and $g (x)$ cannot both be positive". it says their product must be zero, which is a weaker (and physically more meaningful) statement.

Worked Example. Active vs inactive in one problem. Minimize $f (x) = x^{2} - 4 x$ subject to $x \leq 1$ . Rewrite. $g (x) = x - 1 \leq 0$ . The Lagrangian is $L = x^{2} - 4 x + λ (x - 1)$ .

Stationarity: $2 x - 4 + λ = 0 ⟹ λ = 4 - 2 x$ .

Complementary slackness: $λ \cdot (x - 1) = 0$ .

Case A ( $λ = 0$ ). Then $4 - 2 x = 0 ⟹ x = 2$ . Primal check. $g (2) = 2 - 1 = 1 > 0$ . violates the constraint. Discard.
Case B ( $x - 1 = 0$ ). Then $x = 1$ . $λ = 4 - 2 (1) = 2$ . Dual check. $λ = 2 \geq 0$ . All conditions pass.

Result: The optimum is $x = 1$ with $λ = 2$ . The constraint is active. you are on the wall. Sense-check: The unconstrained minimum of $x^{2} - 4 x$ is at $x = 2$ , where the parabola bottoms out. The constraint $x \leq 1$ blocks that point. The best legal point is the closest feasible point, $x = 1$ .

18.4.2 From SVM's Perspective

Connection to SVM. Complementary slackness is the mathematical reason SVMs are "sparse". why they only care about a handful of data points.

In the SVM primal, each data point $i$ gets a constraint. $y_{i} (w^{T} x_{i} + b) \geq 1$ . In the dual, each gets a multiplier $α_{i} \geq 0$ . The complementary slackness condition becomes:

α_{i} \cdot [y_{i} (w^{T} x_{i} + b) - 1] = 0

This creates the same two cases:

Support vectors ( $α_{i} > 0$ ). The point lies exactly on the margin. The constraint is active. $y_{i} (w^{T} x_{i} + b) - 1 = 0$ . These points define where the hyperplane goes.

Non-support vectors ( $α_{i} = 0$ ). The point lies safely beyond the margin. The constraint is inactive. $y_{i} (w^{T} x_{i} + b) - 1 > 0$ . These points contribute zero to the solution.

The SVM solution $w = \sum α_{i} y_{i} x_{i}$ sums only over points with $α_{i} > 0$ . the support vectors. Complementary slackness is the switch that turns off 99% of the data.

Visual Intuition

Draw a horizontal axis for $x$ and a vertical axis for the multiplier $λ$ . The condition $λ \cdot g (x) = 0$ traces two perpendicular line segments. the $λ$ -axis (where $g (x) = 0$ . So the point is on the constraint boundary) and the $g (x)$ -axis (where $λ = 0$ . So the point is inside). The optimal solution sits somewhere on this L-shaped region. In Case A, you are on the vertical segment. in Case B, you are on the horizontal segment.

Assumptions &. Scope.

Multiple constraints. With $m$ constraints, complementary slackness applies per constraint. $λ_{i} \cdot g_{i} (x) = 0$ for each $i$ . Each constraint independently may be active or inactive.
Equality constraints. Equality constraints $h (x) = 0$ have no complementary slackness condition. they are always active by definition. Their multipliers are unrestricted in sign.

Pitfalls.

Misreading the condition as "either $λ = 0$ or $g (x) = 0$ ." Correct. But incomplete. The condition requires the product to be zero. Both could be zero simultaneously, though this is rare in practice.

Forgetting to use complementary slackness for case splitting. Students sometimes try to solve for $x$ and $λ$ from stationarity alone and end up with one equation in two unknowns. Complementary slackness is the second equation you need. it tells you either $λ = 0$ or $g (x) = 0$ .

Solving both cases and keeping both answers. Only one case will satisfy all four KKT conditions simultaneously (in well-posed convex problems). Check primal and dual feasibility on both and discard the invalid one.

Using complementary slackness backwards. The condition is $λ \cdot g (x) = 0$ , not $λ + g (x) = 0$ and not $λ - g (x) = 0$ . The product being zero is what ties the multiplier to the constraint level.

Recap. Complementary slackness ( $λ \cdot g (x) = 0$ ) splits every constraint into two cases. active ( $g (x) = 0$ , $λ \geq 0$ ) or inactive ( $λ = 0$ , $g (x) < 0$ ). This case-splitting is the engine of KKT solution methods and the reason SVMs only depend on support vectors. Next (Section 18.5), we work through a full single-variable QP example using all four KKT conditions, including step-by-step case analysis with complementary slackness.

Real-World & Domain Connection

Complementary slackness identifies which constraints actually matter. In cloud infrastructure scheduling (the example from this lecture), hundreds of customer pods each have time-window constraints. At the optimal schedule, only a handful of constraints are binding. the rest are inactive and can be ignored. Similarly, in portfolio optimization, only assets at their allocation bounds get non-zero multipliers. In structural engineering, only the beams that are at their stress limits matter for a safety analysis. The pattern is universal. constraints that are not binding do not affect the optimum.

18.5 Worked Example 1 -- Single-Variable QP with KKT

Hook. You know the theory. Now let us put all four KKT conditions to work on a concrete problem. The goal is to minimize a simple quadratic function subject to a single inequality constraint. By the end, you will have the exact recipe for any KKT problem. write the Lagrangian, apply stationarity, split cases with complementary slackness. And verify the remaining conditions.

18.5.1 Problem Statement

Minimize:

f (x) = (x - 3)^{2}

Subject to:

x \leq 1

Symbol Registry:

Symbol	Meaning	Type	Domain
$f (x)$	Objective to minimize. $(x - 3)^{2}$	scalar	$R \to R$
$g (x)$	Constraint. $x - 1 \leq 0$	scalar	$R \to R$
$λ$	Lagrange multiplier	scalar	$λ \geq 0$
$L (x, λ)$	Lagrangian	scalar	$R^{2} \to R$

18.5.2 Setup

Intuition. The function $(x - 3)^{2}$ is a parabola centered at $x = 3$ . Without constraints, the minimum is at $x = 3$ with value $f (3) = 0$ . But the constraint says $x \leq 1$ . a wall at $x = 1$ blocks the way. You cannot reach 3. The constrained minimum must be at or before $x = 1$ .

Rewrite the constraint in standard form $g (x) \leq 0$ :

x \leq 1 ⟹ x - 1 \leq 0

So $g (x) = x - 1$ .

18.5.3 Form the Lagrangian

L (x, λ) = (x - 3)^{2} + λ (x - 1)

18.5.4 Stationarity

Take the derivative of $L$ with respect to $x$ and set to zero:

\frac{\partial L}{\partial x} = 2 (x - 3) + λ = 0

So the stationarity condition gives us one equation relating $x$ and $λ$ :

2 (x - 3) + λ = 0 ⟹ λ = - 2 (x - 3) = 2 (3 - x)

18.5.5 Apply Complementary Slackness

Formalize. Case splitting. The complementary slackness condition:

λ \cdot (x - 1) = 0

gives two cases to check.

Case A. $λ = 0$ (constraint inactive):

If $λ = 0$ , then from stationarity. $2 (x - 3) + 0 = 0 ⟹ x = 3$ .

Check primal feasibility at $x = 3$ . $g (3) = 3 - 1 = 2 ≰ 0$ . The point lies past the wall. This case is invalid.

Case B. $x - 1 = 0$ (constraint active):

If $x = 1$ , substitute into stationarity:

2 (1 - 3) + λ = 0 ⟹ 2 (- 2) + λ = 0 ⟹ - 4 + λ = 0 ⟹ λ = 4

Candidate. $x = 1$ , $λ = 4$ .

18.5.6 Verify All KKT Conditions

At the candidate $x = 1, λ = 4$ :

Stationarity: $2 (x - 3) + λ = 2 (1 - 3) + 4 = - 4 + 4 = 0$ . ✓
Primal feasibility: $g (x) = x - 1 = 1 - 1 = 0 \leq 0$ . ✓
Dual feasibility: $λ = 4 \geq 0$ . ✓
Complementary slackness: $λ \cdot g (x) = 4 \cdot 0 = 0$ . ✓

All four conditions pass. The optimal solution is $x^{*} = 1$ .

18.5.7 Interpretation

The optimal point $x = 1$ lies exactly on the constraint boundary. The multiplier $λ = 4$ is positive, confirming the constraint is active. the wall is pushing back with a "force" of 4.

Worked Example. Summary box. The constrained optimal value is $f (1) = (1 - 3)^{2} = 4$ . Compare with the unconstrained minimum $f (3) = 0$ . The constraint costs you 4 units of objective value.

Sense-check. The parabola $(x - 3)^{2}$ decreases as you move from any point toward $x = 3$ . At $x = 1$ , you are moving toward $x = 3$ from the left. If you could go one more unit right (to $x = 2$ ), the value would drop from 4 to 1. But the wall at $x = 1$ stops you. The value 4 is the best you can legally achieve.

Visual Intuition

Plot $f (x) = (x - 3)^{2}$ . a U-shaped parabola with its bottom at $(3, 0)$ . Draw a vertical dashed line at $x = 1$ . the constraint boundary. Shade the region $x \leq 1$ as the feasible region. The constrained minimum is the leftmost point of the parabola within the shaded region. the point $(1, 4)$ , where the parabola intersects the wall.

Pitfalls.

Not rewriting the constraint. The standard Lagrangian form requires $g (x) \leq 0$ . The original constraint was $x \leq 1$ . Rewriting to $x - 1 \leq 0$ gives $g (x) = x - 1$ . If you use $g (x) = 1 - x$ instead, the Lagrangian sign flips and the solution changes. Always convert to $g (x) \leq 0$ form first.

Accepting Case A without checking feasibility. Case A ( $λ = 0$ ) gave $x = 3$ , which violates the constraint. Students sometimes stop here and report $x = 3$ as the answer. Always verify primal feasibility on every candidate from every case.

Forgetting the sign of $λ$ . When $x = 1$ gave $λ = 4$ , that is valid ( $λ \geq 0$ ). But in other problems, the active case might give a negative $λ$ , which fails dual feasibility. Check the sign.

18.5.8 Student Questions and Answers

Q: In Case B we used $x - 1 = 0$ to find $x = 1$ , then substituted back to get $λ = 4$ . What about the $x = 3$ from Case A. why cannot we use it?

A: $x = 3$ came from assuming $λ = 0$ (constraint inactive). But $x = 3$ violates the constraint $x \leq 1$ . it lies past the wall. Primal feasibility fails. That case is discarded. The only valid case is $x - 1 = 0$ , which puts the point exactly at the wall boundary.

Q: How do we write the final solution in an exam?

A: State the optimal point. $x^{*} = 1$ . Then show each KKT condition verified. stationarity (the derivative equation holds), primal feasibility ( $x - 1 \leq 0$ ), dual feasibility ( $λ = 4 \geq 0$ ). And complementary slackness ( $λ (x - 1) = 0$ ). Conclude. "All KKT conditions are satisfied. So $x^{*} = 1$ is the optimal solution."

Recap. The KKT recipe for a single-variable QP has seven steps.

First, write the constraint as $g (x) \leq 0$ . Then form the Lagrangian $L = f + λ g$ .

Set $\partial L / \partial x = 0$ for stationarity. Split cases using $λ \cdot g (x) = 0$ for complementary slackness.

Check primal and dual feasibility on each candidate. Discard the invalid cases. The survivor is the optimum.

Next (Section 18.6), we generalize this from one variable to $n$ variables using vector and matrix notation.

Real-World & Domain Connection

The single-variable case maps to any optimization with one decision. how many units to produce given a capacity limit, what interest rate to offer given a regulatory cap, what temperature to set given an energy budget. The KKT recipe. Lagrangian, stationarity, case split, feasibility check. scales directly to the multi-variable QP problems that drive portfolio optimization, SVM training. And supply chain logistics.

18.6 Quadratic Programming in Vector Form

Hook. A quadratic program sounds intimidating. But you have already solved one in Section 18.5. The only new thing here is notation. we replace scalars with vectors and matrices so the same logic handles problems with hundreds of variables instead of just one. Everything you learned about KKT still applies.

18.6.1 The Standard Form

Intuition + Analogy. Think of $x$ as a shopping cart full of decisions. maybe it has the amounts of 50 different stocks to buy. The term $\frac{1}{2} x^{T} Q x$ measures how those decisions interact (risk, in the stock example. two stocks might move together). The term $c^{T} x$ is the standalone cost of each decision. The constraint $A x \leq b$ is your budget. you cannot spend more than $b$ .

Formalize. A quadratic program (QP) in vector form:

Minimize \frac{1}{2} x^{T} Q x + c^{T} x

The variable $x \in R^{n}$ is an $n$ -dimensional decision vector. $Q \in R^{n \times n}$ is the quadratic term matrix. $c \in R^{n}$ is the linear coefficient vector. The objective has two parts:

$\frac{1}{2} x^{T} Q x$ . the quadratic part (interaction effects)
$c^{T} x$ . the linear part (standalone contributions)

The factor $\frac{1}{2}$ is there purely for calculus convenience. it cancels the 2 that appears when you differentiate $x^{T} Q x$ .

Symbol Registry

Symbol	Meaning	Type	Dimensions
$x$	Decision variable vector	vector	$n \times 1$
$Q$	Quadratic term matrix	matrix	$n \times n$
$c$	Linear term coefficients	vector	$n \times 1$
$A$	Inequality constraint coefficients	matrix	$m \times n$
$b$	Inequality constraint RHS	vector	$m \times 1$
$E$	Equality constraint coefficients	matrix	$p \times n$
$d$	Equality constraint RHS	vector	$p \times 1$

18.6.2 Why Quadratic -- A Concrete Example

Worked Example. Let $x = [x_{1} x_{2}]$ be a 2D vector and let $Q = I = [1001]$ (the identity matrix). Then:

\frac{1}{2} x^{T} Q x = \frac{1}{2} [x_{1} x_{2}] [1001] [x_{1} x_{2}] = \frac{1}{2} (x_{1}^{2} + x_{2}^{2})

This is a parabolic bowl in 3D. half the squared distance from the origin. Different $Q$ matrices produce different shapes. diagonal $Q$ gives axes-aligned ellipses. off-diagonal entries tilt and rotate the surface.

Now add a linear term. if $c = [- 2 0]$ , then $c^{T} x = - 2 x_{1}$ . The bowl shifts horizontally. its minimum moves away from the origin. The full objective $\frac{1}{2} (x_{1}^{2} + x_{2}^{2}) - 2 x_{1} = \frac{1}{2} [(x_{1} - 2)^{2} + x_{2}^{2}] - 2$ has its unconstrained minimum at $(x_{1}, x_{2}) = (2, 0)$ .

18.6.3 The Role of Q -- Positive Semi-Definiteness

A matrix $Q$ is positive semi-definite (PSD) if:

x^{T} Q x \geq 0 for all vectors x

When $Q$ is PSD:

The quadratic surface is convex. shaped like a bowl.
Local minima = global minima. Any minimum you find is the global minimum.
Gradient-based optimization converges regardless of starting point.

If $Q$ is symmetric and PSD, the bowl is symmetric. The surface is identical on both sides of the minimum.

SVM connection: In the SVM primal, the objective is $\frac{1}{2} ∥ w ∥^{2} = \frac{1}{2} w^{T} I w$ . So $Q = I$ . the identity matrix. The identity is PSD (in fact, positive definite). This guarantees the SVM problem is convex. And the solution is the unique globally optimal margin.

Visual Intuition

Imagine a 3D plot with $x_{1}, x_{2}$ on the horizontal plane and the objective value on the vertical axis. With $Q = I$ and $c = 0$ , the surface is a symmetric bowl centered at the origin. Changing $Q$ stretches the bowl into an elliptical shape. Adding $c$ shifts the bowl's center. Constraints $A x \leq b$ cut the bowl with flat planes. the feasible region is the part of the bowl below the cutting plane.

18.6.4 Adding Constraints

Inequality constraints (walls):

A x \leq b

$A$ is $m \times n$ . each row is one constraint. $b$ is an $m$ -dimensional vector of right-hand-side values. The inequality is component-wise. each row $i$ says $\sum_{j} A_{ij} x_{j} \leq b_{i}$ .

Equality constraints (exact requirements):

E x = d

$E$ is $p \times n$ , $d$ is $p$ -dimensional. Equality constraints force the solution to lie exactly on a hyperplane.

18.6.5 Dimensions Summary

Object	Description	Dimensions
$x$	Decision variable vector	$n \times 1$
$Q$	Quadratic term matrix	$n \times n$
$c$	Linear term vector	$n \times 1$
$A$	Inequality constraint coefficients	$m \times n$
$b$	Inequality constraint RHS	$m \times 1$
$E$	Equality constraint coefficients	$p \times n$
$d$	Equality constraint RHS	$p \times 1$

Assumptions &. Scope.

Convexity requires PSD Q. If $Q$ is not PSD, the problem may have saddle points or multiple local minima. KKT gives necessary conditions. But not sufficiency.
Dimension compatibility. Every matrix-vector multiplication must be dimensionally sound. $x^{T} Q x$ requires $Q$ to be $n \times n$ . $c^{T} x$ requires $c$ to be $n \times 1$ . $A x$ requires $A$ to have $n$ columns.
Inequality vs equality. Inequality constraints ( $A x \leq b$ ) require signed multipliers ( $λ \geq 0$ ). Equality constraints ( $E x = d$ ) use unrestricted multipliers ( $ν \in R^{p}$ ).

Pitfalls.

Forgetting the $\frac{1}{2}$ factor. The factor $\frac{1}{2}$ in $\frac{1}{2} x^{T} Q x$ is not decorative. When you differentiate, $\frac{\partial}{\partial x} (\frac{1}{2} x^{T} Q x) = Q x$ (if $Q$ is symmetric). Without it, the gradient is $2 Q x$ . And formulas throughout the literature would differ.

Confusing PSD with PD. Positive semi-definite ( $x^{T} Q x \geq 0$ ) permits a zero eigenvalue. the bowl has a flat bottom in one direction. Positive definite ( $x^{T} Q x > 0$ for $x \neq = 0$ ) is strictly curved. A zero eigenvalue means the gradient-zero equation $Q x = - c - A^{T} λ$ might not have a unique solution.

Dimension mismatch in constraints. Each constraint row multiplies all $n$ variables. If you have 3 variables and write $A x \leq b$ , $A$ must be $m \times 3$ . A common error is transposing dimensions.

Recap. QP in vector form generalizes the single-variable case to $n$ dimensions. The quadratic part $\frac{1}{2} x^{T} Q x$ captures interactions. the linear part $c^{T} x$ captures independent effects. $Q$ being PSD guarantees convexity and a unique global minimum. Constraints $A x \leq b$ and $E x = d$ define the feasible region. Next (Section 18.7), we build the Lagrangian for this general form and derive its gradient.

Real-World & Domain Connection

The QP vector form is the standard representation in every numerical optimization solver. CVXOPT, Gurobi, OSQP. And MATLAB's quadprog all accept problems in exactly this format. Portfolio optimization uses $Q$ as the covariance matrix of asset returns, $c$ as negative expected returns. And constraints for budget and sector allocations. Model predictive control in robotics solves a QP at every time step to plan the next control action subject to actuator limits.

18.7 Lagrangian for General Quadratic Programs

Hook. The single-variable Lagrangian from Section 18.5 was $L = (x - 3)^{2} + λ (x - 1)$ . Now we need the $n$ -variable version with $m$ inequality constraints and $p$ equality constraints. The pattern is the same. objective plus penalty terms. Only the notation balloons. vectors and matrices instead of scalars.

18.7.1 Formulating the Lagrangian

Intuition + Analogy. Think of running a factory with $n$ machines. Each machine setting $x_{j}$ affects your production cost (the objective $\frac{1}{2} x^{T} Q x + c^{T} x$ ). You have $m$ safety rules (inequality constraints $A x \leq b$ ) and $p$ production targets (equality constraints $E x = d$ ). The Lagrangian creates a single score that combines your production cost with penalties for breaking rules. A safety inspector checks each rule and assigns a fine. the multiplier $λ_{i}$ for rule $i$ .

Symbol Registry

Symbols $x, Q, c, A, b, E, d$ carry over from Section 18.6. New symbols:

Symbol	Meaning	Type	Dimensions / Domain
$λ$	Multiplier vector for inequality constraints	vector	$m \times 1$ , $λ \geq 0$
$ν$	Multiplier vector for equality constraints	vector	$p \times 1$ , unrestricted
$L (x, λ, ν)$	Lagrangian	scalar	$R^{n + m + p} \to R$
$g (λ, ν)$	Dual function (after substituting $x$ )	scalar	$R^{m + p} \to R$

Formalize. The Lagrangian for a general QP:

L (x, λ, ν) = \frac{1}{2} x^{T} Q x + c^{T} x + λ^{T} (A x - b) + ν^{T} (E x - d)

Each piece:

$\frac{1}{2} x^{T} Q x + c^{T} x$ . the original objective
$λ^{T} (A x - b)$ . penalty for inequality constraint violation. Since $A x - b \leq 0$ , this term is always $\leq 0$ when $λ \geq 0$ . It reduces the Lagrangian value.
$ν^{T} (E x - d)$ . penalty for equality constraint violation. Since $ν$ is sign-unrestricted, this term can increase or decrease $L$ .

The constraint $A x \leq b$ is rewritten as $A x - b \leq 0$ to match the standard form $g (x) \leq 0$ . The $λ^{T}$ transpose makes the product a scalar. $λ$ is $m \times 1$ and $(A x - b)$ is $m \times 1$ . So $λ^{T} (A x - b)$ is $1 \times 1$ .

18.7.2 Taking the Gradient

Formalize. Stationarity. Take the gradient with respect to $x$ and set to zero:

\nabla_{x} L = Q x + c + A^{T} λ + E^{T} ν = 0

Why each term:

$\frac{\partial}{\partial x} (\frac{1}{2} x^{T} Q x) = Q x$ . the $\frac{1}{2}$ cancels the 2 from differentiation, just like $\frac{d}{d x} (\frac{1}{2} a x^{2}) = a x$
$\frac{\partial}{\partial x} (c^{T} x) = c$ . the gradient of a linear form is its coefficient vector
$\frac{\partial}{\partial x} (λ^{T} A x) = A^{T} λ$ . the transpose appears because the derivative of $u^{T} A x$ with respect to $x$ is $A^{T} u$
$\frac{\partial}{\partial x} (ν^{T} E x) = E^{T} ν$ . same logic
$λ^{T} b$ and $ν^{T} d$ do not depend on $x$ . So they differentiate to zero

18.7.3 Solving for x

From $\nabla_{x} L = 0$ :

Q x = - (c + A^{T} λ + E^{T} ν)

If $Q$ is invertible (positive definite):

x = - Q^{- 1} (c + A^{T} λ + E^{T} ν)

This expresses the optimal $x$ in terms of the multipliers $λ$ and $ν$ . a key step for converting from primal (variables $x$ ) to dual (variables $λ, ν$ ).

18.7.4 From Primal to Dual

Formalize. Dual function. Substitute the expression $x = - Q^{- 1} (c + A^{T} λ + E^{T} ν)$ back into the Lagrangian. The resulting function $g (λ, ν)$ depends only on $λ$ and $ν$ :

g (λ, ν) = L (- Q^{- 1} (c + A^{T} λ + E^{T} ν), . λ, . ν)

The primal problem had $n$ variables (in $x$ ). The dual has $m + p$ variables (in $λ$ and $ν$ ). When the number of constraints $m + p$ is smaller than the number of primal variables $n$ , the dual is easier to solve.

The dual problem is then. maximize $g (λ, ν)$ subject to $λ \geq 0$ .

18.7.5 Primal vs Dual Relationship

Weak duality. For any feasible $x$ and any $λ \geq 0$ :

g (λ, ν) \leq f (x)

Why? The Lagrangian adds $λ^{T} (A x - b)$ to the objective. Since $A x - b \leq 0$ and $λ \geq 0$ , this term is $\leq 0$ . we are subtracting something. So $L (x, λ, ν) \leq f (x)$ . Since $g$ is the minimum of $L$ over $x$ , we have $g \leq L \leq f$ .

Strong duality. For convex QPs with Slater's condition, at the optimum:

g (λ^{*}, ν^{*}) = f (x^{*})

The primal and dual optimal values are equal. The dual curve rises to meet the primal at exactly the optimum.

Visual Intuition

Plot the objective value on the vertical axis against the feasible region on the horizontal. The primal function $f (x)$ is a convex curve. The dual function $g (λ)$ is a concave curve lying below it (weak duality). They touch at exactly one point. the optimum (strong duality). The gap between them is the duality gap, which shrinks to zero at optimality.

Pitfalls.

Forgetting the transpose in the gradient. $\nabla_{x} (λ^{T} A x) = A^{T} λ$ , not $A λ$ . The dimensions must work. $A^{T} λ$ is $n \times 1$ , matching the dimension of $Q x$ and $c$ .

Assuming $Q$ is always invertible. If $Q$ is only positive semi-definite (not strictly positive definite), $Q^{- 1}$ does not exist. The formula $x = - Q^{- 1} (c + A^{T} λ + E^{T} ν)$ fails. You need a different solution approach.

Mixing up inequality and equality multiplier signs. Inequality multipliers $λ$ must be $\geq 0$ . Equality multipliers $ν$ are unrestricted. If you restrict $ν \geq 0$ , you are solving a different problem.

Recap. The general QP Lagrangian $L = \frac{1}{2} x^{T} Q x + c^{T} x + λ^{T} (A x - b) + ν^{T} (E x - d)$ generalizes the single-variable case. Taking $\nabla_{x} L = 0$ gives $Q x + c + A^{T} λ + E^{T} ν = 0$ , which lets us eliminate $x$ and form the dual function $g (λ, ν)$ . The dual has $m + p$ variables instead of $n$ . often a significant reduction. Next (Section 18.8), we state the four KKT conditions in this matrix-vector notation.

Real-World & Domain Connection

This Lagrangian formulation is the mathematical engine inside every convex QP solver. When you call cvxopt.solvers.qp(Q, c, A, b) or use MATLAB's quadprog, the solver internally forms this Lagrangian, applies the KKT conditions. And solves the resulting linear system. The dual reduction ( $n \to m + p$ ) is what makes SVM training feasible when the feature dimension exceeds the number of data points. the dual has one variable per data point, not per feature.

18.8 KKT Conditions for the General QP

Hook. We stated the four KKT conditions for a single constraint in Section 18.2. Now we write them in the language of the general QP. matrices, vectors. And multiple constraints. The logic is identical. Only the notation changes.

For the general QP with optimal point $x^{*}$ and optimal multipliers $λ^{*}, ν^{*}$ , the four KKT conditions are:

18.8.1 Primal Feasibility (PF)

A x^{*} \leq b, E x^{*} = d

The optimal point must satisfy every original constraint. both inequality and equality. Component-wise. for each $i = 1, \dots, m$ , the $i$ -th row of $A$ dotted with $x^{*}$ is $\leq b_{i}$ . For each equality $j = 1, \dots, p$ , the $j$ -th row of $E$ dotted with $x^{*}$ equals $d_{j}$ .

18.8.2 Dual Feasibility (DF)

λ^{*} \geq 0

Every component of the inequality multiplier vector must be non-negative. Equality multipliers $ν^{*}$ are unrestricted. they can be positive, negative. Or zero.

18.8.3 Stationarity (SP)

\nabla_{x} L (x^{*}, λ^{*}, ν^{*}) = 0

Explicitly:

Q x^{*} + c + A^{T} λ^{*} + E^{T} ν^{*} = 0

The gradient of the Lagrangian vanishes at the optimum. This is the matrix-vector version of the balance-of-forces condition.

18.8.4 Complementary Slackness (CS)

λ_{i}^{*} \cdot (A_{i} x^{*} - b_{i}) = 0 for each inequality i = 1, \dots, m

For every inequality constraint individually, either the multiplier is zero (constraint inactive) or the constraint is tight. sits exactly on the boundary (constraint active). The product must be zero.

In vector form. $λ^{*} ⊙ (A x^{*} - b) = 0$ , where $⊙$ is element-wise multiplication (Hadamard product).

Pitfalls.

Forgetting equality constraints have no complementary slackness. Equality constraints are always active by definition ( $E x = d$ ). Their multipliers $ν$ are unrestricted. Do not write $ν ⊙ (E x - d) = 0$ . it would be directly true because $E x = d$ . And it is not part of KKT.

Treating the conditions as a "fill in the blanks" exercise. Each condition has a specific meaning. Primal feasibility = constraints hold. Dual feasibility = inequality multipliers are non-negative. Stationarity = gradient vanishes. Complementary slackness = active/inactive case split. Understand what each one checks.

Recap. The four KKT conditions in matrix form are the same four conditions from Section 18.2, scaled up to handle $n$ variables, $m$ inequality constraints. And $p$ equality constraints. PF. $A x \leq b, E x = d$ . DF. $λ \geq 0$ . SP. $Q x + c + A^{T} λ + E^{T} ν = 0$ . CS. $λ_{i} (A_{i} x - b_{i}) = 0$ for each $i$ . Next (Section 18.9), a fully worked two-variable QP example puts everything together. Lagrangian, stationarity, dual formation. And KKT verification.

Real-World & Domain Connection

When a convex QP solver reports "optimal solution found," it means it has found a point $(x^{*}, λ^{*}, ν^{*})$ that satisfies all four KKT conditions to within numerical tolerance. The solver iterates until the maximum violation of any KKT condition drops below $1 0^{- 8}$ or so. Checking KKT residuals is the standard way to verify that a candidate solution returned by a solver is actually optimal.

18.9 Worked Example 2 -- Two-Variable QP with Dual Formulation

Hook. Can you reduce a two-variable constrained problem to a one-variable unconstrained problem? Yes. by forming the Lagrangian, eliminating the primal variables. And solving the dual instead. This is the core trick that makes SVM training and portfolio optimization computationally feasible. Let us work through the full recipe.

18.9.1 Problem Statement

Minimize:

f (x_{1}, x_{2}) = \frac{1}{2} (x_{1}^{2} + x_{2}^{2})

Subject to:

x_{1} + x_{2} \geq 1

Symbol Registry:

Symbol	Meaning	Type	Domain
$x_{1}, x_{2}$	Decision variables	scalars	$R$
$f (x_{1}, x_{2})$	Objective. $\frac{1}{2} (x_{1}^{2} + x_{2}^{2})$	scalar	$R^{2} \to R$
$λ$	Lagrange multiplier	scalar	$λ \geq 0$
$L (x_{1}, x_{2}, λ)$	Lagrangian	scalar	$R^{3} \to R$
$g (λ)$	Dual function	scalar	$λ - λ^{2}$

18.9.2 Geometric Interpretation

Intuition. The objective $\frac{1}{2} (x_{1}^{2} + x_{2}^{2}) = \frac{1}{2} ∥ x ∥^{2}$ is half the squared distance from the origin. You are trying to find the point closest to the origin that lies on or above the line $x_{1} + x_{2} = 1$ .

Without the constraint, the minimum is at $(0, 0)$ with value 0. The constraint says you must be at least as far as that line. The constrained optimum will be the point on the line that is closest to the origin. the perpendicular projection of the origin onto the line.

18.9.3 Convert to Standard Form

The constraint $x_{1} + x_{2} \geq 1$ is a " $\geq$ " inequality. For the standard Lagrangian form with a plus sign, convert to $\leq$ form:

x_{1} + x_{2} \geq 1 ⟹ - (x_{1} + x_{2}) \leq - 1 ⟹ - x_{1} - x_{2} + 1 \leq 0

So $g (x) = - x_{1} - x_{2} + 1$ and the Lagrangian is:

L = f (x) + λ g (x) = \frac{1}{2} (x_{1}^{2} + x_{2}^{2}) + λ (- x_{1} - x_{2} + 1)

Equivalently, absorbing the minus sign:

L (x_{1}, x_{2}, λ) = \frac{1}{2} (x_{1}^{2} + x_{2}^{2}) - λ (x_{1} + x_{2} - 1)

Notation note. Some textbooks write $L = f (x) + λ g (x)$ with $g (x) \leq 0$ . others write $L = f (x) - λh (x)$ with $h (x) \geq 0$ . Both conventions produce the same result. The professor uses the second convention in this example. Pick one and stick with it throughout the exam.

18.9.4 Stationarity -- Find Critical Points

Formalize. Take partial derivatives of $L$ with respect to $x_{1}$ and $x_{2}$ , set both to zero:

\frac{\partial L}{\partial x _{1}} = x_{1} - λ = 0 ⟹ x_{1} = λ

\frac{\partial L}{\partial x _{2}} = x_{2} - λ = 0 ⟹ x_{2} = λ

At any stationary point, $x_{1} = x_{2} = λ$ . The two primal variables are expressed in terms of the single dual variable.

18.9.5 Form the Dual

Formalize. Substitution. Substitute $x_{1} = λ$ and $x_{2} = λ$ back into the Lagrangian:

L = \frac{1}{2} (λ^{2} + λ^{2}) - λ (λ + λ - 1) = \frac{1}{2} (2 λ^{2}) - λ (2 λ - 1) = λ^{2} - 2 λ^{2} + λ = λ - λ^{2}

The dual function is $g (λ) = λ - λ^{2}$ . The original primal had two variables $(x_{1}, x_{2})$ . The dual has one variable ( $λ$ ). We cut the problem size in half.

18.9.6 Maximize the Dual

Worked Example. Dual maximization. The dual problem. maximize $g (λ) = λ - λ^{2}$ subject to $λ \geq 0$ .

Take the derivative and set to zero:

g^{'} (λ) = 1 - 2 λ = 0 ⟹ λ = \frac{1}{2}

Second derivative check. $g^{''} (λ) = - 2 < 0$ . Since it is negative everywhere, the function is concave. this is a maximum.

The dual optimal point is $λ^{*} = \frac{1}{2}$ .

18.9.7 Compute Optimal Values

Dual optimal value:

g (\frac{1}{2}) = \frac{1}{2} - (\frac{1}{2})^{2} = \frac{1}{2} - \frac{1}{4} = \frac{1}{4}

Primal optimal point (back-substitute). $x_{1}^{*} = λ = \frac{1}{2}$ , $x_{2}^{*} = λ = \frac{1}{2}$ .

Primal optimal value:

f (\frac{1}{2}, \frac{1}{2}) = \frac{1}{2} ((\frac{1}{2})^{2} + (\frac{1}{2})^{2}) = \frac{1}{2} (\frac{1}{4} + \frac{1}{4}) = \frac{1}{2} \cdot \frac{2}{4} = \frac{1}{4}

Primal value = dual value = $\frac{1}{4}$ . Strong duality holds.

Sense-check. The point $(\frac{1}{2}, \frac{1}{2})$ lies exactly on the line $x_{1} + x_{2} = 1$ . The distance from the origin is $(\frac{1}{2})^{2} + (\frac{1}{2})^{2} = \frac{1}{2} = \frac{1}{2} \approx 0.707$ . The constraint value is $f = \frac{1}{4} = 0.25$ . No other point on or above the line can get closer to the origin.

18.9.8 Verify KKT Conditions

Primal Feasibility: $x_{1} + x_{2} = \frac{1}{2} + \frac{1}{2} = 1 \geq 1$ . ✓
Dual Feasibility: $λ = \frac{1}{2} \geq 0$ . ✓
Stationarity: Used to find $x_{1} = x_{2} = λ$ . ✓
Complementary Slackness: $λ \cdot (x_{1} + x_{2} - 1) = \frac{1}{2} \cdot (1 - 1) = \frac{1}{2} \cdot 0 = 0$ . ✓

All four conditions hold. The optimal solution is $(x_{1}^{*}, x_{2}^{*}) = (\frac{1}{2}, \frac{1}{2})$ .

18.9.9 Where the KKT Conditions Come From in This Problem

Each condition corresponds to a step in the solution:

Primal feasibility: the constraint $x_{1} + x_{2} \geq 1$ . the optimum sits exactly at equality.
Dual feasibility: the multiplier is $λ = \frac{1}{2} > 0$ . valid.
Stationarity: $\nabla L = 0$ gave $x_{1} = λ$ and $x_{2} = λ$ .
Complementary slackness: because the constraint is active ( $x_{1} + x_{2} = 1$ ), the product $λ \cdot 0 = 0$ vanishes regardless of $λ$ 's value.

18.9.10 The Full Solution Format

The exam recipe for any QP problem:

Write the Lagrangian (convert constraints to standard form).
Apply stationarity ( $\nabla L = 0$ ) to express $x$ in terms of multipliers.
Substitute back to form the dual function $g (λ, ν)$ .
Maximize (or minimize) the dual to find optimal multipliers.
Back-substitute to get primal optimal point $x^{*}$ .
Verify primal/dual values are equal (strong duality).
Verify all four KKT conditions at the candidate point.

18.9.11 Student Questions and Answers

Q: Is it possible that any KKT condition will not be satisfied after doing all these steps?

A: Yes, if the surface is non-convex, some KKT conditions may fail. But for the convex QP problems in this course (and on exams), KKT conditions will hold at the optimum.

Q: Several students asked. When writing the Lagrangian, some sources use $f (x) + λ g (x)$ and others use $f (x) - λ g (x)$ . Which is correct?

A: The standard form is $L = f (x) + λ g (x)$ with $g (x) \leq 0$ . If your constraint is $x_{1} + x_{2} \geq 1$ , convert it. multiply by $- 1$ to get $- x_{1} - x_{2} \leq - 1$ . So $g (x) = - x_{1} - x_{2} + 1 \leq 0$ . Then $L = f (x) + λ (- x_{1} - x_{2} + 1)$ . This is identical to $L = f (x) - λ (x_{1} + x_{2} - 1)$ . Both are the same equation. Pick one convention and be consistent.

Q: Why is it called "primal" and "dual"?

A: Primal = the original minimization problem you face. Dual = the same problem viewed from a different angle, usually as a maximization. The primal looks at minimizing from below. the dual looks at maximizing from above. They meet at the same optimal point. The dual reduces the number of variables (here from 2 to 1), making it easier to solve.

Q: After finding $λ = \frac{1}{2}$ , do we always need to compute the primal value?

A: Here we computed it to show strong duality (primal = dual). In an exam, the dual is often the easier route. Solve the dual first, then back-substitute to get primal variables and value.

Q: So KKT conditions are just an extension of Lagrange multipliers we already know?

A: Exactly. Stationarity is the same gradient-zero step you have been doing. KKT formalizes the remaining three checks (primal feasibility, dual feasibility, complementary slackness) as a named checklist.

Pitfalls.

Sign convention mistakes. With a " $\geq$ " constraint, you must either convert to " $\leq$ " (multiply by $- 1$ ) OR absorb the minus into the Lagrangian as $- λh (x)$ . Mixing the two approaches mid-problem leads to wrong signs for $λ$ .

Forgetting the dual feasibility range. The dual is maximized over $λ \geq 0$ . If you treat $λ$ as unrestricted and maximize $λ - λ^{2}$ over all $R$ , you still get $λ = \frac{1}{2}$ , which happens to be valid. But in other problems, the unrestricted maximum might give a negative $λ$ . always check $λ \geq 0$ .

Not verifying complementary slackness explicitly. Even though the product $λ \cdot (x_{1} + x_{2} - 1) = 0$ is "obvious" once you have $x_{1} + x_{2} = 1$ , exams expect you to write it out.

Recap. The two-variable QP example shows the full primal-to-dual pipeline. Lagrangian → stationarity → dual function → dual maximization → back-substitution → KKT verification. The dual reduced 2 variables to 1. Strong duality confirmed the answer. Next (Section 18.10), we see how this same mathematics powers real-world scheduling problems.

Real-World & Domain Connection

The primal-to-dual reduction showed here is the exact mechanism that makes SVM training feasible. In SVM, the primal has as many variables as features (which can be millions in NLP). But the dual has one variable per training data point. often much smaller. The same dual trick enables portfolio optimization (covariance matrix as $Q$ , budget constraints as $A x = b$ ) and model predictive control (minimizing control effort subject to actuator limits).

18.10 Real-World Quadratic Programming Application

Hook. Constrained optimization is not just theory. Every day, cloud providers, airlines, logistics companies. And hedge funds solve quadratic programs to make billion-dollar decisions. The KKT conditions you just learned are what guarantee those solutions are correct.

18.10.1 Cloud Upgrade Scheduling

Intuition. You manage hundreds of customer pods that need software upgrades. Each customer has time-window restrictions. banking customers can only be upgraded Friday at 7 PM US time, retail customers monthly on Saturday at 10 PM, some cannot be upgraded in April or May. And you have a resource cap. at most 20 upgrades per month.

The goal is to schedule all upgrades in minimum total time while respecting every constraint. This is a constrained optimization problem. Each constraint violation incurs a penalty, exactly like the $λ \cdot g (x)$ terms in the Lagrangian.

Worked Example. Scheduling as QP. Simplify to a small case. You have 3 pods $(P_{1}, P_{2}, P_{3})$ and 2 time slots $(T_{1}, T_{2})$ . Each pod $j$ takes $t_{j}$ hours. You want to minimize total time.

Decision variable $x_{ij} = 1$ if pod $i$ is scheduled in slot $j$ , else 0.
Objective. minimize $\sum_{i} \sum_{j} t_{i} \cdot x_{ij}$ (total upgrade hours).
Constraint 1 (one slot per pod). $\sum_{j} x_{ij} = 1$ for each pod $i$ .
Constraint 2 (capacity). $\sum_{i} x_{ij} \leq 20$ per slot $j$ .
Constraint 3 (time windows). $x_{i, Friday 7PM} = 0$ for non-banking customers.

Integer programming extension. $x_{ij} \in {0, 1}$ makes this a mixed-integer QP. But the constraints are linear. The Lagrange multipliers $λ$ penalize capacity violations. complementary slackness ensures only slots at capacity get non-zero penalties.

Sense-check. At the optimal schedule, the only constraints that matter are the ones at their limits. slots that are full and pods whose time windows are the most restrictive. All other constraints have zero multipliers and contribute nothing to the optimality conditions.

Visual Intuition

Picture a Gantt chart with time on the horizontal axis and pods on the vertical axis. Each pod is a horizontal bar spanning its upgrade window. Constraints are vertical lines (capacity limits) and shaded forbidden zones (time-window restrictions). The optimal schedule packs as many bars as possible into the allowed zones without crossing vertical lines. The Lagrange multipliers measure the "pressure" at each capacity boundary.

Assumptions &. Scope.

Integer constraints. Real scheduling problems involve binary decisions (upgrade or not), which makes them integer programs. harder than continuous QPs. But the Lagrangian relaxation framework still applies. you relax the integer constraints, solve a continuous QP. And round.
Scalability. With hundreds of pods, the QP has thousands of variables. Specialized solvers (Gurobi, CPLEX) use interior-point methods and exploit problem structure (sparse constraints, block-diagonal $Q$ ).

Recap. Real-world scheduling is a constrained optimization problem. The Lagrangian penalty terms $λ \cdot g (x)$ model the cost of violating constraints. Complementary slackness identifies which constraints are binding at the optimum. the ones you actually need to worry about. Next (Section 18.11), we see how the same QP machinery powers Support Vector Machines.

Q: How do you represent crossing a constraint with a penalty in equation form?

A: The Lagrangian penalty term $λ \cdot g (x)$ does exactly this. When a constraint is violated ( $g (x) > 0$ ), the penalty $λ \cdot g (x)$ is positive and increases the objective value, making that point less desirable. The magnitude of $λ$ controls how harshly the violation is penalized. At the optimum, complementary slackness ( $λ \cdot g (x) = 0$ ) ensures that the penalty term contributes nothing. either the constraint is satisfied ( $g (x) \leq 0$ with $λ = 0$ ) or the point sits exactly on the boundary ( $g (x) = 0$ ). This mechanism is how constrained optimization handles constraint crossings without needing "if-then" logic in the solver.

Real-World & Domain Connection

Beyond cloud scheduling, QP scheduling appears in airline crew rostering (minimize costs subject to FAA rest rules), hospital nurse scheduling (coverage constraints per shift), manufacturing job-shop scheduling (machine capacity constraints). And even exam timetabling (room capacity, no student double-booking). The mathematical structure. minimize quadratic cost + linear penalties subject to linear constraints. is universal.

18.11 Introduction to Support Vector Machines (SVM)

Hook. You have spent the entire lecture learning KKT conditions and quadratic programming. Now here is why. the Support Vector Machine. one of the most successful classifiers in machine learning. is nothing more than a convex QP. Every KKT concept you have mastered directly explains how SVMs work and why they find the globally optimal decision boundary.

18.11.1 Linear Decision Boundaries

Intuition + Analogy. Imagine two neighborhoods. Red Town and Blue Town. on a map. You need to build a straight road between them that puts every red house on one side and every blue house on the other. That road is called a decision boundary. Both logistic regression and SVM draw such lines. The difference is which line they pick.

Analogy. The widest street. An SVM tries to build the widest possible street between the two neighborhoods. The road itself is the decision boundary. The sidewalks on each side are margins. Only the houses sitting right on the sidewalks matter. those are the support vectors. Move those houses. And the road shifts. Move any other house. And nothing changes.

Symbol Registry

Symbol	Meaning	Type	Domain
$w$	Weight vector (hyperplane normal)	vector	$R^{d}$
$∥ w ∥$	Euclidean norm (length) of $w$	scalar	$∥ w ∥ \geq 0$
$b$	Bias term	scalar	$R$
$α_{i}$	Dual multiplier for data point $i$	scalar	$α_{i} \geq 0$
$y_{i}$	Class label for data point $i$	scalar	$y_{i} \in {- 1, + 1}$
$x_{i}$	Feature vector for data point $i$	vector	$R^{d}$
$C$	Soft-margin penalty constant	scalar	$C > 0$

18.11.2 The Problem with Many Possible Lines

Given two well-separated clusters, infinitely many lines can separate them. Logistic regression picks one by maximizing likelihood. SVM picks one by maximizing the margin. the gap between the closest points of each class and the boundary. A wider margin means a more confident, more robust classifier.

18.11.3 Support Vectors and Margin Maximization

Formalize. SVM finds the widest street separating two classes:

Identify the closest points from each class to the opposite class. the support vectors.
Draw two parallel hyperplanes through the support vectors of each class.
Place the decision boundary exactly midway between them.
Maximize the distance between the two hyperplanes.

The margin width is:

margin = \frac{2}{∥ w ∥}

Maximizing $\frac{2}{∥ w ∥}$ is equivalent to minimizing $∥ w ∥$ . And squaring (monotonic for positive numbers) gives the familiar QP objective:

Minimize \frac{1}{2} ∥ w ∥^{2}

18.11.4 The Connection to Quadratic Programming

SVM is a QP. Compare:

SVM objective. $\frac{1}{2} ∥ w ∥^{2} = \frac{1}{2} w^{T} I w$
QP standard form. $\frac{1}{2} x^{T} Q x + c^{T} x$

Here $x = w$ , $Q = I$ (the identity matrix). And $c = 0$ . The constraints are $y_{i} (w^{T} x_{i} + b) \geq 1$ for each data point $i$ . linear in $w$ .

Because $Q = I$ is positive definite, the SVM problem is convex. There is exactly one global minimum. Any solver (gradient descent, SMO, dual QP solver) will converge to it.

18.11.5 The Dual SVM Problem

From primal to dual. Just like in Section 18.9, the primal SVM can be converted to a dual. The dual uses multipliers $α_{i}$ (one per data point, replacing $λ$ ) and becomes:

α max i \sum α_{i} - \frac{1}{2} i \sum j \sum α_{i} α_{j} y_{i} y_{j} (x_{i}^{T} x_{j})

subject to $α_{i} \geq 0$ and $\sum_{i} α_{i} y_{i} = 0$ .

The primal had $d$ variables (one per feature). The dual has $N$ variables (one per data point). When the number of features exceeds the number of data points, the dual is far more efficient.

Crucially, the dual depends only on dot products $x_{i}^{T} x_{j}$ between data points. This enables the kernel trick. replace the dot product with a kernel function $K (x_{i}, x_{j})$ and you get a nonlinear classifier without ever leaving the QP framework.

18.11.6 Why SVM Can Be Slow

The dual involves an $N \times N$ matrix of dot products. Training time grows quadratically with dataset size. With 100,000 data points, that is a 10-billion-entry matrix. SVM training can take as long as (or longer than) training a neural network on the same data. The QP solver is the bottleneck.

18.11.7 When Data Is Not Linearly Separable

Real data has noise. Red points land in the green zone and vice versa. Two strategies handle this:

Soft-margin SVM: Allow misclassifications by adding a penalty term. The objective becomes:

\frac{1}{2} ∥ w ∥^{2} + C n \sum ξ_{n}

where $ξ_{n} \geq 0$ is the slack for data point $n$ . And $C$ trades off margin width against classification errors. This is directly analogous to adding $λ \cdot g (x)$ penalty terms in constrained optimization.

Kernel trick: Map data to a higher-dimensional space where a linear separator exists. In 2D, concentric circles are not separable by a line. But lift the inner circle into the third dimension. suddenly a plane slices between them. The kernel trick computes high-dimensional dot products without ever constructing the high-dimensional coordinates. It is one of the most elegant ideas in machine learning.

18.11.8 Preview of Next Topics

The remaining SVM material (in subsequent lectures) covers:

Deriving the primal SVM, converting to dual, proving it is a QP with strong duality.
Soft-margin SVM with penalty for misclassification ( $ξ$ variables).
The kernel trick. replacing dot products with kernel functions for nonlinear classification.

18.11.10 Student Questions and Answers

Q: If the data is not linearly separable (outliers, one red point in the green area), can SVM handle that?

A: A hard-margin linear SVM cannot. it finds no clean separating hyperplane. But soft-margin SVM handles this by allowing some misclassifications with a penalty ( $ξ$ variables and the $C$ constant). Kernel SVM handles more complex nonlinear patterns by projecting to higher dimensions where a linear separation becomes possible. Low-dimensional nonlinearity becomes high-dimensional linearity.

Q: Is it not computationally expensive to project data into higher dimensions?

A: It would be, if done naively. The kernel trick makes it cheap. you compute dot products in the high-dimensional space without ever constructing the high-dimensional coordinates. The math simplifies dramatically. This is the "trick" in the kernel trick.

Q: Is the dual always easier to solve than the primal?

A: Not always. But often yes. The dual reduces the number of variables when the number of constraints is smaller than the number of primal variables. In SVM, the dual transforms from minimizing over $w$ (dimension = number of features) to maximizing over $α$ (dimension = number of data points $N$ ). When $N < d$ (more features than examples), the dual is more efficient. When $N > d$ , the primal may be faster.

Pitfalls.

Thinking SVM is a neural network. SVM is a linear classifier with a clever margin-maximization objective. It is not a deep learning model. It solves a convex QP, not a non-convex neural network optimization.

Confusing hard-margin SVM with soft-margin. Hard-margin requires perfectly separable data and produces no solution otherwise. In practice, always use soft-margin (with $C$ ) unless you are certain the data is clean.

Overlooking the QP connection. The SVM objective $\frac{1}{2} ∥ w ∥^{2}$ is the exact same form as $\frac{1}{2} x^{T} Q x$ . Everything you learned about QP optimality, KKT conditions. And duality applies directly. Complementary slackness identifies support vectors. data points with $α_{i} > 0$ .

18.11.9 Practical Note

Recap. SVM is a convex QP that finds the maximum-margin linear separator. The dual formulation reduces the number of variables and enables the kernel trick. Complementary slackness identifies support vectors. the only data points that matter. SVM training can be as slow as neural network training because of the QP solve over all data points.

Real-World & Domain Connection

SVMs dominated text classification throughout the 2000s. spam filters, sentiment analysis. And document categorization all used linear SVMs with bag-of-words features. In bioinformatics, SVMs classify gene expression profiles to identify cancer subtypes. In computer vision (pre-deep-learning era), SVMs with histogram-of-gradient features were state-of-the-art for pedestrian detection. The dual formulation and kernel trick remain foundational ideas, directly influencing modern kernel methods and Gaussian processes.

Exam Guidance Summary

Exam note: Expect a question requiring you to justify all four KKT conditions for a given minimization problem with constraints. Or to verify that a candidate point satisfies KKT.

QP problems on the exam will typically be two-variable cases like. minimize $x_{1}^{2} + x_{2}^{2}$ subject to a single linear constraint.

Exam note: The full solution format for a QP exam problem is:

Write the Lagrangian (convert constraints to the appropriate sign convention).
Apply stationarity ( $\nabla L = 0$ ) to relate $x$ and the multipliers.
Substitute to form the dual.
Maximize the dual to get the optimal multipliers.
Back-substitute for the primal variables.
Verify primal feasibility, dual feasibility. And complementary slackness.
Conclude that the point is optimal.

Sometimes you may only be given a candidate point and asked to verify that KKT conditions hold. In that case, skip the solving steps and directly check all four conditions at the given point.

Exam note: For SVM, understand that minimizing $\frac{1}{2} ∥ w ∥^{2}$ is a quadratic program with $Q = I$ . Complementary slackness identifies which data points become support vectors. Know the dual formulation.

Complementary slackness is critical. it is the mechanism that enables the case-splitting approach to KKT problem solving. And it identifies support vectors in SVM.

Key Industry Applications

Cloud infrastructure scheduling: Minimizing total upgrade time for hundreds of customer pods subject to temporal and resource constraints. This is a constrained optimization problem where penalties for constraint violations are directly modeled by Lagrangian penalty terms $λ \cdot g (x)$ .

Support Vector Machines (SVM): Classification via margin maximization. The primal SVM objective $\frac{1}{2} ∥ w ∥^{2}$ is a quadratic form ( $\frac{1}{2} x^{T} Q x$ with $Q = I$ ), making SVM a convex QP with guaranteed global optimality. Used extensively in text classification, bioinformatics. And image recognition. The dual formulation enables the kernel trick for nonlinear classification.

Portfolio optimization: QP is the standard framework for minimizing portfolio risk with return constraints. The objective $\frac{1}{2} x^{T} Q x + c^{T} x$ uses the covariance matrix as $Q$ . PSD by construction, guaranteeing convexity. Returns are captured by linear constraints $c^{T} x \geq r_{target}$ .

Logistic regression vs SVM: Both produce linear decision boundaries. SVM maximizes the margin for robust classification. logistic regression maximizes likelihood and provides calibrated probability estimates. SVM performs well on clean, well-separated data. Logistic regression is preferred when probability outputs are needed.