Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-3-5-haiku-20241022· AnthropicHugging Face LMArena Human Preference 140K

Golden Section Search algorithm

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Geminigemini-2.5-pro’s answer.
  1. User

    Golden Section Search algorithm

  2. Claude 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:

    1. 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.

    2. 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:

    1. 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
    2. 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
    3. 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) / 2
    

    Advantages

    • 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

    1. Optimization problems in mathematics
    2. Engineering design optimization
    3. Economic modeling
    4. 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?

  3. User

    implement in modern fortran

  4. Claude 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_section
    

    Key Modern Fortran Features Demonstrated

    1. Module-Based Design

      • Encapsulates algorithm in a module
      • Provides clear separation of concerns
      • Uses private and public for controlled access
    2. Pure Functions

      • pure keyword ensures no side effects
      • Enables compiler optimizations
      • Supports functional programming paradigms
    3. Interfaces

      • Generic function interface for input function
      • Allows passing different function types
    4. Optional Arguments

      • tolerance is an optional parameter
      • Uses merge() for default value handling
    5. Explicit Real Kind

      • Uses real64 for double precision
      • Explicit precision specification
      • _real64 literal suffix
    6. Modern Control Structures

      • Named do loop with search_loop
      • Explicit loop termination condition
    7. Intrinsic Modules

      • Uses iso_fortran_env for kind parameters

    Advantages of This Implementation

    • Type-safe
    • Flexible function input
    • High performance
    • Clear, readable code
    • Supports generic optimization scenarios

    Potential Improvements

    1. Add error handling for invalid intervals
    2. Implement maximum iteration limit
    3. 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?

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.