MODULE 4 · B.

TECH STUDY NOTES

Optimization in
Machine Learning
From Gradient Descent to Linear Programming — A Comprehensive Guide

TOPICS QUESTIONS COVERED LEVEL

8 Core Concepts 3-mark & 9-mark [Link] (AI/ML/CS)

TABLE OF CONTENTS

4.1Introduction to Optimization

4.2Gradient Descent

4.3Gradient Descent with Momentum

4.4Stochastic Gradient Descent

4.5Batch vs SGD vs Mini-batch

4.6Constrained Optimization & Lagrange

4.7Convex Optimization

4.8Linear Programming

4.9Quadratic Programming
 SECTION 4.1

01Introduction to Optimization in Machine Learning

What is Optimization?

Optimization is the mathematical process of finding the best solution — the values of parameters that
minimize (or maximize) some objective function. In machine learning, this objective function is called
the loss function or cost function.

DEFINITION

Optimization in ML refers to the process of adjusting model parameters (weights and biases) so that
the model's predictions become as accurate as possible by minimizing the loss function.

Why is Optimization Crucial?

Optimization is the backbone of every machine learning model. Without it, a model cannot learn from
data. Here's why it is indispensable:

Minimizes Loss: Every ML model has a loss function (e.g., Mean Squared Error, Cross-Entropy).
Optimization finds the parameter values that minimize this loss, making predictions more accurate.

Enables Learning: Optimization is literally the "learning" in machine learning — it is the

mechanism by which the model improves with data.

Generalization: Proper optimization helps models generalize to unseen data, not just memorize
training data.

Convergence: It ensures the training process converges to a good solution within a reasonable
number of iterations.

Computational Efficiency: Smart optimization algorithms (like SGD, Adam) make training
feasible even on massive datasets.

KEY INSIGHT

Without optimization, a neural network is just a static mathematical expression. Optimization gives it
the ability to learn by iteratively adjusting weights to reduce error.

3-MARK QUESTIONS — SECTION 4.1

Q Why is optimization crucial in training machine learning models?

Optimization is crucial in machine learning because it is the mechanism through which a model learns
from data. Specifically:
It minimizes the loss function, reducing the difference between predicted and actual outputs.

It iteratively updates model parameters (weights, biases) in the direction that improves performance.

Without optimization, model parameters remain random; no learning occurs.

Efficient optimization ensures the model converges to a good solution in reasonable time.

In short, optimization transforms raw data and a model architecture into a trained, useful predictor.

Q For a simple linear regression model y = wx + b with MSE loss, which quantity does gradient
descent update at each step?
Gradient Descent updates the model parameters — specifically the weight w and bias b — at each
step. These are the learnable parameters of the model. The update is:

UPDATE RULE
w ← w − η · ∂L/∂w b ← b − η · ∂L/∂b

where η is the learning rate and L is the MSE loss. The gradients ∂L/∂w and ∂L/∂b indicate the
direction of steepest ascent, and the parameters are updated in the opposite direction to minimize the
loss.

Q Given loss L(w) = (w − 4)² and current parameter w = 0, find the gradient dL/dw at w = 0.

GRADIENT CALCULATION
L(w) = (w − 4)² dL/dw = 2(w − 4) ← applying chain rule / power rule At w = 0: dL/dw = 2(0

− 4) = −8

The gradient at w = 0 is −8. The negative sign indicates that increasing w will decrease the loss,
which makes intuitive sense since the minimum of this parabola is at w = 4 .

Q Write the update rule of Gradient Descent. Define learning rate.

Update Rule:

GD UPDATE RULE
θ ← θ − η · ∇θL(θ) Where: θ = model parameter (weight/bias) η = learning rate ∇L(θ) =

gradient of loss with respect to θ

Learning Rate (η): The learning rate is a positive scalar hyperparameter that controls the size of the
step taken during each update.
If η is too large → overshooting; the loss may diverge.

If η is too small → very slow convergence; training takes too long.

Typical values: 0.001 , 0.01 , 0.1

 SECTION 4.2

02Gradient Descent
Intuition

Imagine you are standing on a hilly landscape in thick fog, and you want to reach the lowest valley.
You can't see far, but you can feel the slope under your feet. Gradient Descent says: take a small
step in the direction that goes downhill. Repeat until you stop descending.

