This is a big syllabus, but don't worry — let me break everything down in the simplest way possible,

like I'm explaining it to someone who's never touched this subject. I'll cover the key concepts, skip
the deeply mathematical unimportant parts, and at the end give you the most important viva
questions.

Unit 1: Introduction — The Basics

What is Optimization?

Optimization simply means finding the best solution to a problem. "Best" usually means either the
minimum or maximum of some function. For example: "What's the cheapest route from A to B?" or
"How do I maximize profit?"

The function you're trying to minimize/maximize is called the objective function. The variables
you're tweaking are called decision variables.

Continuous vs Discrete Optimization

• Continuous: variables can take any real value (like temperature, price). Most of your syllabus
covers this.

• Discrete: variables can only take integer/specific values (like number of items). Think
scheduling, network routing.

Constrained vs Unconstrained Optimization

• Unconstrained: you can choose any value for your variables. No restrictions.

• Constrained: there are rules/limits. E.g., "spend at most ₹10,000" or "production ≥ 100
units." Constraints can be equalities (=) or inequalities (≤, ≥).

Global vs Local Optima ← Tricky and important!

Imagine a hilly landscape. A local minimum is a valley that looks like the lowest point nearby, but
there's actually a deeper valley somewhere else — that's the global minimum.

• Local minimum: best in its neighborhood

• Global minimum: best overall

Most algorithms only guarantee finding a local minimum, not the global one. This is a fundamental
challenge.

Stochastic vs Deterministic Optimization

• Deterministic: same input always gives same output. Most classical methods are
deterministic.
 • Stochastic: involves randomness (e.g., Simulated Annealing, Genetic Algorithms). Useful
when the problem is very complex or noisy.

Convexity ← Very important!

A function is convex if the line segment between any two points on it lies above or on the graph.
Think of a bowl shape.

Why does it matter? For convex problems, any local minimum IS the global minimum. This makes life
much easier. A common way to check convexity is the Sylvester criterion — checking if the Hessian
matrix (second derivatives) is positive semi-definite.

Unit 2: Unconstrained Optimization

Recognizing a Local Minimum

At a local minimum:

• First derivative (gradient) = 0 → called a stationary point

• Second derivative (Hessian) is positive definite (like a bowl, curving upward)

If the gradient is zero but Hessian is negative definite → local maximum. If indefinite → saddle point.

Two Main Algorithm Strategies

Line Search: Choose a direction to move in, then figure out how far to go along that direction. It's like
deciding "I'll go north" and then asking "how many steps?"

Trust Region: Instead of picking a direction first, you build a simple model of the function in a small
region (the "trust region") and find the best point within that region. Then you decide whether to
expand or shrink the region based on how accurate the model was.

Search Directions (for Line Search)

1. Steepest Descent: Move in the direction of the negative gradient (downhill). Simple but slow
— it zigzags.

2. Newton's Method: Uses both gradient AND second derivative (Hessian) to take a smarter
step. Converges very fast (quadratically) near the solution, but computing the Hessian is
expensive.

3. Quasi-Newton Methods (like BFGS): Approximate the Hessian instead of computing it

exactly. Best of both worlds — faster than steepest descent, cheaper than Newton.

Rate of Convergence ← Important for viva!

• Steepest Descent: linear convergence (slow, especially if the function is elongated)

 • Newton's Method: quadratic convergence (very fast near solution)

• Quasi-Newton: superlinear convergence (between the two)

Cauchy Point (Trust Region)

The Cauchy Point is the minimum of the trust-region model along the steepest descent direction. It's
used as a "safe" fallback — it guarantees at least some decrease in the function value. The algorithm
then tries to do better than this point.

Unit 3: Conjugate Gradient Methods

This is an efficient iterative method for solving large systems of equations and optimization problems.

The key idea: instead of going in steepest descent directions (which zigzag), conjugate gradient picks
directions that are "conjugate" to each other — meaning they don't interfere with progress already
made. It's like solving a maze without retracing your steps.

For a quadratic function with n variables, the conjugate gradient method finds the exact solution in
at most n steps.

For non-quadratic functions, you restart periodically. The two popular variants are Fletcher-Reeves
and Polak-Ribière formulas (just know their names and that they differ in how they compute the
update direction).

Unit 4: Calculating Derivatives

Sometimes you don't have a formula for the derivative. So you approximate it numerically.

Finite Difference Approximation:

The basic idea: the derivative of f at x is approximately [f(x+h) − f(x)] / h for a small h.

• Forward difference: [f(x+h) − f(x)] / h (less accurate)

• Central difference: [f(x+h) − f(x−h)] / 2h (more accurate)

For higher dimensions:

• Gradient: vector of first partial derivatives — approximate each component

• Jacobian: matrix of first derivatives of a vector function — approximate column by column

• Hessian: matrix of second derivatives — expensive, but can exploit sparsity (most entries are
zero) to save computation

Sparse Jacobian/Hessian: In large problems, most second derivatives are zero. You can group
variables cleverly and compute multiple columns in one function evaluation. This is called
compression.
Unit 5: Constrained Optimization — The Most Important Unit!

KKT Conditions ← Most important topic for your viva

KKT = Karush-Kuhn-Tucker. These are the first-order necessary conditions for a point to be optimal in
a constrained problem. Think of them as the "rules" a solution must satisfy.

For minimizing f(x) subject to:

• Equality constraints: g(x) = 0

• Inequality constraints: h(x) ≤ 0

The KKT conditions say: at the optimal point x*, there exist multipliers λ (for equalities) and μ (for
inequalities) such that:

1. Stationarity: ∇f + λ∇g + μ∇h = 0 (gradient of Lagrangian is zero)

2. Primal feasibility: constraints are satisfied

3. Dual feasibility: μ ≥ 0 for inequality constraints

4. Complementary slackness: μ·h(x) = 0 (either the constraint is active OR its multiplier is zero)

These are necessary conditions. For convex problems, they are also sufficient.

Lagrangian Function

L(x, λ, μ) = f(x) + λg(x) + μh(x)

The Lagrange multiplier λ tells you how much the optimal value of f would improve if you relaxed the
constraint slightly. It's the "shadow price" of the constraint.

Constraint Qualifications

KKT conditions hold only if some regularity condition (constraint qualification) is satisfied at the
solution. The most common one is LICQ (Linear Independence Constraint Qualification) — the
gradients of active constraints must be linearly independent.

Second-Order Conditions

Just like unconstrained optimization, second-order conditions help distinguish minima from maxima
or saddle points. In constrained optimization, we look at the Hessian of the Lagrangian restricted to
the tangent cone (directions that are feasible to move in).

Augmented Lagrangian Methods ← Important!

