Constrained Optimization and Duality

Ordinary unconstrained optimization — gradient descent, Newton's method — assumes you can move freely in any direction. The real world rarely works that way. A loan model might need all its coefficients positive. A portfolio cannot invest negative dollars. An SVM must keep every data point on the right side of a margin. These are constraints, and they change the game entirely.

This lecture builds the mathematical machinery for handling constraints. Converting them into penalty terms, trading off between primal and dual formulations. And understanding why sometimes the dual is easier to solve than the primal. The core ideas — Lagrange multipliers, duality, complementary slackness. Form the backbone of modern convex optimization and reappear throughout machine learning.

15.1 Linear and Quadratic Programming

15.1.1 Symbol Registry — Linear and Quadratic Programming

15.1.2 Linear Programming

A simple linear program:

$$\begin{array}{r}\text{minimize}\&x+4y\\ \text{subject to}\&x\ge 3\\ \&y<8\end{array}$$

The objective $x+4y$ is linear (no powers, no products of variables). Both constraints are linear. The problem asks for values of $x$ and $y$ that make $x+4y$ as small as possible without breaking any rule. The feasible region: $x$ from 3 upward, $y$ up to (but not including) 8. The minimum occurs at the tightest corner: $x=3$, $y$ as small as possible. With no lower bound on $y$, the minimum is pushed to $y\to -\infty$, making the problem unbounded below. This is why real-world LPs always have bounded domains.

Linear programs are solved with the simplex method (moves vertex to vertex) or interior-point methods (cuts through the middle). You may have seen these in operations research courses.

Visual intuition: Plot the constraints on an $xy$-plane. Each inequality is a half-plane. Their intersection is the feasible polygon. Overlay the objective $x+4y$ as parallel level lines. Slide the line perpendicular to its gradient direction until it just touches the polygon. That touching point is the optimum. For a minimization, you slide in the direction opposite to the gradient $(1,4)$.

15.1.3 Quadratic Programming

A single-variable quadratic program:

$$\begin{array}{r}\text{maximize}\&x^2\\ \text{subject to}\&x\le 4\end{array}$$

The objective $x^2$ is nonlinear (quadratic), and the constraint is linear. This counts as QP because something in the problem is nonlinear. A richer two-variable example:

$$\begin{array}{r}\text{minimize}\&x-4y\\ \text{subject to}\&x^2+y^2\le 8\\ \&x+y\le 4\end{array}$$

The first constraint is nonlinear (a disk of radius $\sqrt{8}$). The second constraint and the objective are linear. Because a nonlinear part appears somewhere, this is quadratic programming.

15.1.4 Why Study Constrained Optimization?

Constrained optimization connects to two critical areas in machine learning:

1. L1 and L2 regularization (Lasso and Ridge regression). The L1 constraint region is a diamond; the L2 constraint region is a circle. These shapes explain why L1 produces sparse solutions (coefficients exactly zero). The sharp corners of the diamond touch the axes at points where variables are zero. L2's smooth circle rarely touches an axis, so coefficients are small but rarely exactly zero.

1. Support Vector Machines (SVM) — a classification algorithm that relies heavily on constrained optimization. You solve the dual of SVM rather than the primal because. (a) the dual depends on the number of data points, not the feature dimension. And (b) the dual is always convex, making it solvable with guarantees. Understanding primal and dual is the prerequisite for SVM.

Real-World & Domain Connection. Linear programming powers supply chain logistics. Companies like Amazon and FedEx solve massive LPs daily to route millions of packages through warehouses and delivery trucks. Minimizing cost while respecting capacity constraints. Quadratic programming drives Markowitz portfolio optimization in finance. Where the objective is a quadratic risk term (variance) and constraints are linear budget limits. Together, LP and QP form the computational backbone of operations research. With applications spanning airlines scheduling crews, factories planning production, and power grids balancing load.

15.2 Lagrangian Formulation

15.2.1 The Penalty Parameter Concept

Start with a simple constrained problem:

$$\begin{array}{r}\text{minimize}\&f(x)=x^2\\ \text{subject to}\&x\ge 2\end{array}$$

Without the constraint, the minimum of $x^2$ is 0 at $x=0$. With $x\ge 2$, the smallest allowed $x$ is 2, so $f(2)=4$ is the constrained minimum. The constraint cuts off part of the domain.