DEFINITION

Gradient Descent is an iterative first-order optimization algorithm that minimizes a loss function by
moving model parameters in the direction of the negative gradient.

Algorithm

1 Initialize parameters θ randomly (or to zeros).

2 Compute the loss L(θ) using the current parameters on the entire dataset.

3 Compute the gradient: ∇L(θ) = ∂L/∂θ

4 Update parameters: θ ← θ − η · ∇L(θ)

5 Repeat steps 2–4 until convergence (loss stops decreasing significantly).

CORE FORMULA
θ_new = θ_old − η · ∂L/∂θ For linear regression (MSE Loss): ∂L/∂w = (2/n) · Σ (ŷᵢ − yᵢ) · xᵢ

∂L/∂b = (2/n) · Σ (ŷᵢ − yᵢ)

9-MARK QUESTIONS — GRADIENT DESCENT

Q For f(x) = x² + 4x: (a) Find the derivative. (b) Perform two iterations of Gradient Descent
from x = 2, learning rate = 0.1.

(A) FINDING THE DERIVATIVE

DERIVATIVE
f(x) = x² + 4x f'(x) = df/dx = 2x + 4 Verification: minimum occurs at f'(x) = 0 → 2x + 4

= 0 → x = −2 (true minimum)

(B) TWO ITERATIONS OF GRADIENT DESCENT

Given: x₀ = 2, η = 0.1, f'(x) = 2x + 4

━━ Iteration 1 ━━ x₀ = 2 f'(x₀) = 2(2) + 4 = 8 x₁ = x₀ − η · f'(x₀) = 2 − 0.1 × 8 = 2 − 0.8 x₁ =

1.2 ━━ Iteration 2 ━━ x₁ = 1.2 f'(x₁) = 2(1.2) + 4 = 2.4 + 4 = 6.4 x₂ = x₁ − η · f'(x₁) = 1.2 −

0.1 × 6.4 = 1.2 − 0.64 x₂ = 0.56

The parameter is slowly moving from x = 2 towards the minimum at x = −2 . After 2 iterations: x₀ = 2
→ x₁ = 1.2 → x₂ = 0.56. With more iterations, x will converge to −2.

OBSERVATION
Each iteration reduces x by a smaller amount because the gradient magnitude decreases as we
approach the minimum — this is a hallmark of Gradient Descent on convex functions.
 SECTION 4.3

03Gradient Descent with Momentum

The Problem with Basic Gradient Descent

Standard Gradient Descent can be slow, especially when the loss surface has narrow ravines or flat
regions. It may also oscillate rather than converge smoothly. Momentum solves this by incorporating
the history of past gradients.

Concept: Physical Analogy

Think of a ball rolling down a hill. Without momentum, the ball stops immediately when the slope
flattens. With momentum, the ball accumulates velocity — it moves faster in the consistent direction
and dampens oscillations in noisy directions.

MOMENTUM UPDATE RULE

── Standard Gradient Descent ── θ ← θ − η · ∇L(θ) ── Gradient Descent with Momentum ── v_t = β

· v_{t-1} + η · ∇L(θ) ← velocity update θ = θ − v_t ← parameter update Where: v_t = velocity

(momentum) at step t β = momentum coefficient (typically 0.9) η = learning rate ∇L(θ) =

current gradient

How Momentum Works

The velocity term v_t accumulates gradients over time, like a moving average.

β = 0.9 means 90% of past velocity is retained — the algorithm "remembers" where it was going.

In consistent gradient directions, velocity builds up → faster convergence.

In oscillating directions, opposing gradients cancel out → reduced oscillation.

9-MARK QUESTIONS — GD VS GD WITH MOMENTUM

Q Compare / Differentiate basic Gradient Descent and Gradient Descent with Momentum.

Aspect Basic Gradient Descent GD with Momentum

Update Rule θ ← θ − η·∇L v = β·v + η·∇L; θ ← θ − v

Memory Uses only current gradient Uses history of past gradients (velocity)

Speed Can be slow on ravines & flat areas Accelerates convergence

Oscillation May oscillate in steep directions Dampens oscillations