Regular Lagrangian methods can fail when multipliers don't exist or convergence is poor. The
Augmented Lagrangian adds a penalty term:

L_A = f(x) + λg(x) + (ρ/2)|g(x)|²

The ρ term penalizes constraint violation. This combines the benefits of Lagrange multipliers (exact
method) and penalty methods (robustness). The algorithm alternates between minimizing over x and
updating the multipliers λ.

Now here's an interactive study widget to help you quiz yourself before the viva:

visualize

visualize show_widget

Most Important Viva Questions (Summary)

Here are the ones most likely to be asked:

1. What is the difference between local and global optima? Can an algorithm guarantee a
global minimum?

2. What makes a problem convex, and why does convexity simplify optimization?

3. Compare Line Search and Trust Region strategies.

4. Why does steepest descent converge slowly? What does Newton's method do better?

5. What are the KKT conditions? State all four and explain complementary slackness.

6. What is the Lagrange multiplier and what does it physically represent?

7. What is LICQ and why are constraint qualifications needed?

8. What is the Augmented Lagrangian and why is it preferred over a simple penalty method?

9. What is the rate of convergence for steepest descent vs Newton's vs Quasi-Newton?

10. How does finite-difference approximation work? What's the advantage of central difference?

Quick tip for your viva: When in doubt, always link your answer back to a simple geometric intuition
— like a bowl, a hill, or a valley. Examiners love it when you show you understand the idea, not just
the formula. Good luck Noni, you've got this!

You said: is there any formula that may be asked

is there any formula that may be asked

10:59 am

Claude responded: Yes!

Yes! Here are the key formulas you should know — I've kept only the ones actually likely to be asked
in a viva, with plain English explanations of each.
Unit 1 — Convexity Check

