Golden Section Search algorithm
- User
Golden Section Search algorithm
Assistant
I'll explain the Golden Section Search algorithm, which is an efficient method for finding the minimum or maximum of a unimodal function within a specified interval.
Key Characteristics
The Golden Section Search is a numerical optimization technique with several important properties:
-
Efficiency: It converges quickly to the optimal point without requiring derivative information. The algorithm reduces the search interval by a constant factor in each iteration, making it more efficient than linear search methods.
-
Unimodal Function Requirement: The algorithm works best with unimodal functions, which have a single minimum or maximum within the search interval. This means the function either increases and then decreases, or decreases and then increases.
Algorithm Steps
Here's a detailed breakdown of the Golden Section Search algorithm:
-
Initial Setup
- Choose an initial interval [a, b] containing the potential optimum
- Calculate the golden ratio φ ≈ 1.618 (precisely (1 + √5) / 2)
- Compute two interior points x1 and x2 within the interval
-
Interval Reduction
- Evaluate the function at x1 and x2
- Based on the function values, eliminate part of the interval
- Maintain a consistent interval reduction strategy
-
Convergence
- Repeat the interval reduction process
- Stop when the interval becomes sufficiently small
Pseudocode
def golden_section_search(f, a, b, tolerance=1e-5): golden_ratio = 1.618034 # φ # Initial interior points x1 = b - (b - a) / golden_ratio x2 = a + (b - a) / golden_ratio while abs(b - a) > tolerance: # Compare function values at interior points if f(x1) < f(x2): b = x2 x2 = x1 x1 = b - (b - a) / golden_ratio else: a = x1 x1 = x2 x2 = a + (b - a) / golden_ratio return (a + b) / 2Advantages
- Does not require derivative calculations
- Works well for smooth, unimodal functions
- Guaranteed convergence
- Relatively simple implementation
Limitations
- Requires a unimodal function
- Less effective for multimodal or discontinuous functions
- Assumes a single minimum/maximum within the interval
Practical Applications
- Optimization problems in mathematics
- Engineering design optimization
- Economic modeling
- Machine learning hyperparameter tuning
Mathematical Insight
The algorithm leverages the golden ratio's unique mathematical properties. By consistently reducing the interval using a fixed proportion, it efficiently narrows down the search space.
The key is maintaining two interior points that allow systematic interval reduction without recomputing all previous points.
Complexity
- Time Complexity: O(log(1/ε)), where ε is the tolerance
- Space Complexity: O(1)
Would you like me to elaborate on any specific aspect of the Golden Section Search algorithm?
-
- User
implement in modern fortran
Assistant
Here's a modern Fortran implementation of the Golden Section Search algorithm with several contemporary Fortran features:
module golden_section_search_mod implicit none private public :: golden_section_search contains ! Generic interface for function to be minimized pure function golden_section_search(func, a, b, tolerance) result(x_min) ! Interfaces and type declarations interface pure function func(x) result(f_value) real, intent(in) :: x real :: f_value end function func end interface ! Input parameters real, intent(in) :: a ! Lower bound of search interval real, intent(in) :: b ! Upper bound of search interval real, intent(in), optional :: tolerance ! Convergence tolerance ! Result variable real :: x_min ! Local variables real, parameter :: GOLDEN_RATIO = 1.618033988749895_real64 real, parameter :: DEFAULT_TOLERANCE = 1.0e-8_real64 real :: x1, x2, current_tolerance real :: f1, f2 ! Set tolerance current_tolerance = merge(tolerance, DEFAULT_TOLERANCE, present(tolerance)) ! Initial interior points x1 = b - (b - a) / GOLDEN_RATIO x2 = a + (b - a) / GOLDEN_RATIO ! Search loop search_loop: do while (abs(b - a) > current_tolerance) ! Evaluate function at interior points f1 = func(x1) f2 = func(x2) ! Interval reduction strategy if (f1 < f2) then b = x2 x2 = x1 x1 = b - (b - a) / GOLDEN_RATIO else a = x1 x1 = x2 x2 = a + (b - a) / GOLDEN_RATIO end if end do search_loop ! Return midpoint of final interval x_min = (a + b) / 2.0_real64 end function golden_section_search ! Example test function pure function example_function(x) result(f) real, intent(in) :: x real :: f ! Quadratic function with known minimum f = x**2 + 2*x + 1 end function example_function end module golden_section_search_mod program test_golden_section use, intrinsic :: iso_fortran_env, only: real64 use golden_section_search_mod implicit none real(real64) :: result real(real64), parameter :: lower_bound = -10.0_real64 real(real64), parameter :: upper_bound = 10.0_real64 ! Find minimum of example function result = golden_section_search(example_function, lower_bound, upper_bound) print *, "Minimum found at x =", result print *, "Function value at minimum =", example_function(result) end program test_golden_sectionKey Modern Fortran Features Demonstrated
-
Module-Based Design
- Encapsulates algorithm in a module
- Provides clear separation of concerns
- Uses
privateandpublicfor controlled access
-
Pure Functions
purekeyword ensures no side effects- Enables compiler optimizations
- Supports functional programming paradigms
-
Interfaces
- Generic function interface for input function
- Allows passing different function types
-
Optional Arguments
toleranceis an optional parameter- Uses
merge()for default value handling
-
Explicit Real Kind
- Uses
real64for double precision - Explicit precision specification
_real64literal suffix
- Uses
-
Modern Control Structures
- Named
doloop withsearch_loop - Explicit loop termination condition
- Named
-
Intrinsic Modules
- Uses
iso_fortran_envfor kind parameters
- Uses
Advantages of This Implementation
- Type-safe
- Flexible function input
- High performance
- Clear, readable code
- Supports generic optimization scenarios
Potential Improvements
- Add error handling for invalid intervals
- Implement maximum iteration limit
- Support different optimization objectives (minimize/maximize)
Example Use Cases
! Minimize a custom function result = golden_section_search(my_complex_function, -5.0, 5.0) ! Use custom tolerance result = golden_section_search(my_function, 0.0, 1.0, tolerance=1.0e-10)Performance Considerations
- Compile with optimization flags (
-O3) - Use profiling to verify performance
- Consider inlining for small functions
Would you like me to elaborate on any aspect of this implementation or discuss optimization strategies?
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.