Hyperparameters Only learning rate η Learning rate η + momentum β

Analogy Ball that stops when slope levels Ball that accelerates downhill

Local Minima Easily stuck in shallow minima Better at escaping shallow minima

Complexity Simple to implement Slightly more complex

Typical Use Simple convex problems Deep learning, non-convex problems

KEY INSIGHT

The momentum term acts as a low-pass filter on gradients — it smooths out noisy updates while
amplifying consistent directions. This is why it's almost universally preferred over vanilla gradient
descent in practice.

STANDARD VALUES

β = 0.9 is the most common momentum coefficient. At β = 0.9, the effective step size in a
consistent gradient direction is approximately 10× larger than the basic step (1/(1−0.9) = 10).
 SECTION 4.4

04Stochastic Gradient Descent (SGD)

Motivation

In Batch Gradient Descent, we compute the gradient over the entire dataset before each parameter
update. For large datasets (millions of samples), this is computationally infeasible — just one update
takes forever.

DEFINITION

Stochastic Gradient Descent (SGD) updates parameters after computing the gradient on a single
randomly selected training example at each step, making updates much faster but noisier.

Algorithm

1 Shuffle the training dataset randomly.

2 For each example (xᵢ, yᵢ), compute the gradient of the loss for that single example: ∇L(θ; xᵢ, yᵢ) .

3 Update: θ ← θ − η · ∇L(θ; xᵢ, yᵢ)

4 Repeat for all examples (one pass = one epoch). Repeat for multiple epochs.

SGD UPDATE
Batch GD: uses all N samples θ ← θ − η · (1/N) Σᵢ ∇L(θ; xᵢ, yᵢ) SGD: uses single sample i θ ←

θ − η · ∇L(θ; xᵢ, yᵢ) Mini-batch: uses batch of size B θ ← θ − η · (1/B) Σᵢ∈batch ∇L(θ; xᵢ,

yᵢ)

3-MARK QUESTIONS — SGD

Q What is a main advantage of SGD over full-batch gradient descent for very large datasets?

The main advantage of SGD over Batch Gradient Descent for large datasets is computational
efficiency and faster parameter updates:
Batch GD must process all N training examples before a single update — extremely slow for N =
millions.

SGD performs an update after every single sample, giving N updates per epoch vs. just 1 for Batch
GD.

SGD reaches a reasonable solution much faster in wall-clock time.

The noise in SGD updates can help escape shallow local minima.

SGD requires far less memory per update since only one sample is processed at a time.

Q Differentiate between Batch Gradient Descent and SGD.

Aspect Batch Gradient Descent Stochastic GD (SGD)

Data per update Entire dataset (N samples) Single sample

Gradient accuracy Exact gradient Noisy approximation

Updates per epoch 1 N

Speed Slow on large data Fast

Memory usage High Very low

Convergence path Smooth, stable Noisy, oscillating

Local minima Can get stuck Noise helps escape

 SECTION 4.5

05Batch GD vs SGD vs Mini-batch GD

9-MARK QUESTION

Q Compare / Differentiate Batch GD, SGD, and Mini-batch GD. How do their algorithms differ?

ALGORITHMS

BATCH GRADIENT DESCENT

1. For each epoch:

2. Compute gradient over all N samples

3. g = (1/N) Σ ∇L(θ; xᵢ, yᵢ)

4. θ ← θ − η · g

5. 1 update per epoch

STOCHASTIC GD (SGD)

1. For each epoch:

2. Shuffle dataset

3. For each sample i:

4. g = ∇L(θ; xᵢ, yᵢ)

5. θ ← θ − η · g

6. N updates per epoch

MINI-BATCH GRADIENT DESCENT

1. Choose batch size B (typically 32, 64, 128)

2. For each epoch: shuffle dataset, split into batches

3. For each mini-batch of size B:

4. g = (1/B) Σᵢ∈batch ∇L(θ; xᵢ, yᵢ)

5. θ ← θ − η · g

6. N/B updates per epoch

FULL COMPARISON TABLE

Aspect Batch GD SGD Mini-batch GD

Samples/update All N 1 B (e.g., 32–256)

Gradient quality Exact Very noisy Approximate, stable