Hessian positive semi-definite (Sylvester's Criterion): For a 2×2 Hessian H to be positive definite:

• H₁₁ > 0 (top-left element positive)

• det(H) > 0 (determinant positive)

If both hold → function is convex at that point.

Unit 2 — Unconstrained Optimization

Gradient condition at a minimum:

∇𝑓(𝑥 ∗ ) = 0

(gradient equals zero vector at a stationary point)

Newton's Step (most important formula here):

𝑥𝑘+1 = 𝑥𝑘 − 𝐻 −1 ∇𝑓(𝑥𝑘 )

where H is the Hessian matrix. This is what makes Newton fast.

Steepest Descent Step:

𝑥𝑘+1 = 𝑥𝑘 − 𝛼𝑘 ∇𝑓(𝑥𝑘 )

where αₖ is the step size (found by line search). Simple but slow.

Wolfe Conditions (for choosing step size αₖ): These two conditions ensure a "good enough" step
size:

• Sufficient decrease: f(xₖ + αdₖ) ≤ f(xₖ) + c₁α∇fₖᵀdₖ

• Curvature condition: ∇f(xₖ + αdₖ)ᵀdₖ ≥ c₂∇fₖᵀdₖ

where 0 < c₁ < c₂ < 1. Just know these exist and what they mean — don't go too deep.

Taylor Expansion (used everywhere):

1
𝑓(𝑥 + 𝑝) ≈ 𝑓(𝑥) + ∇𝑓(𝑥)𝑇 𝑝 + 𝑝𝑇 𝐻𝑝
2

This is the quadratic model used in both line search and trust region methods.

Unit 3 — Conjugate Gradient

CG Update direction:
 𝑑𝑘+1 = −∇𝑓𝑘+1 + 𝛽𝑘 𝑑𝑘

Fletcher-Reeves formula for β:

∥ ∇𝑓𝑘+1 ∥2
𝛽𝑘𝐹𝑅 =
∥ ∇𝑓𝑘 ∥2

Polak-Ribière formula for β:

𝑇
∇𝑓𝑘+1 (∇𝑓𝑘+1 − ∇𝑓𝑘 )
𝛽𝑘𝑃𝑅 =
∥ ∇𝑓𝑘 ∥2

Just know: β controls how much of the previous direction is carried forward.

Unit 4 — Finite Differences

Forward difference (gradient approximation):

∂𝑓 𝑓(𝑥 + ℎ𝑒𝑖 ) − 𝑓(𝑥)
≈
∂𝑥𝑖 ℎ

Central difference (more accurate):

∂𝑓 𝑓(𝑥 + ℎ𝑒𝑖 ) − 𝑓(𝑥 − ℎ𝑒𝑖 )
≈
∂𝑥𝑖 2ℎ

Hessian approximation (second derivative):

∂2 𝑓 𝑓(𝑥 + ℎ𝑒𝑖 ) − 2𝑓(𝑥) + 𝑓(𝑥 − ℎ𝑒𝑖 )

≈
∂𝑥𝑖2 ℎ2

Forward difference error = O(h), Central difference error = O(h²) ← this is why central is preferred.

Unit 5 — Constrained Optimization (Most Formula-Heavy)

Lagrangian function:

𝐿(𝑥, 𝜆, 𝜇) = 𝑓(𝑥) + 𝜆𝑇 𝑔(𝑥) + 𝜇𝑇 ℎ(𝑥)

where g(x) = 0 are equality constraints, h(x) ≤ 0 are inequality constraints.

**KKT Stationarity condition:**

∇𝑥 𝐿 = ∇𝑓(𝑥 ∗ ) + 𝜆𝑇 ∇𝑔(𝑥 ∗ ) + 𝜇𝑇 ∇ℎ(𝑥 ∗ ) = 0

Complementary Slackness:

𝜇𝑖 ⋅ ℎ𝑖 (𝑥 ∗ ) = 0, 𝜇𝑖 ≥ 0∀𝑖

Augmented Lagrangian:
𝜌
𝐿𝐴 (𝑥, 𝜆, 𝜌) = 𝑓(𝑥) + 𝜆𝑇 𝑔(𝑥) + ∥ 𝑔(𝑥) ∥2
2

The multiplier update rule:

𝜆𝑘+1 = 𝜆𝑘 + 𝜌 ⋅ 𝑔(𝑥𝑘 )

Cheat Sheet to Memorize Tonight

visualize

visualize show_widget

Claude's response was interrupted

You said: any other tricky concept left or tricky question that may be asked out of these

any other tricky concept left or tricky question that may be asked out of these

11:40 am

Claude responded: Great question — here are the tricky concepts and curveball questions that
examiners love to ask, which weren't fully covered before.

Great question — here are the tricky concepts and curveball questions that examiners love to ask,
which weren't fully covered before.

Tricky Concepts You Should Know

1. Saddle Points — the sneaky one

A saddle point satisfies ∇f = 0 (looks like a minimum on paper) but is neither a min nor a max. The
Hessian is indefinite — some eigenvalues positive, some negative. Like a horse saddle — minimum in
one direction, maximum in another.

Examiners love asking: "If gradient is zero, is it always a minimum?" — Answer: NO. It could be a
saddle point or maximum.

2. Ill-conditioning — why steepest descent really struggles

When a function's contours are very elongated (like a narrow valley), the condition number of the
Hessian is very large. Steepest descent zigzags back and forth across the valley making tiny progress.
Newton's method handles this perfectly because it uses the Hessian to "reshape" the problem. This
is the real reason Newton beats steepest descent — not just speed, but handling ill-conditioned
problems.

3. Active vs Inactive Constraints

A constraint h(x) ≤ 0 is called active (or binding) at x* if h(x*) = 0 — it's holding the solution back. It's
inactive if h(x*) < 0 — it's satisfied with slack and not affecting the optimum.

Complementary slackness says: if a constraint is inactive → its KKT multiplier must be zero. If the
multiplier is nonzero → the constraint must be active. This is what examiners test with numerical
examples.

4. Why can't you always trust KKT conditions?

KKT conditions are only necessary, not always sufficient. And they only hold when a constraint
qualification (like LICQ) is satisfied. If constraints are degenerate (their gradients are linearly
dependent at the solution), KKT multipliers may not even exist — so the conditions are meaningless.
This is a very common tricky question.

5. Penalty Method vs Augmented Lagrangian — the difference

Pure penalty method: L = f(x) + ρ·|g(x)|² — just penalize constraint violation. Problem: to get an
exact solution you need ρ → ∞, which makes the problem numerically ill-conditioned (very hard to
solve).

Augmented Lagrangian fixes this by also including the multiplier term λᵀg(x), so you can get an exact
solution with a finite ρ. This is the key distinction.

6. The difference between necessary and sufficient conditions

Condition What it means

Necessary If x* is a min, then this must hold. But holding it doesn't guarantee a min.

Sufficient If this holds, then x* is definitely a min.

First-order conditions (∇f = 0, KKT) are necessary. Second-order conditions (positive definite Hessian)
make them sufficient. Examiners love asking "is this condition necessary, sufficient, or both?"

7. Trust Region — what happens when the model is bad?

The trust region algorithm computes a ratio ρ = (actual reduction) / (predicted reduction). If ρ is close
to 1 → model was accurate → expand the trust region. If ρ is small or negative → model was wrong
→ shrink the trust region and try again. This adaptive behavior is what makes trust region methods
robust — a very common viva point.

8. Quasi-Newton — what is BFGS actually doing?

BFGS maintains an approximation Bₖ to the Hessian (or its inverse) and updates it using gradient
information at each step using the formula:

Bₖ₊₁ = Bₖ + (yyᵀ/yᵀs) − (BₖssᵀBₖ/sᵀBₖs)

where s = xₖ₊₁ − xₖ and y = ∇fₖ₊₁ − ∇fₖ.

You don't need to memorize this exactly, but know: it updates the Hessian approximation using the
change in position (s) and change in gradient (y). The key property is that it stays positive definite —
so the search direction is always a descent direction.

Curveball Questions Likely to Be Asked

Q: Can a non-convex problem have a unique global minimum? Yes! A function can be non-convex
but still have only one minimum overall — convexity is a sufficient condition for this property, not a
necessary one.

Q: What happens if you choose step size α too large or too small in line search? Too large → you
overshoot, function value increases, divergence. Too small → progress is negligible, very slow
convergence. The Wolfe conditions exist precisely to ensure α is "just right."

Q: Is Newton's method always better than steepest descent? Not always. Newton requires
computing and inverting the Hessian — O(n³) cost for n variables. For very large problems, this is
prohibitively expensive. Steepest descent or conjugate gradient may be preferred despite slower
convergence.

Q: What is a feasible direction? A direction p from a feasible point x such that moving a small step
along p keeps you feasible (doesn't violate constraints). The tangent cone is the set of all feasible
directions at x*.

Q: If KKT conditions are satisfied, is the point definitely a global minimum? Only if the problem is
convex. For non-convex problems, KKT gives a local minimum at best.

Q: Why is central difference more accurate than forward difference? Forward difference has error
proportional to h (first order). Central difference cancels the first-order error term due to symmetry,
leaving error proportional to h² (second order). So for the same step size h, central difference is far
more accurate.

Q: What does the Lagrange multiplier λ = 0 mean? It means the constraint is not active — the
unconstrained minimum already satisfies the constraint, so the constraint has no effect on the
solution. The optimal point would be the same even without that constraint.

Q: What is the difference between a feasible point and an optimal point? A feasible point satisfies
all constraints but may not minimize the objective. An optimal point is feasible AND minimizes the
objective. All optimal points are feasible, but not all feasible points are optimal.
The three most dangerous tricky questions to be prepared for are the saddle point trap, the
"necessary vs sufficient" distinction for KKT, and the penalty vs augmented Lagrangian comparison. If
you can answer those confidently, you're in great shape for tomorrow!

Start your own conversation

DSC 09 · Viva Preparation

Numerical Optimization

// Full Viva-Ready Notes + Q&A · Nocedal & Wright, 2006

Unit 1 · IntroUnit 2 · UnconstrainedUnit 3 · Conjugate GradientUnit 4 · DerivativesUnit 5 ·

Constrained🔥 Viva Q&A

Unit 01Introduction to Optimization

Definition

What is Optimization?

Optimization is the process of finding the best solution (minimum or maximum) of an objective
function, possibly subject to constraints. It involves choosing values of variables to minimize cost,
error, time, or maximize profit, accuracy, efficiency.

Mathematical Formulation

A general optimization problem is written as: minimize f(x) subject to constraints c_i(x) = 0 (equality)
and c_j(x) ≥ 0 (inequality), where x is the vector of decision variables and f(x) is the objective
function.

Continuous vs Discrete Optimization

Continuous: Variables can take any real value (e.g., finding the minimum of a smooth
function). Discrete: Variables are restricted to integers or a finite set (e.g., traveling salesman
problem). Continuous problems are generally easier to solve using calculus-based methods.

Constrained vs Unconstrained Optimization

Unconstrained: No restrictions on variable values — solution can be anywhere in the

domain. Constrained: Variables must satisfy equality or inequality constraints — feasible region is
restricted. Most real-world problems are constrained.

Global vs Local Optimization

Global Minimum: The absolute lowest value of f(x) over the entire domain — hardest to
guarantee. Local Minimum: Lowest value in a neighborhood — most algorithms only guarantee this.
Most practical algorithms find local optima.

Stochastic vs Deterministic Optimization

Deterministic: Algorithm always produces the same result for the same input (e.g., gradient
descent). Stochastic: Uses randomness to explore solution space (e.g., simulated annealing, genetic
algorithms). Stochastic methods are better for escaping local minima.

Convexity — Why It Matters

A function f is convex if the line segment between any two points on the graph lies above or on the
graph. For a convex function, every local minimum is also a global minimum — this is the "holy grail"
property. A convex set means any two points in the set can be connected by a line that stays in the
set.

Key Insight: If both the objective function and feasible region are convex, the problem is tractable —
we are guaranteed a global solution. Non-convex problems may have many local minima and are
generally NP-hard.

Unit 02Fundamentals of Unconstrained Optimization

What is a Local Minimum?

A point x* is a local minimum if f(x*) ≤ f(x) for all x in a neighborhood around x*. Necessary
condition: gradient ∇f(x*) = 0. Sufficient condition: Hessian H(x*) is positive definite (all eigenvalues
positive). A nonsmooth problem is one where the gradient doesn't exist everywhere (e.g., |x|).

Two Strategies: Line Search vs Trust Region

Line Search: First decides a search direction, then finds how far to move along that direction (step
length α). Think: "which direction, then how far?" Trust Region: First decides a region (radius Δ)
within which to trust the model, then finds the best step within that region. Think: "how far can I
trust my model?"

Search Directions for Line Search

Steepest Descent: Direction = –∇f (negative gradient). Simplest but slowest convergence
(zigzags). Newton's Method: Direction = –H⁻¹∇f. Uses curvature info, faster convergence but
expensive (requires Hessian). Quasi-Newton: Approximates H⁻¹ using gradient information only —
best practical balance.

Step Length & Wolfe Conditions

After choosing direction, we need step length α. Too small = slow progress. Too large = may
overshoot. The Wolfe conditions ensure sufficient decrease in f and sufficient curvature — this
guarantees the line search makes meaningful progress without being too conservative or aggressive.

Rate of Convergence

Linear convergence: Error reduces by a constant factor each step (steepest descent). Superlinear
convergence: Convergence accelerates over iterations. Quadratic convergence: Error roughly
squares each step (Newton's method near solution) — very fast. Quasi-Newton methods achieve
superlinear convergence.

Newton's Method — Concept

Uses a quadratic approximation of f around current point. Step direction: p = –

H⁻¹∇f. Advantage: Quadratic convergence near solution. Disadvantage: Requires computing and
inverting Hessian (expensive for large problems), and may fail if Hessian is not positive definite (not
near a minimum).

Quasi-Newton Methods (e.g., BFGS)

Instead of computing the full Hessian, these methods build an approximation of the inverse Hessian
using gradient differences between iterations. BFGS (Broyden-Fletcher-Goldfarb-Shanno) is the most
popular — it maintains a positive definite Hessian approximation and achieves superlinear
convergence. No second derivatives needed.

Trust Region Method

Builds a model m_k(p) of f around current point x_k, then minimizes this model within a ball of
radius Δ_k (the trust region). If the actual reduction matches the predicted reduction well, the step is
accepted and Δ_k may grow. If not, Δ_k is shrunk. The Cauchy Point is the minimizer of the model
along the steepest descent direction — it guarantees global convergence.

Key Insight: Line search and Trust Region are NOT competing — they are different frameworks for
generating steps. Both can use the same underlying models (quadratic approximations). Trust Region
is generally more robust when the model is poor.

Unit 03Conjugate Gradient Methods

What are Conjugate Directions?

Two directions p and q are conjugate with respect to a matrix A if p^T A q = 0. Conjugate directions
have a special property: minimizing along one direction doesn't "spoil" progress made in previous
conjugate directions. This eliminates the zigzagging problem of steepest descent.

Conjugate Gradient (CG) Method — Core Idea

CG generates a sequence of search directions that are mutually A-conjugate. For a quadratic function
of n variables, CG finds the exact solution in at most n steps. For non-quadratic functions, it is used
iteratively. It only requires matrix-vector products — no Hessian storage needed, making it ideal for
large-scale problems.

Why CG is Better than Steepest Descent

Steepest descent zigzags because successive directions are orthogonal, causing repeated work. CG
avoids this by making each new direction conjugate to all previous ones — progress in one direction
is preserved. For n-dimensional quadratics, steepest descent may take thousands of steps; CG takes
at most n.

Practical CG (Fletcher-Reeves / Polak-Ribière)

For non-quadratic functions, we use the nonlinear CG method. The direction update uses a scalar β:
p_{k+1} = –∇f_{k+1} + β_k * p_k. Fletcher-Reeves and Polak-Ribière are two ways to compute β.
Polak-Ribière is generally preferred as it can "reset" automatically when progress stalls.

Rate of Convergence of CG

CG convergence depends on the condition number κ(A) = λ_max/λ_min (ratio of largest to smallest
eigenvalue). Small condition number → fast convergence. Large condition number → slow
convergence. Preconditioning — transforming the problem to reduce the condition number — is the
key technique to speed up CG in practice.
Key Insight: CG is the method of choice for large-scale problems because it requires only O(n)
memory (just storing vectors, not matrices), while Newton-type methods require O(n²) memory for
the Hessian.

Unit 04Calculating Derivatives

Why Approximate Derivatives?

Many optimization algorithms need gradient and Hessian information. But in practice, the function
may be given as black-box code, derivatives may be too complex to derive analytically, or the
function may not be differentiable analytically. Numerical differentiation provides practical
approximations.

Finite-Difference Approximations

Forward difference: ∇f(x) ≈ [f(x+h·e_i) – f(x)] / h. Requires n+1 function evaluations. Central
difference: ∇f(x) ≈ [f(x+h·e_i) – f(x–h·e_i)] / (2h). More accurate (second-order) but needs 2n
evaluations. Choosing h: too small → numerical cancellation errors; too large → truncation errors.

Approximating the Gradient

The gradient vector ∇f(x) has n components. Each component is approximated by perturbing one
variable at a time. This costs n (forward difference) or 2n (central difference) function evaluations.
For large n, this becomes expensive — motivating automatic differentiation (not in syllabus but good
to know).

Jacobian and Sparse Jacobian

The Jacobian is the matrix of partial derivatives of a vector function F(x): J_{ij} = ∂F_i/∂x_j. For m
outputs and n inputs, it's m×n. A sparse Jacobian has mostly zeros. By exploiting sparsity structure,
we can compute the Jacobian with far fewer function evaluations by perturbing multiple variables
simultaneously (if their columns don't share nonzero rows).

Approximating the Hessian

The Hessian H is the n×n matrix of second derivatives. By finite differences: H_{ij} ≈ [∇f(x+h·e_j) –
∇f(x)] / h. Computing the full Hessian by finite differences costs O(n²) function evaluations — very
expensive for large n. Sparse Hessian: Exploits zero structure to reduce cost, similar to sparse
Jacobian techniques.

Key Insight: Quasi-Newton methods (Unit 2) avoid computing the Hessian entirely by building an
approximation from gradients — this is why they are preferred over finite-difference Hessian
approximations for most large-scale problems.

Unit 05Theory of Constrained Optimization

Feasible Region & Types of Solutions

The feasible region is the set of all x satisfying the constraints. A global solution minimizes f over the
entire feasible region. A local solution minimizes f within a neighborhood inside the feasible region.
Constraints can be active (equality holds at solution) or inactive (strict inequality holds).

KKT Conditions (First-Order Optimality)

The Karush-Kuhn-Tucker (KKT) conditions are necessary conditions for a local minimum of a
constrained problem. They state: ∇f(x*) = Σ λ_i ∇c_i(x*) + Σ μ_j ∇h_j(x*), with μ_j ≥ 0 (for inequality
constraints) and μ_j · h_j(x*) = 0 (complementary slackness). λ and μ are called Lagrange multipliers /
KKT multipliers. These generalize the Lagrange condition to inequality constraints.

Constraint Qualifications

For KKT conditions to be valid, the problem must satisfy a constraint qualification (CQ) at the
solution. The most common is LICQ (Linear Independence Constraint Qualification): the gradients of
active constraints must be linearly independent. Without a CQ, KKT conditions may not hold even at
a true minimum.

Tangent Cone

The tangent cone at a feasible point x* is the set of directions along which you can move and stay (to
first order) in the feasible region. It characterizes the local geometry of the feasible set at a point.
Constraint qualifications essentially ensure the tangent cone is well-behaved (equals the linearized
feasible cone).

Second-Order Conditions & Projected Hessian

Second-order necessary condition: The Lagrangian Hessian must be positive semidefinite on the
tangent space of active constraints. Second-order sufficient condition: Positive definite on that
tangent space → strict local minimum. The Projected Hessian is the Hessian of the Lagrangian
projected onto the subspace of active constraint gradients — it captures curvature relevant to
constrained optimality.

Augmented Lagrangian Methods

The Lagrangian of a constrained problem is L(x, λ) = f(x) – λ^T c(x). The Augmented Lagrangian adds
a penalty term: L_A(x, λ, ρ) = f(x) – λ^T c(x) + (ρ/2)||c(x)||². This combines the benefits of penalty
methods (no need for feasibility) with Lagrangian duality (dual variables updated iteratively). Unlike
pure penalty methods, finite ρ is sufficient — avoids ill-conditioning.

Linear vs Non-linear Constrained Optimization

Linear Programming (LP): Both objective and constraints are linear — solved efficiently by Simplex or
interior point methods. Non-linear Programming (NLP): Objective or constraints (or both) are non-
linear — much harder, requires KKT theory, SQP, or augmented Lagrangian methods. Most real-world
ML and data science problems are NLPs.

Key Insight: The KKT conditions are the cornerstone of constrained optimization — everything else
(SQP, augmented Lagrangian, interior point methods) is essentially a computational strategy to find a
point satisfying these conditions.

Quick RefKey Terms at a Glance

Term One-Line Definition

Objective function The function f(x) being minimized or maximized

 Term One-Line Definition

Gradient ∇f Vector of first partial derivatives — points in direction of steepest ascent

Hessian H Matrix of second partial derivatives — describes curvature

Positive Definite All eigenvalues positive → bowl-shaped → local minimum

Convex function Local min = global min; line segment between any two points lies above curve

Lagrange multiplier Shadow price — how much objective changes per unit relaxation of constraint

KKT conditions First-order necessary conditions for constrained optimality

BFGS Most popular quasi-Newton method; approximates inverse Hessian

Condition number κ λ_max/λ_min; high κ → ill-conditioned → slow convergence

Active constraint Constraint satisfied with equality at the solution point

Feasible point Any x that satisfies all constraints

Stationary point Point where ∇f = 0 (could be min, max, or saddle)

Viva Questions & Answers

Unit 1 — Introduction

Q1What is the difference between a local minimum and a global minimum?

A local minimum is a point where f(x*) is smaller than all nearby points — it's the lowest point in its
neighborhood. A global minimum is the absolute lowest value of f over the entire domain. Every
global minimum is a local minimum, but not vice versa. Most algorithms can only guarantee finding a
local minimum, not a global one.

Q2Why is convexity important in optimization?

For a convex function over a convex feasible set, any local minimum is also a global minimum. This
means we don't need to worry about getting stuck in a suboptimal solution. Algorithms are
guaranteed to find the global optimum efficiently. Most practical algorithms work best (or only
correctly) on convex problems.
Q3What is the difference between stochastic and deterministic optimization?

Deterministic algorithms always produce the same output for the same input — no randomness
involved (e.g., gradient descent, Newton's method). Stochastic algorithms use random elements to
explore the solution space — they can escape local minima but provide no guarantee of finding the
global minimum in finite time (e.g., simulated annealing, genetic algorithms, stochastic gradient
descent in ML).

Q4Give a real-world example of a constrained optimization problem.

Portfolio optimization in finance: minimize risk (variance of returns) subject to the constraint that
total invested amount = budget, and each investment ≥ 0. Other examples: minimizing fuel
consumption of an aircraft subject to reaching the destination on time; training a neural network
with regularization constraints; shortest path subject to road network constraints.

Unit 2 — Unconstrained Optimization

Q5Compare Line Search and Trust Region methods.

Line Search: Picks a direction first, then finds the optimal step length along that direction. Direction is
fixed, step length varies. Trust Region: Defines a region where the model is trusted, then finds the
best step within that region. Both direction and length are determined simultaneously. Trust Region
is generally more robust when the quadratic model is poor, while Line Search is simpler to
implement. Both converge to the same class of solutions.

Q6Why does steepest descent converge slowly?

Steepest descent is slow because successive search directions are orthogonal to each other. This
causes a zigzagging behavior — each step undoes some of the progress from the previous step. The
algorithm keeps correcting itself without making efficient progress. Convergence rate is linear and
depends heavily on the condition number — a high condition number (elongated ellipsoidal
contours) causes very slow zigzagging convergence.

Q7What is a Quasi-Newton method and why is it used?

A Quasi-Newton method approximates the Hessian (or its inverse) using only gradient information,
avoiding the expensive computation of true second derivatives. The most popular is BFGS. It builds
up a Hessian approximation iteratively using the secant equation. Advantage: superlinear
convergence (faster than steepest descent) without computing second derivatives. Used when
Newton's method is too expensive but gradient-only methods are too slow.

Q8What is the Cauchy Point and why is it important?

The Cauchy Point is the minimizer of the trust region quadratic model along the steepest descent
direction, within the trust region boundary. It's important because it guarantees global
convergence of the trust region method — any step that achieves at least as much reduction as the
Cauchy Point is acceptable, and this ensures the algorithm never gets completely stuck. It's the "safe
fallback" in trust region algorithms.

Q9What are the necessary and sufficient conditions for a local minimum?

First-order necessary condition (FONC): ∇f(x*) = 0 (gradient is zero — stationary point). Second-
order necessary condition (SONC): Hessian H(x*) is positive semidefinite. Second-order sufficient
condition (SOSC): Hessian H(x*) is positive definite — this guarantees a strict local minimum. Note:
FONC alone gives stationary points, which could be minima, maxima, or saddle points.

Unit 3 — Conjugate Gradient

Q10What does "conjugate" mean in the Conjugate Gradient method?

Two directions p and q are conjugate (A-conjugate) with respect to matrix A if p^T A q = 0. This is a
generalization of orthogonality. The key property is that minimizing along a conjugate direction
doesn't destroy the minimum condition in the previous direction. This allows CG to make non-
interfering progress in different directions, avoiding the zigzagging of steepest descent.

Q11How many iterations does CG need to solve an n-dimensional quadratic problem exactly?

At most n iterations — it finds the exact solution in at most n steps for a strictly convex quadratic
problem with n variables. This is because CG generates n mutually conjugate directions, which span
the full space. In practice, for non-quadratic problems, it is run iteratively with restarts. And if the
matrix has only k distinct eigenvalues, CG converges in at most k steps.

Q12What is preconditioning and why is it used with CG?

Preconditioning transforms the optimization problem into an equivalent one with a better condition
number. A preconditioner P (approximation to A⁻¹) is used to convert Ax=b into P⁻¹Ax = P⁻¹b, which
has smaller condition number κ → faster CG convergence. Ideally P = A (but then we've solved the
problem), so we use cheap approximations like incomplete Cholesky factorization or diagonal scaling.

Unit 4 — Calculating Derivatives

Q13What is finite difference approximation? What is the trade-off in choosing h?

Finite difference approximates derivatives numerically by evaluating the function at nearby points.
Forward difference: f'(x) ≈ [f(x+h) – f(x)]/h. The trade-off in choosing step size h: too small h →
catastrophic cancellation (floating point errors dominate), too large h → truncation error
(approximation is inaccurate). Optimal h is typically around √(machine epsilon) ≈ 10⁻⁸ for forward
differences, and ∛(machine epsilon) for central differences.

Q14Why is central difference more accurate than forward difference?

Central difference: [f(x+h) – f(x–h)]/(2h) has second-order accuracy — truncation error is O(h²).
Forward difference: [f(x+h) – f(x)]/h has only first-order accuracy — truncation error is O(h). Central
difference achieves much better accuracy for the same h. Trade-off: central difference requires 2n
function evaluations for gradient vs n+1 for forward difference.

Q15What is a sparse Jacobian and how do we exploit sparsity?

A sparse Jacobian has most entries equal to zero — each output function depends on only a few
input variables. We can exploit sparsity by simultaneous perturbation: perturb multiple variables at
once if they don't both appear (nonzero) in the same row of J. This can reduce the number of
function evaluations from n (full) to much fewer. Sparsity pattern must be known or estimated first.

Unit 5 — Constrained Optimization

Q16State the KKT conditions in simple terms.

At an optimal point x*, the gradient of the objective must be expressible as a weighted combination
of the gradients of the active constraints. In other words, you can't improve f without violating a
constraint — all improving directions are "blocked" by constraints. Specifically: ∇f = Σλᵢ∇cᵢ (equality
constraints) + Σμⱼ∇hⱼ (inequality constraints), with μⱼ ≥ 0 and μⱼhⱼ = 0 (complementary slackness —
multiplier is zero for inactive constraints).

Q17What is complementary slackness?

Complementary slackness states that for each inequality constraint: μⱼ · hⱼ(x*) = 0. This means either
the constraint is active (hⱼ = 0) or its multiplier is zero (μⱼ = 0) — but not both can be non-zero.
Intuitively: if a constraint is not binding (slack), it doesn't affect the optimum and its multiplier is
zero. If the multiplier is non-zero, the constraint must be tight (active) at the solution.

Q18What is the Augmented Lagrangian and how does it improve on the pure penalty method?

The pure penalty method adds ρ||c(x)||² to f, driving constraint violations to zero — but requires
ρ→∞, causing ill-conditioning. The Augmented Lagrangian adds both a penalty term AND Lagrange
multiplier estimate: L_A = f – λᵀc + (ρ/2)||c||². By updating λ iteratively, the method achieves
constraint satisfaction with finite ρ — no ill-conditioning. It gets the best of both: the robustness of
penalty methods and the accuracy of Lagrangian duality.

Q19What is a constraint qualification? Give an example.

A constraint qualification is a regularity condition on the constraints at a solution point, required for
KKT conditions to be valid. The most common is LICQ (Linear Independence Constraint
Qualification): the gradients of all active constraints at x* must be linearly independent. Without a
CQ, the KKT conditions may fail to hold even at a true optimal point — so we cannot use them to
characterize the solution. LICQ ensures the constraint gradients form a "nice" local description of the
feasible set.

Q20What is the difference between the Lagrangian and the Augmented Lagrangian?

The standard Lagrangian L(x,λ) = f(x) – λᵀc(x) incorporates constraints via multipliers — stationary
points of L satisfy KKT conditions but may be saddle points, not minima. It can be unbounded below.
The Augmented Lagrangian adds a quadratic penalty: L_A = f – λᵀc + (ρ/2)||c||². This makes the
subproblem well-posed (bounded below, can find a local minimum), while still incorporating
Lagrange multiplier updates for constraint satisfaction. It's more numerically stable than the pure
Lagrangian.

Bonus — Cross-Unit / Tricky

B1What is the relationship between the condition number and convergence?

The condition number κ = λ_max/λ_min measures how "stretched" the problem is. For steepest
descent convergence rate ≤ (κ–1)/(κ+1). High κ → rate close to 1 → very slow convergence. For CG,
convergence in at most k steps where k = number of distinct eigenvalues; practically, high κ still slows
convergence. This is why preconditioning (artificially reducing κ) is so important in practice.

B2Why can't we always use Newton's method?

Three main reasons: (1) Cost: Computing and storing the n×n Hessian costs O(n²) memory and O(n³)
to solve — infeasible for large n. (2) Non-positive definiteness: Away from a minimum, the Hessian
may not be positive definite, so the Newton step may not be a descent direction. (3) Black-box
functions: If derivatives can't be computed analytically, computing the Hessian requires O(n²)
function evaluations. Quasi-Newton methods solve issues 1 and 3; modified Newton (with Hessian
modification) addresses issue 2.

B3What is the role of the Lagrange multiplier economically / intuitively?

The Lagrange multiplier λ represents the marginal value of relaxing the constraint by one unit. In
economics, it's the "shadow price" — how much the optimal objective would improve if the
constraint were loosened slightly. If λ = 0, the constraint is not binding (inactive) and relaxing it
doesn't help. If λ > 0 (for a minimization problem with ≥ constraint), the constraint is tight and
relaxing it would reduce the minimum value.

Here's your complete study guide based on both PYQs:

Most Important Topics (Ranked by Frequency)

1. Linear Programming — appears in every section of both papers 2. Lagrangian / Constrained

Optimization — appears 4+ times across both 3. Gradient-based methods (Newton, Conjugate
Gradient, Steepest Descent) 4. Convex functions & stationary points 5. Line Search & Golden
Section 6. Numerical differentiation (forward/backward difference)

Viva Questions with Detailed Answers

Topic 1: Stationary Points & Convexity

Q1. What is a stationary point? Explain its three types.

A stationary point is a point where the gradient of a function is zero — i.e., f'(x) = 0 (or ∇f(x) = 0 for
multivariate functions). It's where the curve momentarily "flattens out."

The three types are:

Local Minimum — f'(x) = 0 and f''(x) > 0. The function decreases on both sides towards this point.
Example: f(x) = x², at x=0: f'(0)=0, f''(0)=2 > 0 → local minimum.

Local Maximum — f'(x) = 0 and f''(x) < 0. The function increases towards this point from both sides.
Example: f(x) = -x², at x=0: f'(0)=0, f''(0)=-2 < 0 → local maximum.

Saddle Point — f'(x) = 0 but f''(x) = 0, or for multivariate: Hessian is indefinite (neither positive nor
negative definite). The function increases in some directions and decreases in others. Example: f(x,y)
= x² - y², at (0,0) it's a saddle point.

Q2. What is a convex function? How do you check convexity?

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

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

Geometrically: the line segment between any two points on the curve lies above or on the curve.

Check methods:
 • If f''(x) ≥ 0 for all x → convex (1D)

• If the Hessian matrix H is positive semi-definite → convex (multivariate)

PYQ Example: f(x,y) = {x + y ≤ 6} — this is actually a feasible region (a half-plane), which is a convex
set. A convex set satisfies the same definition above for points.

Another PYQ example: f(x,y) = {x² + y² ≥ 6} — the feasible region is the exterior of a circle, which is
NOT convex (you can draw two points inside the region where the connecting line exits it).

Topic 2: Linear Programming

Q3. How do you determine unique / multiple / infeasible solutions in a graphical LPP?

Situation Graphical Method Simplex Method

One basic feasible solution is optimal;

Unique Optimal point is a single corner (vertex) of the
all non-basic reduced costs are non-
solution feasible region
zero

Objective function is parallel to one of the A non-basic variable has reduced cost
Multiple
constraint boundary lines at the optimal; = 0 in the optimal tableau; alternate
solutions
entire edge segment is optimal pivots exist

Feasible region is empty — constraints Artificial variables remain in the basis

Infeasible
contradict each other with non-zero values

Feasible region extends to infinity in the No limiting constraint in the direction

Unbounded
direction of optimization of improvement

PYQ Example (Dec 2024, Q3b): max Z = 2x₁ - x₂ + 3x₃ — after solving by Simplex, if a non-basic
variable has cⱼ - zⱼ = 0, the problem has multiple optimal solutions. You can find three by pivoting on
that variable.

Q4. Solve a transportation problem — what are the three methods and when to use each?

All three find an initial basic feasible solution (IBFS), not necessarily the optimal:

North-West Corner Method — Start from top-left cell, allocate as much as possible, move right or
down. Simple but ignores costs entirely → usually gives the worst solution.

Least Cost Method — Always pick the cell with the minimum cost and allocate there. Better than
NWC because it considers costs.

Vogel's Approximation Method (VAM) — For each row/column, compute the penalty = difference
between the two lowest costs. Allocate to the minimum cost cell in the row/column with the highest
penalty. Gives the closest to optimal → best IBFS method.

Example (PYQ 2024, Q1c): 3 sources S₁, S₂, S₃ with supply 7, 9, 18 and 4 destinations D₁-D₄ with
demand 5, 8, 7, 14. After finding IBFS using any method, you'd apply MODI (Modified Distribution)
method to check and reach optimality.
Topic 3: Lagrangian Method (Appears in BOTH papers)

Q5. Explain the Lagrangian method. Solve: minimize f(x,y) = 2x + y subject to x² + y² = 1.

The Lagrangian method handles equality-constrained optimization. For:

minimize f(x) subject to g(x) = 0

We form: L(x, λ) = f(x) + λ·g(x)

Then solve: ∂L/∂x = 0, ∂L/∂y = 0, ∂L/∂λ = 0

Solution for PYQ problem:

• g(x,y) = x² + y² - 1 = 0

• L = 2x + y + λ(x² + y² - 1)

• ∂L/∂x = 2 + 2λx = 0 → x = -1/λ

• ∂L/∂y = 1 + 2λy = 0 → y = -1/(2λ)

• Substituting into constraint: 1/λ² + 1/(4λ²) = 1 → 5/(4λ²) = 1 → λ = ±√(5)/2

• Taking λ = √5/2: x = -2/√5, y = -1/√5 → f = -√5 (minimum)

• Taking λ = -√5/2: x = 2/√5, y = 1/√5 → f = √5 (maximum)

PYQ (2024): Find points on x² + y² = 80 closest/farthest from (1,2): Minimize/maximize D² = (x-1)² +

(y-2)² subject to x² + y² = 80. L = (x-1)² + (y-2)² + λ(x² + y² - 80) ∂L/∂x: 2(x-1) + 2λx = 0 → x(1+λ) = 1 → x
= 1/(1+λ) ∂L/∂y: 2(y-2) + 2λy = 0 → y(1+λ) = 2 → y = 2/(1+λ) Substituting: 1/(1+λ)² + 4/(1+λ)² = 80 →
5/(1+λ)² = 80 → (1+λ)² = 1/16 → 1+λ = ±1/4 → Closest point: x=4, y=8; Farthest: x=-4, y=-8

Topic 4: Newton's Method (Multivariate)

Q6. Explain Newton's method for optimization. Use it to minimize f(x₁,x₂) = 8x₁² - 4x₁x₂ + 5x₂² from
(5,2).

Newton's method for minimization uses the update rule:

x_{k+1} = x_k - [∇²f(x_k)]⁻¹ · ∇f(x_k)

Where ∇²f is the Hessian matrix.

Step 1 — Compute gradient ∇f:

• ∂f/∂x₁ = 16x₁ - 4x₂

• ∂f/∂x₂ = -4x₁ + 10x₂

Step 2 — Compute Hessian H:

H = | 16 -4 |

| -4 10 |
H is constant here (quadratic function), so Newton's method converges in one step.

Step 3 — Gradient at (5,2): ∇f = [16(5) - 4(2), -4(5) + 10(2)] = [72, 0]

Step 4 — Compute H⁻¹: det(H) = 160 - 16 = 144 H⁻¹ = (1/144) × |10 4| | 4 16|

Step 5 — Update: x₁ = [5,2] - H⁻¹·[72,0] = [5,2] - [1/2, 2] = [4.5, 0] → after full computation gives [0,0]
as minimum.

Key insight: For quadratic functions, Newton's method finds the exact minimum in one iteration. For
non-quadratic functions, it may need multiple iterations.

Topic 5: Conjugate Gradient Method

Q7. What is the Conjugate Gradient method? Apply it to minimize f(x₁,x₂) = 3x² - 4x₁x₂ + 2x₂² + 4x₁ +
6 from (0,0).

The Conjugate Gradient (CG) method is between steepest descent (slow) and Newton's method
(expensive). It generates search directions that are mutually conjugate with respect to the Hessian.

Algorithm:

1. Start at x₀, compute gradient g₀ = ∇f(x₀)

2. Set initial direction d₀ = -g₀

3. Compute step size: α_k = (gₖᵀgₖ) / (dₖᵀHdₖ)

4. Update: x_{k+1} = x_k + α_k·d_k

5. Compute new gradient: g_{k+1} = ∇f(x_{k+1})

6. Compute β_k = (g_{k+1}ᵀg_{k+1}) / (gₖᵀgₖ) (Fletcher-Reeves)

7. New direction: d_{k+1} = -g_{k+1} + β_k·d_k

8. Repeat until convergence

PYQ Solution from (0,0): f(x₁,x₂) = 3x₁² - 4x₁x₂ + 2x₂² + 4x₁ + 6

• H = |6 -4|, ∇f = [6x₁-4x₂+4, -4x₁+4x₂] |-4 4|

• At (0,0): g₀ = [4, 0], d₀ = [-4, 0]

• α₀ = (16)/([-4,0]·H·[-4,0]ᵀ) = 16/([-4,0]·[-24,16]ᵀ) = 16/96 = 1/6

• x₁ = [0,0] + (1/6)·[-4,0] = [-2/3, 0]

• Continue until ∇f ≈ 0

Can Steepest Descent also be used? Yes, but it converges much slower — it zigzags because
consecutive directions are orthogonal, not conjugate. For quadratic problems with n variables, CG
converges in at most n steps; steepest descent may need many more.

Topic 6: Golden Section Rule

Q8. How is the golden ratio c = 1.618 derived? Apply Golden Section to minimize f(x) = x² over [-5,
15].

Derivation of golden ratio: The Golden Section method reduces the interval by a constant factor ρ at
each step. For efficiency, we want:

New interval / Old interval = constant = (1-ρ)

For the method to reuse one function evaluation per iteration, the two interior points must be
placed symmetrically such that after eliminating one side, the remaining point is at the correct
relative position for the next step.

This gives the equation: ρ² = 1 - ρ → ρ² + ρ - 1 = 0 → ρ = (√5 - 1)/2 ≈ 0.618

Therefore c = 1/ρ = 2/(√5-1) = (√5+1)/2 ≈ 1.618 (the golden ratio φ)

Application to minimize f(x) = x² on [-5, 15] with ε = 1.5:

Initial: a = -5, b = 15, length = 20

Each iteration:

• x₁ = a + (1-0.618)(b-a) = a + 0.382(b-a)

• x₂ = a + 0.618(b-a)

• If f(x₁) < f(x₂): eliminate right → b = x₂

• Else: eliminate left → a = x₁

• Stop when (b-a) ≤ ε = 1.5

Iteration 1: x₁ = -5 + 0.382(20) = 2.64, x₂ = -5 + 0.618(20) = 7.36 f(2.64) = 6.97, f(7.36) = 54.2 → f(x₁) <
f(x₂) → b = 7.36, new interval = [-5, 7.36]

Continue until interval width ≤ 1.5. The minimum converges to x = 0.

Topic 7: Hessian & Gradient (Rosenbrock Function — PYQ 2024)

Q9. Compute ∇f and ∇²f for f(x) = 100(x₂ - x₁²)² + (1 - x₁)². Show x = (1,1) is the minimizer.*

Gradient:

• ∂f/∂x₁ = 100·2(x₂-x₁²)·(-2x₁) + 2(1-x₁)·(-1) = -400x₁(x₂-x₁²) - 2(1-x₁)

• ∂f/∂x₂ = 100·2(x₂-x₁²) = 200(x₂-x₁²)

At (1,1): ∇f = [-400·1·0 - 0, 200·0] = [0, 0] ✓ (stationary point)

Hessian:

H = | -400(x₂-3x₁²) + 2 -400x₁ |

| -400x₁ 200 |

At (1,1):

H = | -400(1-3) + 2 -400 | = |802 -400|

 | -400 200| |-400 200|

det(H) = 802×200 - 400² = 160400 - 160000 = 400 > 0, and H₁₁ = 802 > 0 → H is positive definite → x*
= (1,1) is a local (and global) minimizer ✓

Quick Revision: Key Definitions for Viva

Unimodal function: A function that has exactly one local minimum (for minimization) in a given
interval. Essential for line search methods — both Golden Section and Fibonacci methods require
unimodality.

Convex set: A set S where for any two points x, y ∈ S, the line segment λx + (1-λ)y ∈ S for all λ ∈ [0,1].
Example: a circle and its interior is convex; a donut shape is not.

Global vs local maximum: A global maximum is the highest value of f over the entire domain. A local
maximum is highest only in some neighborhood. For f(x) = x³ - 12x² + 36x + 17 on [1,10]: compute
f'(x) = 3x²-24x+36 = 0 → x = 2 and x = 6 are critical points; check endpoints x=1 and x=10 too for
global max.

Reduced cost (Simplex): cⱼ - zⱼ for non-basic variables. If all ≤ 0 (for max), current solution is optimal.
If any = 0, multiple optima exist. If any > 0, improve by pivoting.

Saddle point: For f(x,y) = 8x₁ + 12x₂ + x₁² - 2x₂²: find critical point, compute Hessian. If det(H) < 0 →
saddle point (neither max nor min).

The topics to prioritize most are: Simplex Method, Lagrangian optimization (especially the
closest/farthest on a circle type), Conjugate Gradient, convex function checking, and LPP
formulation + graphical method — these appear in both papers and in both sections.