The solution: convert the constrained problem into an unconstrained one using the Lagrangian. Add each constraint directly into the objective, multiplied by a penalty parameter.

15.2.2 Symbol Registry

15.2.3 Worked Case 1 — Invalid $x$

15.2.4 Worked Case 2 — Valid $x$

15.2.5 Two-Player Game Intuition

Analogy 1 — Park and inspector: You roam in a fenced park. Inside the fence, no problem. Step outside and an inspector (Lambda) charges you any fine they want. They want to maximize the fine. You, wanting to minimize your cost, stay inside.

Analogy 2 — Pill maker: You want to minimize your food cost while meeting calorie needs. A pill maker sets a pill price. The pill maker wants to maximize the pill price. But they cannot exceed your minimum food cost — or you would just buy food. The pill maker sees your choices and sets the price accordingly to extract maximum profit without driving you to food.

Analogy 3 — Chef and spicy food (turn order matters): You order three dishes but cannot handle spice. The chef, wanting to maximize spiciness, makes all three dishes as spicy as possible. If instead the chef chooses dishes first and you pick the least spicy, you have the advantage. The player who goes first is at a disadvantage — the opponent can respond optimally.

Visual Intuition: Picture a bowl-shaped surface (the objective). Cut a vertical cylinder through it (the feasible region). The Lagrangian is like wrapping a rubber sheet over the bowl. The sheet is pulled down by the bowl but pushed up by Lambda wherever the constraint boundary is crossed. At the optimum, the sheet touches the bottom of the bowl right at the edge of the cylinder. The pull of the bowl (gradient of $f$) and the push of the constraint (gradient of the penalty) balance perfectly. That is $\nabla f=\lambda \nabla g$, the fundamental Lagrange multiplier equation.

