Numerical Optimization Methods

From-scratch implementations of classical optimization algorithms in Python, covering both unconstrained and constrained optimization. Built with NumPy and SymPy — no optimization libraries used. Includes step-by-step derivations, symbolic solutions, and publication-quality visualizations.

---

Notebooks

1. Unconstrained Optimization (unconstrained_optimization.ipynb)

Objective: Minimize f(x, y) = x² + y² | Starting point: x₀ = [4, 2]

Method	Final x	f(x*)	Iterations
Gradient Descent (η=0.1)	[2.048, 1.024]	5.243	3
Steepest Descent (exact line search)	[0, 0]	0	1
Newton's Method	[0, 0]	0	1
BFGS (Quasi-Newton, H₀=I)	[0, 0]	0	1

Methods covered:

• Gradient Descent — fixed step size η=0.1, update: xₖ₊₁ = xₖ − η∇f(xₖ)
• Steepest Descent — exact line search α = (g·x)/(g·g), converges in 1 step
• Newton's Method — uses Hessian inverse: xₖ₊₁ = xₖ − [∇²f]⁻¹∇f(xₖ)
• BFGS — Quasi-Newton with BFGS Hessian update, H₀ = I

---

2. Constrained Optimization (constrained_optimization.ipynb)

Objective: Minimize f(x, y, z) = 2x² + 4y² + 6z²
Subject to: x + y + z = 3 and x − z = 1

Method	x*	y*	z*	f*
Lagrange (2-var)	0.6667	0.3333	—	1.3333
Lagrange (3-var, 2 constraints)	1.5833	0.8333	0.5833	9.8333
Matrix Form Lagrange	verified ✓	verified ✓	—	verified ✓
KKT Conditions	(0, 0)	—	—	0

Methods covered:

• Lagrange Multipliers (2-var) — symbolic solution via SymPy, stationarity conditions
• Lagrange Multipliers (3-var, 2 equality constraints) — dual multipliers λ₁, λ₂
• Matrix Form — xᵀAx subject to cᵀx = 1 using A⁻¹
• KKT Conditions — inequality constraints with complementary slackness, case analysis
• Equality + Inequality — candidate point evaluation on constraint boundary

---

Key Concepts Demonstrated

Unconstrained:                    Constrained:
─────────────────────────         ─────────────────────────
∇f(x) = 0  (first-order)         L = f + λᵀg  (Lagrangian)
∇²f > 0    (second-order)        ∂L/∂x = 0   (stationarity)
                                  KKT: μᵢgᵢ = 0 (slackness)

---

Visualizations

Both notebooks include dark-theme contour plots showing:

• Optimization paths for each method on f(x,y) contours
• Constraint boundaries and feasible regions
• Convergence trajectories from x₀ to x*

---

Setup & Run

1. Clone the repository

git clone https://github.com/mirnawalid/numerical-optimization.git
cd numerical-optimization

2. Install dependencies

pip install -r requirements.txt

3. Open notebooks

jupyter notebook

Open unconstrained_optimization.ipynb or constrained_optimization.ipynb and run all cells.

---

Project Structure

numerical-optimization/
├── unconstrained_optimization.ipynb   # Gradient Descent, Steepest Descent, Newton, BFGS
├── constrained_optimization.ipynb     # Lagrange Multipliers, KKT, Matrix Form
├── requirements.txt
├── .gitignore
└── README.md

---

Tech Stack

Category	Library
Symbolic math	SymPy
Numerical computation	NumPy
Visualization	Matplotlib
Notebook	Jupyter

---

Author

Mirna Walid
AI Science Student — Galala University, Faculty of Computer Science & Engineering
+20 109031364 | mws103561@gu.edu.eg
LinkedIn · GitHub