Aristotle University of Thessaloniki (AUTH)
Department of Electrical and Computer Engineering
Course: Optimization Techniques
This repository contains MATLAB implementations of classical numerical optimization methods, developed as coursework for the Optimization Techniques course at AUTH ECE. The scope spans single-variable interval reduction, gradient-based unconstrained minimization, constrained projection methods, and population-based evolutionary search. Each module is self-contained and accompanied by a formal technical report.
This module implements and benchmarks iterative interval-reduction algorithms for minimizing convex functions of one variable over the bounded interval [-1, 3]. The mathematical objective is to quantify computational cost — measured in objective function evaluations — as a function of convergence tolerance ε and target final interval length l, across three distinct test functions, revealing the trade-off between method sophistication and evaluation efficiency.
- Define three convex objective functions over the search interval
[-1, 3]. - Implement four search strategies: Bisection, Golden Section, Fibonacci, and Derivative-based Bisection.
- For each method, sweep
εand record the number of function evaluations required to converge. - For each method, sweep the target final interval length
land record the corresponding evaluation counts. - Track and plot the interval endpoint sequence
[a_k, b_k]across iterationskfor each function and method. - Compare results across all methods to quantify efficiency trade-offs.
- MATLAB — loop-based algorithm implementation, function evaluation counting, and 2D plotting of convergence metrics across parameter sweeps.
The module is structured parametrically to isolate each experimental variable independently: scripts are categorized first by search method, then by study type — evaluation count as a function of ε, evaluation count as a function of target interval length l, and endpoint trajectory plots per test function. This separation ensures that varying tolerance and varying interval length are never conflated in the same execution context, enabling clean cross-method comparison without shared computational state.
This module addresses the minimization of the multimodal, non-convex function f(x,y) = x⁵ · e^(-x² - y²), which exhibits multiple local extrema and a saddle point structure in the 2D search landscape. Three gradient-based solvers — Steepest Descent, Newton's Method, and Levenberg-Marquardt — are implemented and benchmarked under three distinct step-size selection strategies, with particular attention to numerical handling of negative-definite and singular Hessians that arise during Newton iterations near non-convex regions.
- Analytically derive and implement the gradient vector and Hessian matrix of the objective function.
- Visualize the 2D search landscape via surface and contour plots to identify critical points structurally.
- Implement three solvers: Steepest Descent, Newton's Method, and Levenberg-Marquardt.
- For each solver, apply three step-size strategies: constant step
γ, exact line search (minimization off(x_k + γ_k d_k)), and the Armijo backtracking rule. - Execute each solver from multiple starting points; record iteration counts, convergence trajectories, and final function values.
- Compare convergence speed, stability, and behavior near ill-conditioned Hessian regions across all solver–strategy combinations.
- MATLAB — numerical differentiation, matrix inversion and regularization, iterative solver loops, convergence plotting, and multi-configuration benchmarking.
The architecture isolates each solver–strategy combination into a self-contained script with no shared state across configurations, allowing any single combination to be executed, profiled, or modified independently without side effects on the remaining configurations. A dedicated visualization script for the objective function surface and contour plots is decoupled from all solver scripts, ensuring that the analytical characterization of the search landscape is reproducible independently of any particular solver run.
This module solves a constrained minimization problem over a convex quadratic objective function using the Projected Steepest Descent method. The feasible set is defined by a system of linear inequality constraints, and at each iteration the unconstrained gradient step is projected back onto the feasible region. The study systematically varies the step-size parameter γ across theoretically meaningful thresholds to demonstrate the stability bounds derived analytically, and to observe the onset of oscillatory and divergent behavior when those bounds are exceeded.
- Define the constrained quadratic optimization problem and characterize the feasible set via its linear inequality representation.
- Implement unconstrained Steepest Descent as a baseline convergence reference.
- Implement the Projected Gradient update:
x_{k+1} = P[x_k − γ ∇f(x_k)], whereP[·]denotes Euclidean projection onto the feasible set. - Derive theoretical bounds on the step-size parameter
γfor guaranteed convergence. - Execute the projected algorithm for three distinct values of
γ, recording convergence trajectories and iteration counts for each. - Analyze stable versus oscillatory or divergent behavior in relation to the theoretical stability bounds.
- MATLAB — quadratic form evaluation, gradient computation, iterative projection loop, and convergence trajectory visualization.
The module is structured parametrically around the step-size parameter γ, with each experimental configuration encoded in an independent script so that the effect of that single variable on projected-gradient stability is directly observable in isolation. This design makes the transition from convergent to oscillatory to divergent regimes immediately reproducible by running scripts sequentially, without any inter-script dependency or shared workspace state that could obscure the causal relationship between the projection step magnitude and algorithmic behavior.
This module applies a Genetic Algorithm to minimize total vehicle traversal time across a directed road network of 17 links, subject to link capacity constraints and flow conservation equations at each node. The fitness function encodes network travel time as a nonlinear function of the flow distribution vector, and the optimizer must satisfy both equality constraints (flow conservation) and inequality constraints (capacity bounds) simultaneously. The model is evaluated under a nominal demand scenario and under a demand uncertainty sweep to characterize sensitivity of the optimal flow distribution to changes in incoming traffic volume.
- Model the road network as a directed graph; define the flow conservation equations and link capacity constraints in matrix form.
- Formulate the fitness function as total vehicle traversal time expressed as a function of the flow vector.
- Configure the GA operator parameters: Roulette Wheel selection, 80% crossover rate, 1% mutation rate.
- Run the GA solver for the nominal demand scenario (
V = 100); record the optimal flow distribution and minimum total travel time. - Sweep the incoming vehicle rate from
V = 85toV = 115; re-run the GA at each demand level. - Analyze and plot the evolution of optimal cost and flow distribution under varying demand to identify network congestion thresholds.
- MATLAB — network constraint formulation, fitness function implementation, result post-processing, and visualization.
- MATLAB Global Optimization Toolbox — provides the
ga()solver used for population-based evolutionary search; required for Genetic Algorithm execution.
Constraint matrices encoding flow conservation equalities and capacity bound inequalities are constructed programmatically within each script and passed directly to ga(), rather than stored as external data files or shared global state. The nominal scenario and the demand sweep are implemented as separate, self-contained scripts so that the constraint-building logic for each case is co-located with its solver configuration, making the mapping from network topology to optimization problem fully traceable within a single readable file per experimental condition.
Prerequisites: MATLAB R2020a or later. Module 4 additionally requires the Global Optimization Toolbox.
1. Clone the repository
git clone https://github.com/eleanazeri/Optimization-Techniques.git
cd Optimization-Techniques2. Navigate to the module of interest
cd 01-1D-Search-Methods3. Execute a script in the MATLAB Command Window
cd('path/to/01-1D-Search-Methods')
run('bisection_evals_vs_epsilon.m')Each module is self-contained. Refer to the inline comments within each script for parameter configuration, stopping criteria, and expected outputs.
This repository is intended for academic reference. All work is original unless otherwise cited within the accompanying technical reports.