UNIT 2 — NON-LINEAR & DYNAMIC OPTIMIZATION

Exam-Oriented Full Revision Notes

BIG PICTURE OF UNIT 2

This unit has 3 major sections:

Section Topics

PART A Unconstrained Optimization

PART B Constrained Optimization

PART C Dynamic Programming

PART A — UNCONSTRAINED OPTIMIZATION

1. What is Unconstrained Optimization?

Definition
Unconstrained optimization means:

Finding the maximum or minimum value of a function WITHOUT any constraints on variables.

No:

•≤
•≥
• = constraints.

Only optimize the function.

General Form
Minimize or maximize:

1
f(x1, x2, …, xn)

without constraints.

REAL LIFE IDEA

Examples:

• minimizing cost
• minimizing error in machine learning
• maximizing profit
• minimizing energy

IMPORTANT TERMS
1. Objective Function
The function to optimize.

Example

f(x) = x² + 4x + 5

2. Local Optimum
Best nearby point only.

3. Global Optimum
Best point in entire domain.

4. Unimodal Function
Only ONE minimum/maximum.

Easy to solve.

2
5. Multimodal Function
Many local minima/maxima.

Harder to solve.

METHODS OF UNCONSTRAINED OPTIMIZATION

Your syllabus includes:

1. Gradient Descent
2. Newton’s Method
3. Quasi-Newton Method

These are VERY IMPORTANT for the exam.

2. Gradient Descent
One of the MOST IMPORTANT TOPICS.

BASIC IDEA
To minimize a function: move in the direction opposite to gradient.

Because:

• gradient points upward

• negative gradient points downward

UPDATE RULE
x(k+1) = x(k) − α∇f(xk)

Where:

• xk = current point
• α = learning rate / step size
• ∇f(xk) = gradient

3
EXAM SENTENCE
Gradient Descent is an iterative optimization algorithm used to minimize a function by
moving in the direction opposite to the gradient.

WRITE THIS EXACTLY.

STEPS OF GRADIENT DESCENT

Step 1
Find derivative:

f′(x)

Step 2
Choose initial point:

x0

Step 3
Choose learning rate:

Step 4
Apply update formula repeatedly.

4
IMPORTANT: LEARNING RATE
Small α
• slow convergence

Large α
• overshooting/divergence

TYPES OF GRADIENT DESCENT

Very important theory question.

1. Batch Gradient Descent

Uses ALL training examples.

Advantages

• stable
• accurate

Disadvantages

• slow for large datasets

2. Stochastic Gradient Descent (SGD)

Uses ONE random sample.

Advantages

• faster

Disadvantages

• noisy updates

5
3. Mini-Batch Gradient Descent
Uses small groups (batches).

MOST COMMON in deep learning.

Balances:

• speed
• stability

NUMERICAL — GRADIENT DESCENT

Problem
Minimize:

f(x) = x² + 4x + 4

Derivative:

f′(x) = 2x + 4

Take:

• x0 = 0
• α = 0.1

Iteration 1
x1 = x0 − αf′(x0)

x1 = 0 − 0.1(4)

x1 = −0.4

Iteration 2
f′(−0.4) = 3.2

6
x2 = −0.4 − 0.1(3.2)

x2 = −0.72

Continue until convergence.

ADVANTAGES OF GRADIENT DESCENT

1. Simple
2. Easy implementation
3. Useful for large problems
4. Used in machine learning

DISADVANTAGES
1. Slow convergence
2. Can get stuck in local minima
3. Sensitive to learning rate

3. NEWTON’S METHOD
HIGHLY IMPORTANT.

Usually asked:

• theory
• derivation
• numerical
• advantages/disadvantages

BASIC IDEA
Gradient Descent uses only:

• first derivative

7
Newton’s Method uses:

• first derivative
• second derivative (Hessian)

Hence: FASTER convergence.

NEWTON UPDATE RULE

x(k+1) = x(k) − H−1(xk)∇f(xk)

Where:

• H(xk) = Hessian matrix

WHAT IS HESSIAN MATRIX?

Matrix of second derivatives.

For two variables:

H = [ ∂²f/∂x1² ∂²f/∂x1∂x2 ∂²f/∂x2∂x1 ∂²f/∂x2² ]

STEPS OF NEWTON METHOD

Step 1
Find gradient.

Step 2
Find Hessian matrix.

Step 3
Choose initial point.

8
Step 4
Apply Newton formula.

Step 5
Repeat until gradient becomes zero.

IMPORTANT RESULT
Newton’s method finds minimum of quadratic function in ONE iteration.

VERY IMPORTANT theory line.

SIMPLE NUMERICAL
Problem
Minimize:

f(x) = x² − 4x + 5

Solution

Derivative

f′(x) = 2x − 4

Second Derivative

f′′(x) = 2

Take:

x0 = 1

9
Newton Update
x1 = x0 − f′(x0)/f′′(x0)

x1 = 1 − (−2/2)

x1 = 2

Now:

f′(2) = 0

Hence minimum occurs at:

x=2

ADVANTAGES OF NEWTON METHOD

1. Faster convergence
2. Less iterations
3. Accurate near optimum

DISADVANTAGES
1. Hessian computation expensive
2. Matrix inversion needed
3. Difficult for large problems
4. Sensitive to initial guess

DIFFERENCE:

GRADIENT DESCENT vs NEWTON METHOD

Gradient Descent Newton Method

Uses first derivative Uses first + second derivative

Slow Fast

Simple Computationally expensive

10
 Gradient Descent Newton Method

No Hessian Requires Hessian

Linear convergence Quadratic convergence

VERY IMPORTANT table.