Real-World & Domain Connection. The Lagrangian formulation was invented by Joseph-Louis Lagrange in 1788 for mechanical systems. But it found its true home in economics and optimization theory. Today, Lagrangian duality underpins every SVM library (libsvm, sklearn.svm), resource allocation in cloud computing (Google's Borg scheduler). Structural engineering (minimum-weight truss design under stress constraints), and optimal control in robotics (trajectories that respect joint limits).

15.3 Primal and Dual Problems

15.3.1 Deriving the Dual

Take the Lagrangian from the previous section:

$$\mathcal{L}(x,\lambda )=x^2+2\lambda -\lambda x$$

15.3.2 Symbol Registry for Duality

15.3.3 Strong vs Weak Duality

Picture the primal surface as a bowl. The dual function lives below it. At the strong-duality point, the dual touches the primal at its minimum. Everywhere else there is a gap — the dual sits strictly below. If you choose any $\lambda$ other than the strong-duality point, the dual value is always below the primal surface. This gap is the duality gap.

What does strong duality prove? The opponent's best possible penalty, when you stay within the feasible region, equals your minimum cost. The best Lambda can do is meet you at your own minimum. Lambda cannot extract more than the natural cost of the problem.

15.3.4 The Min-Max Inequality

15.3.5 Visual Intuition with a 2D Constrained Region

Visual Intuition: Imagine an elliptical bowl sitting on a table. Its deepest point is at $(0,0)$. Now cut two parallel vertical walls through the bowl — at $x+y=1$ and $x+y=2$. The floor between the walls is the feasible band. Since the deepest point is outside the band, the ball rolls until it hits the nearest wall and stops there. The optimum is the point on the boundary $x+y=1$ closest to $(0,0)$. Found by projecting $(0,0)$ onto the line $x+y=1$.

A visualization from the class: change $\lambda$ and watch the dual function trace an inverted parabola. As $\lambda$ increases from 0, the dual function rises in a parabola. At the optimal $\lambda$, the dual's maximum touches the primal's constrained minimum — this is strong duality. For all other $\lambda$, the dual sits below the primal, and the vertical distance between them is the dual gap.

Real-World & Domain Connection. Duality theory underpins auction design. The Google AdWords auction runs a dual linear program billions of times a day. In mechanism design (Nobel Prize-winning work), the primal is maximizing social welfare and the dual reveals the optimal prices. In machine learning, the dual of SVM lets you replace explicit high-dimensional features with kernel functions. Which is the entire reason SVMs work on non-linear data without exploding compute costs.

15.4 Solving Constrained Optimization Problems

15.4.1 The Lagrange Multiplier Method

15.4.2 Symbol Registry for This Section

15.4.3 Worked Example 1 — Equality Constraint

15.4.4 Worked Example 2 — Nonlinear Constraint

15.4.5 Converting Primal to Dual — Two Constraints

Q: For each constraint, do we find a separate dual function? Or one dual with multiple Lambda parameters? A: One dual function with multiple Lambda parameters. With $k$ constraints, the Lagrangian has $k$ multipliers: ${\lambda }_1,\dots ,{\lambda }_k$. After substituting back, the dual $g({\lambda }_1,\dots ,{\lambda }_k)$ is a function of all $k$ multipliers. Solve for them simultaneously using the constraint equations.

Q: With two constraints like $x+y\le 2$ and $x+y\ge 1$, how do you set up both? A: Convert both to $\le 0$ form. $x+y\le 2$ becomes $x+y-2\le 0$ (multiplier ${\lambda }_1$). $x+y\ge 1$ becomes $1-x-y\le 0$ (multiplier ${\lambda }_2$). The Lagrangian is $\mathcal{L}=x^2+y^2+{\lambda }_1(x+y-2)+{\lambda }_2(1-x-y)$. Take $\partial \mathcal{L}/\partial x$ and $\partial \mathcal{L}/\partial y$, solve for $x,y$ in terms of ${\lambda }_1,{\lambda }_2$, then use the two constraint equations to find ${\lambda }_1,{\lambda }_2$. At the optimum, complementary slackness makes both inequalities equalities when both constraints are active.

Real-World & Domain Connection: The five-step Lagrange multiplier method is the engine inside every SVM solver. When libsvm or sklearn's SVC runs, it is executing exactly these steps. Forming the Lagrangian of the SVM primal, substituting stationarity conditions, and solving the resulting dual QP. The same method appears in constrained portfolio optimization (minimize risk subject to target return). Structural engineering (minimize material weight subject to stress limits). And optimal power flow in electrical grids (minimize generation cost subject to voltage and thermal limits).

15.5 Complementary Slackness — Introduction

15.5.1 Symbol Registry — Complementary Slackness

15.5.2 The Core Idea

Why it is needed. The complementary slackness condition, together with primal feasibility ($g_i(\mathbf{x})\le 0$). Dual feasibility (${\lambda }_i\ge 0$), and stationarity (${\nabla }_{\mathbf{x}}\mathcal{L}=0$), form the four KKT (Karush-Kuhn-Tucker) conditions. For convex problems, the KKT conditions are necessary and sufficient for optimality. Satisfy all four and you have found the global optimum.

15.5.3 Connecting to Earlier Examples

At the strong-duality point, when you are fully inside the feasible region, $\lambda =0$ and the penalty vanishes. This matches the valid-$x$ case from Section 15.2. Where $x=3$ satisfied $x\ge 2$ with slack $(g(x)=2-3=-1<0)$, and the optimal $\lambda$ was forced to zero. Complementary slackness was at work: $g(x)<0\Rightarrow \lambda =0$.

When you press against a constraint boundary, $\lambda >0$ and $g_i(\mathbf{x})=0$. This is why, when solving problems with inequalities, you replace them with equalities at the optimum. You are applying complementary slackness even before formally learning its name. If a constraint is active, treat it as an equality.

15.5.4 What Comes Next

The full theory of complementary slackness, together with KKT (Karush-Kuhn-Tucker) conditions, gets covered in the next lecture. The KKT conditions are the formal framework that includes four components:

1. Stationarity: ${\nabla }_{\mathbf{x}}\mathcal{L}=0$ — the gradient of the Lagrangian vanishes.
2. Primal feasibility: $g_i(\mathbf{x})\le 0$ — all constraints satisfied.
3. Dual feasibility: ${\lambda }_i\ge 0$ — all multipliers nonnegative.
4. Complementary slackness: ${\lambda }_i\cdot g_i(\mathbf{x})=0$ — at most one slacks per pair.

15.5.5 Worked Connection — Nonlinear Constraint Revisited

Visual Intuition: Think of watching the optimum point $(1,1)$ on the circle's boundary. If you slowly inflate the circle (relax the constraint). The point moves outward along the ray $(1,1)$ direction, and the objective $-x-y$ decreases. The rate of decrease is $\lambda =1/2$ per unit of radius. If you deflate the circle (tighten the constraint). The optimum moves inward and the objective value increases (gets worse for the minimization). The multiplier is the instantaneous rate of change of the optimal value with respect to the constraint bound.

Real-World & Domain Connection. Complementary slackness appears in economics as the concept of shadow prices. The Lagrange multiplier is the marginal value of relaxing a resource constraint by one unit. In SVM, the complementary slackness condition identifies the support vectors. Data points with ${\lambda }_i>0$ are the ones that define the margin. Points with ${\lambda }_i=0$ are irrelevant to the decision boundary and could be dropped without changing the classifier. This is why SVMs are sparse — most training points end up with ${\lambda }_i=0$ and contribute nothing.

15.6 Connection to Support Vector Machines

15.6.1 Symbol Registry — SVM Context

15.6.2 Why SVM Uses the Dual

Three reasons the dual beats the primal for SVM:

1. Dimensionality: The primal has $d$ variables (feature dimension). The dual has $m$ variables (number of data points). When $m\ll d$, the dual is much smaller. With the kernel trick, $d$ can be infinite while $m$ stays finite — the dual is the only tractable approach.

1. Convexity: The primal SVM can be non-convex in the original space, especially with nonlinear feature maps. But the dual is always convex — a quadratic maximization problem with a positive semidefinite kernel matrix. You can always solve a convex problem reliably. At strong duality, the dual's maximum equals the primal's minimum. So maximizing the convex dual is equivalent to minimizing the non-convex primal.

1. Kernel compatibility: The dual is expressed entirely in terms of dot products ${\mathbf{x}}_i\cdot {\mathbf{x}}_j$. This is what makes the kernel trick possible. Replacing the dot product with a kernel function $K({\mathbf{x}}_i,{\mathbf{x}}_j)$ that computes the dot product in high-dimensional space without ever going there. The primal form cannot use the kernel trick because it operates on individual weight components $w_k$, not dot products.

Visual Intuition: Picture an SVM problem in the primal space. The decision boundary might be a complex curved surface. Each Lagrange multiplier ${\alpha }_i$ in the dual tells you which data points are support vectors. The ones that define the boundary:

• ${\alpha }_i=0$: the point is correctly classified, far from the margin. It contributes nothing to the boundary. Complementary slackness in action.
• ${\alpha }_i>0$: the point is on or inside the margin. It actively shapes the boundary. These points are literally supporting the decision hyperplane.

The decision function becomes $f(\mathbf{x})=\text{sign}\left({\sum }_i{\alpha }_i{y}_{i}K({\mathbf{x}}_i,\mathbf{x})+b\right)$. Only support vectors (${\alpha }_i>0$) matter in the sum.

15.6.3 Dot Products and the Kernel Trick — Preview

Q: In SVM, are the objectives the ones we want to achieve, and the constraints the separating planes? A: The primal SVM objective is to maximize the margin (equivalently, minimize $\frac{1}{2}\Vert w{\Vert }^2$) while classifying all points correctly. The constraints $y_i(w\cdot x_i+b)\ge 1$ ensure every point lies on the correct side of the margin boundary. The dual reformulates everything in terms of Lagrange multipliers ${\alpha }_i$. Solving the primal directly is hard because of possible non-convexity and high dimensionality. The dual, being convex and kernel-compatible, is the practical approach.

Q: How does the regularization parameter $C$ (not $\lambda$ in SVM convention) affect the decision boundary in SVM? A: In the soft-margin SVM primal, the objective is $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i{\xi }_i$, where ${\xi }_i$ are slack variables allowing misclassification. A large $C$ heavily penalizes violations → narrow margin, few misclassifications, risk of overfitting. A small $C$ tolerates violations → wide margin, more misclassifications, better generalization. In the dual, $C$ appears as an upper bound on the Lagrange multipliers: $0\le {\alpha }_i\le C$. This box constraint directly limits each point's influence on the boundary. Points with ${\alpha }_i=C$ are misclassified or inside the margin. Points with $0<{\alpha }_i<C$ are correctly on the margin (support vectors); points with ${\alpha }_i=0$ are correctly classified outside the margin.

Q: Is the dot product the same as cosine distance? How are they related? A: The dot product sums component-wise products: $\mathbf{a}\cdot \mathbf{b}=a_1{b}_1+a_2{b}_2+\cdots$. Cosine similarity normalizes this: $\cos \theta =\frac{\mathbf{a}\cdot \mathbf{b}}{\Vert \mathbf{a}\Vert \Vert \mathbf{b}\Vert }$. The dot product captures both magnitude and direction; cosine captures only direction (values in $[-1,1]$). In SVM, the dual formulation uses dot products because it is the natural quantity that appears when substituting the stationarity conditions. The kernel trick extends dot products to nonlinear feature spaces, enabling SVMs to learn complex boundaries.

Real-World & Domain Connection. SVMs powered the first generation of handwritten digit recognition systems (USPS postal code readers in the 1990s). Face detection in digital cameras, and gene expression classification in bioinformatics. The kernel trick, specifically. Made it possible to classify non-linear patterns (like a circle of one class surrounding another) without explicitly constructing high-dimensional feature spaces. Modern large-scale systems often prefer neural networks. But SVMs remain the gold standard for small-to-medium datasets where interpretability (knowing exactly which points define the boundary) matters. Medical diagnosis, fraud detection, and any domain where you need to explain why a decision was made.

Exam Guidance Summary

The types of problems you should expect:

Type 1 — Convert a Primal to Its Dual Form (Most Common)

Given an objective with one or more constraints:

1. Write constraints in standard $\le 0$ form.
2. Form the Lagrangian with one multiplier per constraint.
3. Take partial derivatives with respect to all primal variables.
4. Substitute back to express everything in terms of multipliers.
5. Write the dual: maximize the resulting function subject to ${\lambda }_i\ge 0$.

This is the most common exam format from the last two to three years. You may not need to solve it — just produce the dual function and state the dual problem. The example from Section 15.4.5 (two-constraint dual) is your template.

Type 2 — Solve a Dual Problem

When the dual has only one variable, take the derivative, find the critical point. Compute the optimal value, and recover the primal variables using the stationarity conditions. If the dual has two variables, they may only ask you to write the form, not solve it.

The full derivation in Section 15.3.1 — from Lagrangian to dual to optimal $\lambda =4$ — is your reference example.

Type 3 — Understand the Min-Max Inequality

Know the inequality:

$$\underset{x}{\min }\underset{\lambda \ge 0}{\max }\mathcal{L}(x,\lambda )\ge \underset{\lambda \ge 0}{\max }\underset{x}{\min }\mathcal{L}(x,\lambda )$$

Understand why it points the way it does — the second-mover advantage in a sequential game. X goes first in the primal, Lambda punishes mistakes, so the primal value is higher (or equal). Lambda goes first in the dual, X responds optimally, so the dual value is lower (or equal). Be ready to explain this in words.

Type 4 — Identify Strong vs Weak Duality

$$d^{\ast }\le p^{\ast }\text{always}$$

• Equality ($d^{\ast }=p^{\ast }$) means strong duality.
• Strict inequality ($d^{\ast }<p^{\ast }$) means weak duality with a duality gap.

Know the conditions for strong duality: convex objective, convex constraints, and a strictly feasible point exists (Slater's condition). Know that SVM and logistic regression both satisfy strong duality.

Key Notes

• Do not memorize formulas in isolation. Understand the two-player game concept and the five-step method. If you understand why the steps work, you can reconstruct any specific formula.
• The five-step method is your universal template: standard form → Lagrangian → derivatives → constraint equation → substitute back.
• KKT conditions are NOT on this exam. They will be covered in the next lecture, just before SVM. Do not spend time memorizing them now.
• Focus your study on: the Lagrangian method (Section 15.2-15.4), primal-to-dual conversion (Section 15.4.5), and conceptual understanding of duality (Section 15.3).

Key Industry Applications

Support Vector Machines (SVM)

The duality framework is the mathematical foundation of SVMs. SVMs are used in:

• Medical diagnosis: Cancer detection from patient features (gene expression, imaging biomarkers), diabetic retinopathy screening, EEG-based seizure detection.
• Text classification: Spam detection, sentiment analysis, document categorization — particularly effective when combined with TF-IDF features.
• Image recognition: Handwritten digit recognition (USPS postal codes), face detection, object categorization from histograms.
• Bioinformatics: Protein fold recognition, gene function prediction, disease subtype classification from microarray data.

Logistic Regression

A baseline linear classifier for binary classification problems:

• Credit scoring: Predicting probability of loan default from applicant features.
• Churn prediction: Identifying customers likely to cancel subscriptions based on usage patterns.
• Medical screening: Estimating disease probability from risk factors and lab values.
• Marketing: Predicting purchase probability from demographic and behavioral data.

SVM handles cases where logistic regression fails — specifically when data is not linearly separable in the original space. If logistic regression gives poor accuracy on non-linear data, SVM with a kernel is the natural next step.

Linear Programming (LP)

Used extensively in operations research and business optimization:

• Supply chain optimization: Minimizing shipping costs across a network of warehouses, factories, and retail locations under capacity constraints.
• Logistics: Routing delivery fleets, scheduling airline crews, planning production lines.
• Resource allocation: Assigning limited resources (budget, personnel, machines) across competing projects to maximize total return.
• Portfolio optimization: Maximizing expected return under linear risk constraints (simpler than the quadratic Markowitz model).
• Telecommunications: Network flow optimization, bandwidth allocation, call routing.

Quadratic Programming (QP)

Appears whenever the objective or constraints have quadratic curvature:

• Portfolio optimization (Markowitz mean-variance): Minimize portfolio variance (a quadratic function of weights) subject to a target return (linear constraint). This is the canonical QP in finance.
• Support Vector Machines: The SVM dual is a convex QP. Every SVM solver (libsvm, sklearn.svm, SVMlight) solves a QP internally.
• Model Predictive Control (MPC). Optimize control inputs over a receding horizon for robots, autonomous vehicles, and industrial processes. The objective penalizes squared tracking errors and squared control effort.
• Signal processing: Constrained least-squares filtering, beamforming, and spectrum estimation.

Gradient Descent / Ascent with Constraints

Constrained optimization explains why unconstrained gradient methods fail on problems with sharp feasible regions:

• The Lagrangian converts constrained problems into unconstrained ones, enabling gradient-based solvers.
• Projected gradient descent handles box constraints (coefficient bounds) and is the workhorse of large-scale constrained ML.
• In deep learning, constraints appear as weight normalization, spectral normalization, and Lipschitz constraints on discriminators (GANs).

L1/L2 Regularization (Lasso/Ridge)

Both are fundamentally constrained optimization problems — minimize a loss function subject to a norm bound on the coefficients:

• L1 (Lasso): $\Vert \beta {\Vert }_1\le t$ creates a diamond-shaped constraint region in coefficient space. The sharp corners (where one or more coordinates equal exactly zero) produce sparse solutions — automatic feature selection. Used in genomics (identifying relevant genes among thousands), compressed sensing, and sparse signal recovery.
• L2 (Ridge): $\Vert \beta {\Vert }_2\le t$ creates a circular constraint region. Smooth boundary means coefficients shrink toward zero but rarely reach exactly zero. All features contribute, but large coefficients are heavily penalized. Used when all features are expected to be relevant, but overfitting is a concern.
• The geometric insight from this lecture: L1's diamond has vertices on the axes where some ${\beta }_j=0$. The loss function's elliptical contours are more likely to first touch the diamond at a vertex than along a face. That is why L1 gives zeros. The circle has no sharp corners, so the contact point is almost never on an axis.

Newton's Method

The numerical method for optimization beyond quadratic degree. When objective or constraint functions involve $x^3$, $x^4$, exponentials, or logarithms, Lagrange multiplier theory no longer applies directly. Newton's method (and its constrained variants like sequential quadratic programming) handles general nonlinear programming by iteratively solving quadratic subproblems. Used in:

• Logistic regression training (iteratively reweighted least squares is a Newton variant).
• Maximum likelihood estimation for complex statistical models.
• Trajectory optimization in robotics and aerospace.