Updates per epoch 1 N N/B

Speed per update Slowest Fastest Moderate

Memory Very high Very low Manageable

Convergence Smooth, stable Noisy, fluctuating Smooth + fast

GPU efficiency Not scalable Poor (no parallelism) Excellent (vectorized)

Local minima Easily stuck Escapes via noise Balance of both

Practical use Small datasets Online learning Deep learning (standard)

CONCLUSION

Mini-batch GD is the dominant choice in practice (used by PyTorch, TensorFlow, etc.). It offers
the best trade-off: stable enough gradient estimates, fast updates, and excellent GPU
vectorization. Batch size of 32 or 64 is commonly used.
 SECTION 4.6

06Constrained Optimization & Lagrange Multipliers

What is Constrained Optimization?

DEFINITION

Constrained Optimization is the problem of minimizing (or maximizing) an objective function subject
to one or more constraints that restrict the feasible set of solutions.

General form: Minimize f(x) subject to g(x) = 0 (equality) or h(x) ≤ 0 (inequality)

Unconstrained optimization allows parameters to take any value. In constrained optimization,

solutions must satisfy additional conditions. Examples in ML:

Support Vector Machines (SVMs) — maximize margin subject to classification constraints.

Regularized regression — minimize loss subject to a budget on the parameter norm.

Neural architecture search — optimize accuracy subject to FLOPs ≤ limit.

The Method of Lagrange Multipliers

Lagrange multipliers provide a systematic way to solve equality-constrained optimization problems by

converting them into unconstrained ones.

LAGRANGIAN
Problem: minimize f(x, y) subject to g(x, y) = 0 Step 1: Form the Lagrangian function L(x, y,

λ) = f(x, y) + λ · g(x, y) Step 2: Set partial derivatives to zero (optimality conditions) ∂L/

∂x = 0 → ∂f/∂x + λ · ∂g/∂x = 0 ∂L/∂y = 0 → ∂f/∂y + λ · ∂g/∂y = 0 ∂L/∂λ = 0 → g(x, y) = 0

(constraint satisfied) Step 3: Solve the system of equations for x, y, and λ

GEOMETRIC INTUITION

At the optimal point, the gradient of f and the gradient of g must be parallel — i.e., ∇f = −λ∇g. This
means the contours of f are tangent to the constraint surface at the solution.

9-MARK QUESTION — LAGRANGE MULTIPLIERS

Q Use Lagrange multipliers to minimize f(x, y) = x² + y² subject to constraint x + y = 1.

PROBLEM SETUP

Minimize f(x, y) = x² + y² subject to g(x, y) = x + y − 1 = 0

Geometrically: find the point on the line x + y = 1 closest to the origin (since f is the squared distance
from origin).

STEP 1: FORM THE LAGRANGIAN

STEP 1
L(x, y, λ) = f(x, y) + λ · g(x, y) = x² + y² + λ(x + y − 1)

STEP 2: PARTIAL DERIVATIVES = 0

 STEP 2
∂L/∂x = 2x + λ = 0 → λ = −2x ... (1) ∂L/∂y = 2y + λ = 0 → λ = −2y ... (2) ∂L/∂λ = x + y −

1 = 0 ... (3)

STEP 3: SOLVE THE SYSTEM

STEP 3
From (1) and (2): −2x = −2y x = y Substituting into (3): x + x = 1 2x = 1 x = 1/2, y =

1/2 Finding λ: λ = −2x = −2(1/2) = −1

RESULT

SOLUTION

The minimum value of f(x, y) = x² + y² subject to x + y = 1 is:

Optimal point: (x*, y*) = (1/2, 1/2)

Minimum value: f(1/2, 1/2) = (1/2)² + (1/2)² = 1/4 + 1/4 = 1/2
Lagrange multiplier: λ = −1

This makes intuitive sense: the closest point on the line x + y = 1 to the origin is indeed the
midpoint (½, ½), at distance 1/√2, so squared distance = 1/2. ✓

Q Explain constrained optimization with a suitable example.

DEFINITION

Constrained optimization finds the best solution to an objective function while satisfying given
constraints. Formally:

