1.
Dichotomous Search
Goal: Minimize a unimodal function f (x)over interval [a , b]
✅ Step-by-Step Procedure:
1. Choose parameters:
o Small number ϵ >0 (e.g., ϵ=10−5)
o Tolerance δ for stopping (e.g., δ=10−3)
2. Repeat until b−a< δ :
a+ b
o Compute midpoint: m=
2
o Evaluate two points:
x 1=m−ϵ
x 2=m+ϵ
o Compare:
If f (x 1)< f (x 2): set b=x 2
Else: set a=x 1
3. Return:
a+b
o Approximate minimum at
2
🔢 2. Fibonacci Search
Goal: Minimize f (x)over [a , b]using Fibonacci numbers
✅ Step-by-Step Procedure:
1. Choose total number of iterations n based on desired accuracy:
o Use Fibonacci numbers F 0 , F 1 , ... , F nwhere F k =F k−1+ F k−2
2. Initialize:
o Compute two interior points:
F n−2
x 1=a+ (b−a)
Fn
F n−1
x 2=a+ (b−a)
Fn
3. Repeat for k =n , n−1 , ... ,2:
o Evaluate f (x 1)and f (x 2)
o If f (x 1)< f (x 2):
Set b=x 2
Update x 2=x 1
F k−3
Recompute x 1=a+ (b−a)
F k−1
o Else:
Set a=x 1
Update x 1=x 2
F k−2
Recompute x 2=a+ (b−a)
F k−1
4. Return:
a+b
o Approximate minimum at
2
🟡 3. Golden Section Search
Goal: Minimize f (x)over [a , b]using the golden ratio
✅ Step-by-Step Procedure:
1. Define golden ratio:
ϕ=
√ 5−1 ≈ 0.618
2
2. Initialize:
o Compute:
x 1=a+(1−ϕ)(b−a)
x 2=a+ ϕ (b−a)
3. Repeat until b−a< δ :
o Evaluate f (x 1)and f (x 2)
o If f (x 1)< f (x 2):
Set b=x 2
Update x 2=x 1
Recompute x 1=a+(1−ϕ)(b−a)
o Else:
Set a=x 1
Update x 1=x 2
Recompute x 2=a+ ϕ (b−a)
4. Return:
a+b
o Approximate minimum at
2
Would you like me to turn this into a printable study sheet or overlay it with a visual diagram
for each method?
printable study sheet
Study Notes: Derivative-Based Root-
Finding Methods
🔹 1. Bisection Method (Not derivative-
based, but often grouped with Newton
for comparison)
✅ Applicability:
Function must be continuous on interval [a , b]
f (a)⋅f (b)< 0(i.e., root lies between a and b )
🔁 Iterative Formula:
a+ b
Let c=
2
If f (c )=0: root found
If f (a)⋅f (c)<0 : set b=c
Else: set a=c
Repeat until ∣b−a ∣<ϵ (tolerance)
📐 Convergence:
Linear
Guaranteed if conditions are met
🧮 Example:
Solve f (x)=x3 −x−2in [1, 2]
1. f (1)=−2, f (2)=4 → sign change
2. c=1.5 , f (1.5)=0.875
3. New interval: [1, 1.5]
4. Repeat until desired accuracy
2. Newton-Raphson Method
✅ Applicability:
Function must be differentiable
Good initial guess required
🔁 Iterative Formula:
f (x n )
x n+1=x n −
f ' (x n)
📐 Convergence:
Quadratic (fast if close to root)
May diverge if guess is poor or f ' ( xn )=0
🧮 Example:
Solve f (x)=x3 −x−2
1. f (x)=x3 −x−2, f ' ( x)=3 x 2−1
2. Initial guess: x 0=1.5
3. Compute:
x 1=1.5−¿ ¿
4. Repeat until ∣ x n+ 1−x n ∣<ϵ
🧠 Comparison Table
Method Requires Derivative Convergence Robustness Speed
Bisection ❌ No Linear Very High Slow
Newton-Raphson ✅ Yes Quadratic Moderate Fast
📌 Tips for Solving Problems
Always plot the function if possible to choose a good initial guess.
For Newton-Raphson, ensure f ' ( x)is not zero or near-zero.
Use Bisection for guaranteed convergence; Newton for speed
Optimization for Data Science – Study Notes
1. 🧭 Line and Line Segment
Line: All points on the line passing through x 1and x 2in Rn :
n
{ y ∈ R : y =λ x 1+(1− λ)x 2 , λ ∈ R }
Line Segment: Points between x 1and x 2:
n
LS [x 1 , x 2 ]={ y ∈ R : y=λ x 1 +(1−λ) x2 , λ ∈[0 ,1]}
Example: Let x 1=(1, 2), x 2=(3 , 4), and λ=0.5:
y=0.5(1 , 2)+0.5 (3 , 4)=(2 ,3)
2. 🧮 Affine Sets
Definition: A set X ⊆ Rn is affine if:
∀ x 1 , x 2 ∈ X , ∀ λ ∈ R , λ x 1 +(1−λ) x 2 ∈ X
Generalization:
k k
∑ ❑ λ i x i ∈ X if ∑ ❑ λi=1
i=1 i=1
Examples:
o A single point
o A line, plane, or hyperplane
o Solution set of linear equations: {x ∈ R n : Ax=b }
3. 📐 Convex Sets
Definition: A set C ⊆ R nis convex if:
∀ x 1 , x 2 ∈C , ∀ λ ∈[0 , 1], λ x1 +(1−λ) x 2 ∈ C
Examples:
o Empty set, singleton, Rn
o Balls: B(x 0 ,r )
o Affine sets
o Line segments
Theorems:
o Intersection of convex sets is convex
o Sum of convex sets: C 1+C 2is convex
o Scalar multiplication: aC is convex for any scalar a
4. 🧊 Hyperplanes and Half-Spaces
Hyperplane:
n T
H={x ∈ R : a x=b }
a : normal vector
b : offset from origin
Half-Spaces:
T
o Positive: H +¿={x: a x≥ b }¿
T
o Negative: H −¿={x : a x≤ b }¿
Examples:
o In R1: a point divides the line
o In R2: a line divides the plane
o In R3: a plane divides space
5. 🧭 Convex Hull
Definition: The smallest convex set containing a set S:
conv (S)=⋂ {C :C is convex and S ⊆C }
Examples:
o conv ({ x , y })=LS [x , y ]
o If S={(x , 0): x ∈ R }∪{(0 , y ): y ∈ R } , then conv (S)=R 2
6. 📉 Convex and Concave Functions
Convex Function:
f (λ x 1+(1− λ) x 2 )≤ λf (x 1)+(1−λ)f (x 2)
Concave Function:
f (λ x 1+(1− λ) x 2 )≥ λf (x 1)+(1−λ)f (x 2)
Visual Test:
o Convex: lies below the chord connecting two points
o Non-convex: may lie above the chord
Example:
f (x)=x is convex
2
o
f ( x)=−x is concave
2
o
🧭 1. Line and Line Segment Strategy
🔹 Problem Type:
Find whether a point lies on a line or within a line segment between two vectors.
🔹 Strategy:
Use the parametric form:
y= λ x1 +(1−λ) x 2
Check if the point satisfies this equation for some λ ∈[0 , 1](line segment) or λ ∈ R
(line).
🔹 Example:
Is y=(2 , 3) on the line segment between x 1=(1, 2)and x 2=(3 , 4)?
Solve:
y= λ(1 , 2)+(1−λ)(3 , 4)⇒(2 , 3)=λ(1 , 2)+(1− λ)(3 , 4)
Find λ : Solving gives λ=0.5, which is in [0, 1] ⇒ Yes, it lies on the segment.
🧮 2. Affine Set Strategy
🔹 Problem Type:
Verify if a set is affine or find if a point belongs to an affine set.
🔹 Strategy:
Use the definition:
λ x 1 +(1−λ)x 2 ∈ X ∀ λ ∈ R
For multiple points:
∑ λ i x i ∈ X if ∑ λi=1
🔹 Example:
Is the solution set of Ax=baffine?
Yes. Any linear combination of solutions with weights summing to 1 is also a solution.
📐 3. Convex Set Strategy
🔹 Problem Type:
Determine if a set is convex or prove convexity.
🔹 Strategy:
Use the convexity condition:
λ x 1 +(1−λ)x 2 ∈C ∀ λ ∈[0 , 1]
Use known properties:
o Affine sets are convex
o Balls, line segments, intersections of convex sets are convex
🔹 Example:
Prove that the intersection of two convex sets is convex.
Let x 1 , x 2 ∈ C1 ∩C 2
Since both sets are convex:
λ x 1 +(1−λ)x 2 ∈C 1 and C2 ⇒ λ x 1+(1− λ)x 2 ∈ C1 ∩C 2
🧊 4. Hyperplane and Half-Space Strategy
🔹 Problem Type:
Classify a point relative to a hyperplane or find the separating hyperplane.
🔹 Strategy:
Use the equation:
T
H={x : a x=b }
For classification:
a x> b: positive half-space
T
o
a x< b: negative half-space
T
o
🔹 Example:
Given a=(1 , 2), b=5, classify x=(1 ,1)
Compute:
T −¿¿
a x=1⋅1+2 ⋅1=3 <5 ⇒ x ∈ H
🧭 5. Convex Hull Strategy
🔹 Problem Type:
Find the convex hull of a set of points.
🔹 Strategy:
Use definition: Convex hull = all convex combinations of points in the set
For two points:
conv ({ x , y })=LS [x , y ]
🔹 Example:
Find the convex hull of S={(1 , 0),(0 , 1)}
Convex combinations:
λ (1 ,0)+(1−λ)(0 ,1)=( λ , 1−λ)⇒conv (S)={(λ ,1−λ): λ ∈[0 , 1]}
📉 6. Convex Function Strategy
🔹 Problem Type:
Verify convexity or use convexity in optimization.
🔹 Strategy:
Use definition:
f (λ x 1+(1− λ)x 2 )≤ λf (x 1)+(1−λ)f (x 2)
Use second derivative test:
o If f '' (x )≥ 0, then f is convex
🔹 Example:
Is f (x)=x2 convex?
Compute:
''
f (x )=2 ≥0 ⇒ Convex
To find the optimal step length ( \alpha ) that minimizes the quadratic function
[ \phi(\alpha) = 5\alpha^2 - 10\alpha + 8, ]
we use the vertex formula for a parabola:
🧮 Step-by-step:
This is a standard quadratic of the form: [ \phi(\alpha) = A\alpha^2 + B\alpha + C ] where:
(A=5)
( B = -10 )
The minimum occurs at: [ \alpha^* = -\frac{B}{2A} = -\frac{-10}{2 \cdot 5} = \frac{10}{10} = \
boxed{1} ]
✅ Final Answer:
[ \alpha = \boxed{1} ]
This value gives the exact step length that minimizes the function along a search direction—
perfect for line search in gradient-based optimization. Want to explore how this connects to
Wolfe conditions or backtracking strategies next?