wiki:FirstPrinciples/ReductionToALocalOptimum

Reduction To A Local Optimum

An optimum is a value such that any change will produce a worse result. Think of a tip of mountain...

This is also the definition of perfection - Perfection is obtained not when there is nothing more to add, but when there is nothing more to remove.

This is also the notion of a balance (a balanced system), an equilibrium. Homeostasis is the proper balance of (and between) all major subsystems of an organism.

The notion of a global optimum depends on the domain. The tip of the Everest is a global optimum in the domain of 8000-meter summits. The notion of a local optimum is that there are a lot of high mountains in the world.

Fixed Point

The notion of a Fixed Point is a Global Optimum of a convex function.

Fixed Point of a function is a value such that a function applied to it produces the same value.

This means that the function converges to its optimum.

For less abstract purposes the function encapsulates a test - usually a predicate.

(define (fixed-point f start)
    (define (iterate old new)
        (if (good-enough? old new) 
            new     
            (iterate new (f new))))
    (iterate start (f start)))

Good-Enough

The processes of Nature are vastly complex, so we usually could not hope for finding (or even defining!) a global optimum. We, mere mortals, could define a predicate - how small is the difference between an ideal and what we really have (are we close enough to the unattainable ideal?).

(define (good-enough? value)
    (< (abs (- ideal value)) tolerance))

An ideal is justified to be a global binding (a constant, of course! or wait...)

Newton's Method

better and better successive approximations

Unless there is nothing to improve - improve''

(define (sqrt x)
    (define tolerance 0.00001)
    (define (good-enough? y)
        (< (abs (- (* y y) x)) tolerance))
    (define (improve y)
        (average (/ x y) y))
    (define (try y)
        (if (good-enough? y)
            y
            (try (improve y))))
    (try 1))
Last modified 2 years ago Last modified on Dec 18, 2017, 12:36:26 PM
Note: See TracWiki for help on using the wiki.