GENERAL FORM
Minimize (or Maximize) f(x) Subject to: gᵢ(x) = 0 for i = 1, ..., m (equality

constraints) hⱼ(x) ≤ 0 for j = 1, ..., p (inequality constraints)

REAL-WORLD EXAMPLE: PORTFOLIO OPTIMIZATION

Suppose an investor wants to maximize expected return while keeping risk (variance) below a
threshold:

PORTFOLIO EXAMPLE
Maximize: E[R] = w₁r₁ + w₂r₂ (expected return) Subject to: w₁ + w₂ = 1 (weights sum to 1)

w₁, w₂ ≥ 0 (no short selling) σ²(w) ≤ σ²_max (risk limit)

EXAMPLE IN ML: SVM

In Support Vector Machines, we solve:

SVM OPTIMIZATION
Minimize: (1/2)||w||² Subject to: yᵢ(w·xᵢ + b) ≥ 1 for all i ← Hard margin constraint:

all points correctly classified with margin at least 1/||w||

This is a classic constrained quadratic programming problem solved using Lagrange multipliers (KKT
conditions).
3-MARK QUESTIONS — CONSTRAINED OPTIMIZATION

Q What is constrained optimization?

Constrained optimization is the process of finding the minimum or maximum of an objective function
f(x) while satisfying specific constraints on the variables. Unlike unconstrained optimization, the

solution must lie in a restricted feasible region defined by equality constraints g(x) = 0 and/or
inequality constraints h(x) ≤ 0 . It arises naturally in ML when physical, resource, or mathematical
requirements limit the parameter space (e.g., SVM margin maximization, regularization).

Q State the method of Lagrange multipliers.

The Method of Lagrange Multipliers converts a constrained optimization problem into an

unconstrained one by introducing auxiliary variables (multipliers) λ.

For: Minimize f(x) subject to g(x) = 0, form the Lagrangian:

LAGRANGIAN
L(x, λ) = f(x) + λ · g(x)

Then solve: ∇L = 0 , i.e., ∂L/∂xᵢ = 0 for all i, and ∂L/∂λ = 0 (which recovers the constraint). The solution
gives the constrained optimum.
 SECTION 4.7

07Convex Optimization
Convex Functions

DEFINITION

A function f is convex if, for any two points x₁, x₂ and any λ ∈ [0, 1]:

f(λx₁ + (1−λ)x₂) ≤ λf(x₁) + (1−λ)f(x₂)

Geometrically: the chord connecting any two points on the curve lies above (or on) the curve.

✓ CONVEX FUNCTIONS

f(x) = x² (parabola)

f(x) = |x| (absolute value)

f(x) = eˣ (exponential)

MSE loss in linear regression

Logistic loss

✅ Every local minimum is a global minimum

✗ NON-CONVEX FUNCTIONS

f(x) = sin(x)

f(x) = x³

f(x) = x⁴ − 3x² (multiple minima)

Loss surfaces of deep neural networks

⚠ Can have multiple local minima — hard to optimize globally

Why Convexity Matters

For convex problems, any local minimum found by gradient descent is guaranteed to be the
global minimum.

Many classical ML problems (linear regression, logistic regression, SVMs) are convex — hence
solvable optimally.

Deep neural networks have non-convex loss surfaces, which is why training is harder and results
are not guaranteed to be globally optimal.

3-MARK QUESTION

Q Give one example of a convex and a non-convex function.

Convex Function: f(x) = x² (a parabola). It satisfies the convexity condition: the line segment between
any two points on the curve lies above the curve. It has a unique global minimum at x = 0. The second
derivative f''(x) = 2 > 0 everywhere, confirming convexity.

Non-Convex Function: f(x) = x⁴ − 3x² + x. This function has multiple local minima and maxima. A
chord drawn between two points on the curve can dip below the curve, violating the convexity condition.
Deep neural network loss functions are prominent non-convex examples in ML.
 SECTION 4.8

08Linear Programming (LP)

DEFINITION

Linear Programming (LP) is an optimization technique where both the objective function and all
constraints are linear in the decision variables. It finds the optimal (maximum or minimum) value of a
linear objective subject to a system of linear constraints.

Standard Form

