Slides: 5 - Introduction to Spatial Optimization.pdf
Remember: local and global optima
Convex vs non-convex problems
Definition
A function is convex if, for any two points in its domain, the line segment connecting them lies above the graph of the function.
- Convex functions have one single global minimum
- No local minima
- All saddle points are global minima
Trade-off:
- (+) Trivial to optimize
- (+) Guaranteed convergence to global minimum
- (-) Can’t represent more complex problems → nuance is lost
Optimization methods
- Numerical optimization
- Heuristic methods
- Meta-heuristic methods
Numerical methods
- Rely on mathematical formulas and determonistic procedures to find optimal solutions
- Generally used when the problem is well-defined with an objective function that is continuous and differentiable
Examples:
- Gradient-based methods: gradient descent, Newton’s method
- Linear programming: simplex method, interior-point methods
- Quadratic programming: active set method
- Dynamic programming: Bellman’s Principle of Optimality
Heuristic methods
Heuristics are rule-of-thumb strategies designed to find good enough solutions quickly, often for problems that are too complex or time-consuming for exact methods
Do not guarantee an optimal solution!
Heuristics are often problem-specific
Examples:
- Greedy algorithms: Huffman coding, Kruskal’s MST algorithm
- Local search methods: hill climbing
Meta-heuristic methods
- Meta-heuristics are higher-level strategies that guide underlying heuristics to explore the search space more effectively.
- They are often used for complex, non-linear, and combinatorial problems where traditional methods may struggle.
- Meta-heuristics are often problem-agnostic and can be applied to a wide range of optimization problems.
- They are designed to avoid getting trapped in local optima and explore the search space more globally
Examples:
- Genetic Algorithms: Evolutionary processes inspired by natural selection.
- Particle Swarm Optimization: Simulates social behavior of birds or fish.
- Ant Colony Optimization: Mimics the foraging behavior of ants.
- Simulated Annealing: Combines probabilistic moves with gradual cooling of the system.
- Tabu Search: Uses memory structures to avoid cycles and escape local optima
Spatial Optimization
Definition
Spatial Optimization is the process of finding the most efficient arrangement or allocation of spatial elements within a given area to achieve specific objectives, considering constraints and utilizing spatial data
Consists of three components:
- Objective, decision variables, and constraints
- Often has one or more objective functions
- Objectives, decision variables and constraints are combined in some way to reflect the spatial problems of interest in either implicit or explicit terms, solved by exact or approximate techniques
Can be either continuous or discrete