4. QUASI-NEWTON METHOD
IMPORTANT THEORY TOPIC.

BASIC IDEA
Newton method is fast BUT: computing Hessian is expensive.

Quasi-Newton methods: APPROXIMATE Hessian instead of exact Hessian.

DEFINITION
Quasi-Newton methods are optimization methods that approximate the Hessian matrix using
gradient information.

KEY IDEA
Instead of:

use approximation:

POPULAR METHODS
1. BFGS
2. DFP

11
 3. SR1

Write at least BFGS in exam.

ADVANTAGES
1. Faster than gradient descent
2. Cheaper than Newton method
3. Good convergence

DISADVANTAGES
1. Approximation errors
2. Complex implementation

PART B — CONSTRAINED OPTIMIZATION

Topics:

• Lagrange Multipliers
• KKT Conditions

VERY IMPORTANT.

5. LAGRANGE MULTIPLIERS
Used when optimization has equality constraints.

GENERAL PROBLEM
Optimize:

f(x,y)

subject to:

g(x,y)=0

12
LAGRANGIAN FUNCTION
L(x,λ)=f(x)+λg(x)

CONDITIONS
∂L/∂x = 0

∂L/∂y = 0

∂L/∂λ = 0

Solve simultaneously.

INTERPRETATION
Lagrange multiplier measures sensitivity of objective function to constraint.

6. KKT CONDITIONS
(Karush-Kuhn-Tucker)

MOST IMPORTANT TOPIC OF UNIT 2.

University favorite.

WHY KKT?
Lagrange works mainly for equality constraints.

KKT extends it to:

• inequality constraints

13
GENERAL FORM
Minimize:

f(x)

subject to:

gi(x) ≤ 0

KKT CONDITIONS
There are FOUR conditions.

MEMORIZE THEM.

1. Stationarity
Gradient of Lagrangian = 0

∇f(x) + ∑λi∇gi(x) = 0

2. Primal Feasibility
Constraints satisfied:

gi(x*) ≤ 0

3. Dual Feasibility
λi ≥ 0

4. Complementary Slackness
MOST IMPORTANT.

14
λigi(x*) = 0

Meaning: Either:

• constraint active OR

• multiplier zero

IMPORTANT CONCEPT:

CONVEX vs CONCAVE
For minimization:

• objective should be convex

For maximization:

• objective should be concave

VERY IMPORTANT theory line from your notes.

KKT SOLVING PROCEDURE

Step 1
Write constraints in standard form.

Step 2
Construct Lagrangian.

Step 3
Find derivatives.

Step 4
Apply KKT conditions.

15
Step 5
Solve cases.

Step 6
Check feasibility.

COMMON EXAM QUESTIONS

1. State KKT conditions.
2. Explain KKT conditions.
3. Solve NLPP using KKT.

VERY HIGH probability.

PART C — DYNAMIC PROGRAMMING

VERY THEORY-ORIENTED topic.

Easy scoring if memorized properly.

7. DYNAMIC PROGRAMMING (DP)

DEFINITION
Dynamic Programming is a mathematical optimization technique that solves complex
problems by dividing them into overlapping subproblems.

FATHER OF DP
Richard Bellman.

IMPORTANT FACT.

16
PRINCIPLE OF OPTIMALITY
MOST IMPORTANT DP THEORY.

Definition
An optimal solution contains optimal solutions to its subproblems.

OR

Whatever the initial state and decision are, the remaining decisions must constitute an
optimal policy.

WRITE THIS EXACTLY.

TWO IMPORTANT PROPERTIES OF DP

1. Optimal Substructure
Optimal solution built from optimal subproblem solutions.

2. Overlapping Subproblems
Same subproblems repeat.

DP stores results instead of recalculating.

DP COMPONENTS
1. Stages
Decision points.

Examples:

• months
• levels
• cities

17
2. States
Condition/status at a stage.

3. Decisions
Choices available.

4. Recursive Relation
(Bellman Equation)

Connects present stage to future optimal cost.

DP APPROACHES
1. Top-Down (Memoization)
Uses recursion + memory.

2. Bottom-Up (Tabulation)
Build solution from smallest subproblems upward.

APPLICATIONS OF DP
VERY IMPORTANT LONG QUESTION.

1. Shortest Path
Find shortest route in multistage graph.

2. Inventory Management
Minimize storage + production cost.

18
3. Project Scheduling
Optimal resource/time allocation.

4. Resource Allocation
Distribute limited resources optimally.

ADVANTAGES OF DP
1. Reduces repeated computation
2. Efficient
3. Solves complex optimization problems

DISADVANTAGES
1. Large memory usage
2. Complex formulation
3. Difficult state definition

MOST IMPORTANT QUESTIONS FOR EXAM

VERY HIGH PRIORITY:

1. Gradient Descent
2. Newton’s Method
3. KKT Conditions
4. Principle of Optimality
5. DP applications
6. Difference between Gradient Descent & Newton Method
7. Advantages/disadvantages
8. Numerical on Newton/KKT

19
30-HOUR STRATEGY FOR THIS UNIT
FIRST PASS (2–3 hrs)
Read entire notes once.

SECOND PASS (2 hrs)

Memorize:

• formulas
• definitions
• conditions
• differences

THIRD PASS (2 hrs)

Practice:

• Gradient Descent numerical

• Newton numerical
• KKT numerical

GOLDEN EXAM LINES

Gradient Descent
Moves opposite to gradient to minimize function.

Newton Method
Uses first and second derivatives for faster convergence.

KKT
Necessary conditions for constrained nonlinear optimization.

20
Principle of Optimality
Optimal solution contains optimal solutions of subproblems.

END OF UNIT 2 NOTES

21