STANDARD LP FORM
Maximize (or Minimize): Z = cᵀx = c₁x₁ + c₂x₂ + ... + cₙxₙ Subject to: Ax ≤ b (inequality
constraints) x ≥ 0 (non-negativity) Where: x = decision variables (what we choose) c =

objective coefficients (profit/cost per unit) A = constraint matrix b = constraint limits

(resources available)

Key Properties of LP

The feasible region is a convex polygon (polyhedron in higher dimensions).

The optimal solution (if it exists) always occurs at a corner point (vertex) of the feasible region.

LP problems can be solved by the Simplex Method or graphically (for 2 variables).

9-MARK QUESTION — LP GRAPHICAL SOLUTION

Q Formulate and solve graphically: Maximize Z = 3x + 2y, subject to x + y ≤ 4, x, y ≥ 0.

PROBLEM FORMULATION

LP PROBLEM
Maximize: Z = 3x + 2y Subject to: x + y ≤ 4 x ≥ 0 y ≥ 0

STEP 1: IDENTIFY THE FEASIBLE REGION

The constraints define a region. Convert the inequality to an equation to draw the boundary line:

Line: x + y = 4 → passes through (4, 0) and (0, 4)

x ≥ 0 → right of y-axis

y ≥ 0 → above x-axis
 y

(0,4)
4

4
y=
x+
Z=3x+2y
2

1
Feasible
Region
x
(0,0) 1 2 3 4 (4,0)★

Figure: Feasible region (shaded) for x + y ≤ 4, x ≥ 0, y ≥ 0. Optimal point marked with ★.

STEP 2: IDENTIFY CORNER POINTS

The feasible region is the triangle with vertices:

Corner Point Z = 3x + 2y Value

O = (0, 0) 3(0) + 2(0) 0

A = (4, 0) 3(4) + 2(0) 12 ← Maximum

B = (0, 4) 3(0) + 2(4) 8

SOLUTION

The maximum value of Z = 12, achieved at point (x = 4, y = 0).

This makes sense: since the coefficient of x (= 3) is greater than the coefficient of y (= 2),
spending all budget on x yields maximum profit.

3-MARK QUESTIONS — LP

Q What is Linear Programming?

Linear Programming (LP) is an optimization method used to find the best outcome in a mathematical
model whose requirements are represented by linear relationships. It involves:
A linear objective function to maximize or minimize (e.g., profit, cost, distance).
 Linear constraints (equalities or inequalities) representing resource limits or requirements.

Non-negativity restrictions on decision variables.

LP is widely used in operations research, resource allocation, supply chain, and ML (e.g., LP relaxations
of combinatorial problems).
 SECTION 4.9

09Quadratic Programming (QP)

DEFINITION

Quadratic Programming (QP) is an optimization problem where the objective function is quadratic
(contains squared terms and cross-products of variables) while the constraints remain linear.

Standard Form

QP STANDARD FORM
Minimize: (1/2)xᵀQx + cᵀx Subject to: Ax ≤ b (linear inequality constraints) Aeq·x = beq
(linear equality constraints) x ≥ 0 Where: Q = symmetric positive semi-definite matrix

(quadratic coefficients — defines curvature) c = linear coefficient vector x = decision

variable vector

Connection to Machine Learning

The most famous application of QP in ML is Support Vector Machines (SVMs):

SVM AS QP
SVM Hard-Margin Primal Problem: Minimize: (1/2)||w||² = (1/2)wᵀw ← quadratic objective Subject

to: yᵢ(wᵀxᵢ + b) ≥ 1 for all i ← linear constraints This is a Quadratic Programming problem!
Solved using the dual form with Lagrange multipliers (KKT conditions)

3-MARK QUESTIONS — QP

Q What is Quadratic Programming?

Quadratic Programming (QP) is a type of constrained optimization problem where the objective
function is quadratic (involves squared terms: x², xy, etc.) while all constraints are linear. The
general form minimizes (1/2)xᵀQx + cᵀx subject to linear constraints. QP is more general than LP and
appears in SVM training (margin maximization), portfolio optimization (minimize variance subject to
return constraints), and control systems.

Q Compare Linear Programming vs Quadratic Programming.

Aspect Linear Programming (LP) Quadratic Programming (QP)

Objective Linear: cᵀx Quadratic: (1/2)xᵀQx + cᵀx

