Simple question about how the optimizer works

[Robin Becker]

In article <mailman.1021037239.26792.python-list at python.org>, James J. Besemer <jb at cascade-sys.com> writes
......
>Personally I very much prefer the term "pattern" as that's how I learned to 
>think
>about this class of algorithms back when I studied AI.  There are strong 
>parallels
>between global optimization and a lot of AI algorithms.
.........
I don't disagree with much of what you say. I think the patters or tree patterns idea
is common in many branches of discrete optimisation.
>> The problem of code optimisation problem is
>> approximately
>>
>> choose c to optimise F(c,X(c,d))
>>       such that X(c,d)=S(p,d)
>> c=code
>> p=program
>> d=program data
>> F=utility function ie code size/speed etc
>> X=execution function
>> S=semantic function
.........

I guess what you're describing is a feasible set approach. 
ie we are assuming that there exists a feasible c with X(c,d)=S(p,d)
(ie we have a working compiler of some sort). Given c there are
transformations that preserve feasibility (these correspond to patterns)
so that T1(c)=c1 with X(Ti(c),d) = X(c,d). (This approach applies
in the input p space as well).

Clearly we want to choose the transformations such that the cost improves,
but in optimisation this is still a 'local' method as it remains to be proved
for any particular domain that the local neighbourhood optimisations converge
to a global optimum. In practice what we want is that Ti(c) can lead to any
feasible c. Such a pattern is pretty large imho :)

There are many examples in mathematics where apparently sensible rules leads to
trouble eg the steepest ascent rule doesn't have good convergence to the top of
a hill even in the absence of constraints.
-- 
Robin Becker