Constraints Linear Linear

Feasible region Polytope (polygon in 2D) Polytope (same)

Optimal location Always at a vertex Can be interior or vertex

Complexity Simpler More complex

Solvers Simplex, Interior point Interior point, Active set

 ML Application LP-relaxed problems SVM, Ridge regression dual

Example Max 3x + 2y s.t. x+y≤4 Min (1/2)||w||² s.t. yᵢ(w·xᵢ+b)≥1

9-MARK QUESTION — LP VS QP

Q Differentiate between Linear Programming and Quadratic Programming (detailed).

LINEAR PROGRAMMING

LP optimizes a linear objective function subject to linear constraints. Key characteristics:

Objective: f(x) = c₁x₁ + c₂x₂ + ... (no squared terms)

Feasible region is a convex polytope; the optimal is always at a vertex.

Can be solved efficiently by the Simplex algorithm or interior point methods.

Applications: production planning, transportation, network flow, scheduling.

QUADRATIC PROGRAMMING

QP optimizes a quadratic objective function (which may include x², xy terms) subject to linear
constraints. Key characteristics:

Objective: f(x) = (1/2)xᵀQx + cᵀx (contains squared/cross terms)

If Q is positive semi-definite (PSD), QP is convex — guaranteed global solution.

Optimal may be at a vertex or interior point.

Solved by interior point, active set, or quadratic simplex methods.

Applications: SVM training, portfolio optimization, least squares fitting.

COMPREHENSIVE COMPARISON

Feature Linear Programming Quadratic Programming

Objective type Linear (degree 1) Quadratic (degree 2)

Constraint type Linear Linear

Feasible region shape Polytope Polytope

Solution location Always at vertex Vertex or interior

Level sets of objective Hyperplanes (flat) Ellipsoids (curved)

Convexity guarantee Always convex Only if Q is PSD

Solving method Simplex, Interior point Active set, Interior point

Computation Polynomial time Polynomial (if convex)

Generality Special case of QP (Q=0) General (includes LP)

ML Applications L1-regularized models SVM, Ridge regression, GP

Example Max 3x+2y, s.t. x+y≤4 Min ½(x²+y²), s.t. x+y≥1

KEY TAKEAWAY

LP is a special case of QP where the quadratic coefficient matrix Q = 0. QP is strictly more

expressive and appears wherever curvature matters in the objective — most notably in SVM
optimization, which is the canonical QP in machine learning.
★Quick Reference Summary
REVISION CARD

ALL KEY FORMULAS

━━ Gradient Descent ━━ θ ← θ − η · ∇L(θ) ━━ Gradient Descent with Momentum ━━ v ← β·v +
η·∇L(θ) θ ← θ − v (β typically 0.9) ━━ SGD ━━ θ ← θ − η · ∇L(θ; xᵢ, yᵢ) (one sample at a time)

━━ Mini-batch GD ━━ θ ← θ − η · (1/B) Σᵢ∈batch ∇L(θ; xᵢ, yᵢ) ━━ Lagrangian ━━ L(x, λ) = f(x) +

λ·g(x) (set ∇L = 0 to solve) ━━ LP ━━ Maximize cᵀx s.t. Ax ≤ b, x ≥ 0 ━━ QP ━━ Minimize

(1/2)xᵀQx + cᵀx s.t. Ax ≤ b

Algorithm Samples/Update Speed Stability Best For

Batch GD All N Slow Very stable Small datasets

SGD 1 Very fast Noisy Online learning

Mini-batch GD B (32–256) Fast Moderate Deep learning

GD + Momentum Any of above Faster than GD Better than GD Non-convex surfaces

COMMON EXAM MISTAKES TO AVOID

Confusing dL/dw with dw/dL — always differentiate loss w.r.t. parameter.

Forgetting the negative sign in gradient descent update (we go downhill).

Using wrong formula in Momentum — velocity is added to learning-rate-scaled gradient, not

subtracted.

In LP graphical method — always evaluate all corner points, not just one.

In Lagrange: remember ∂L/∂λ = 0 gives back the original constraint — don't forget it.

Module 4 · Optimization in Machine Learning · [Link] Study Notes · Prepared for Exam Revision