Yet another term that we frequently hear, but which is often not properly understood, is the concept of optimization. What is optimization? And how does it work?
The idea of optimization is quite simple. You have some complex situation, where
some variable of interest (called the target) is based on a complex
relationship with some other variables. Optimization is the process of trying to find
an assignment of values to the other variables (called parameters) that produces a maximum or minimum value of the target variable, called
the optimum or optimal value
The practice of optimization is quite a bit harder. It depends greatly
on the relationships between the other variables. The general process of finding
an optimum is called programming – not like programming a computer; the term predates the invention of computers.
To make things a bit more formal, we can describe an optimization program in terms of geometry. An optimization problem can be described using a function
from a space S to a real number. The space S is some subset of a euclidean space ℜn for some N. So we have a function, f:S→ℜ, (that is, a function from the space S to a real number) which we call
the objective function if we’re looking for a maximum, or the cost function if we’re looking for a minimum.. Each point in S is called a potential or feasible solution for the objective function. The optimum of the objective function f is the point p in S where f(p) is at a maximum that is, p∈S: (∀x∈S:f(p)≥f(x). (If f is a cost function, jut replace the “≥” in the previous with “≤”.)
The space S is generally defined by a set of constraints, which are relationships between the variables/dimensions of S. If all of the constraints are
linear, and the objective/cost function is linear in terms of all of the variables,
then the solution process is called linear programming. Linear programming problem where all of the values of parameters in the solution must be integers is called an integer programming.
General linear programming – where the values of the variables in the solution can be any real number – is a very tractable problem, which can be solved very efficiently. Integer linear programming, on the other hand, is NP-hard – which is a very fancy way of saying that we have absolutely no clue of how to produce an optimal solution in a reasonable amount of time.
Linear programming turns out to be an extremely useful technique, which solves a large number of very common problems. Most problems of scheduling and resource distribution are ultimately reducible to linear programming. There’s an entire field of applied mathematical research called operations research (OR) which is devoted to optimization problems in general, and most work in OR is focused on finding solutions to linear programming problems, or to finding ways of characterizing different problems in terms of the simplest possible linear programming problem.
There’s also a form of optimization problem of particular interest to computer scientists. Given an optimization problem that has the property that finding the optimal solution involves combining the optimal solutions to multiple overlapping
subproblems, the solution technique is called dynamic programming. Dynamic programming works by computing and remembering the solutions to the subproblems, and then finding a way of combining a selection of the solutions to the subproblems to
create a solution to the full problem.
Hope you get to Genetic Algorithms. This relates to some of your other threads, such as evolution and anti-creationism. Sexual reproduction is my favorite form of optimization.
Re integer programming
In general, many linear programming problems have both integer and continuous variables; such problems are referred to as Mixed Integer Linear Programming problems (MILP). Pure integer and MILP problems can be solved using a technique known as branch and bound, which guarantees a global optimum if carried through to completion (it is always possible, in principle, to carry out a branch and bound to completion). This technique is particularly amenable to parallel processing techniques, which allows solutions with a large number of integer variables to be solved in a reasonable period of time (the computer requirements are heavily dependent on the number of integer variables).
This is a nice summary of what optimization means ; however there’s a technique that you’re not mentioning : constraint programming, i.e. reducing the domain of variables through constraint propagation until you get to the optimum. From my experience it can be better at solving problems than linear programming is.
I’d really be very interested in reading your opinions about this research field.
Some discussion of “hill climbing” and “telephone pole” spaces, and fitness landscapes, plase?
Following Pascal Brunot, I’d mention as an example “constraint-based modeling of metabolic networks” — which coincidently I was reading between my previous post and this one.
Patrick B. Warren, Janette L. Jones, “Duality, thermodynamics, and the linear programming problem in constraint-based models of metabolism”, Comments: 4 pages, 2 figures, 1 table
http://arxiv.org/pdf/q-bio.SC/0702021
I enjoyed it, but took exception to the early sentence:
“From the physical point of view, a metabolic reaction network is an excellent example of a system in a nonequilibrium steady state, since one can usually assume that the metabolite concentrations are are unchanging after a short transient relaxation period.”
Well, the short transient relaxation period that I did NOT neglect in my doctoral research is commonly called: the lifetime of the living organism.
Anyway, yes, do say something about constraint programming, as well as linear, nonlinear, genetic algorithms, and summarize in a nice table of advantages and disadvantages of each. Or something.
This was an excellent general presentation in a large subject. But I think the physical and mathematical view could be posed as perspectives.
In physics we have parameters and variables, but also constants. The problem defines which is which. For a simple example, while the extension x is of course the variable, the spring constant k could be a parameter (tunable spring) for a hanging mass with opposing forces F=kx=mg. But the gravitational acceleration g is normally constant, unless we move the spring system to the moon so g becomes a parameter too.
And in math, we have at least two types of problem. Looking for the point solution, IIRC the general linear optimum problem can be solved. It can also be solved with a simple constraint, and I believe it can now be solved with two independent constraints. Looking for the functional solution, we get calculus of variations.
Jonathan wrote
And when he does, I’ll doubtless start muttering again about biological evolution not being a ‘search’ process or optimization algorithm, but rather a process that finds satisficing ‘solutions’ as a side-effect of the operation of evolutionary operators. 🙂
RBH: Thanks for bringup up Satisficing, as sort of dual to optimization.
en.wikipedia.org/wiki/Satisficing
also:
“Satisficing is an alternative to optimization for cases where there are MULTIPLE and COMPETITIVE objectiveS in which one gives up the idea of obtaining a ‘best’ solution. In this approach one sets lower bounds for the various objectives that, if attained, will be ‘good enough’ and then seeks a solution that will exceed these bounds. The satisficer’s philosophy is that in real-world problems there are too many uncertainties and conflicts in values for there to be any hope of obtaining a true optimization and that it is far more sensible to set out to do ‘well enough’ (but better than has been done previously). (IIASA)”
“By evaluating all possible alternatives, the computation of an optimum strategy (see optimization theory) may not be feasible when the number of alternatives is very large (see combinatorial explosion). E.g., in chess, the number of available plays exceeds computational limits not just for humans (see bremermann’s limit). A decision maker who settles for a less ambitious result and obtains the optimum he can compute under given time or resource constraints is said to satisfice. (Krippendorff)”
pespmc1.vub.ac.be/ASC/SATISFICING.html
Hi Mark
Great post, however game semantics are entering your vocabulary:
“Optimization is the process of trying to find an assignment of values to the other variables (called parameters) that produces a maximum or minimum value of the target variable, called the optimum or optimal value.”
1 – John von Neumann is credited with developing the discipline of game theory with his minimax theorem of 1928 as well as contributing von Neumann algebras to physics.
http://en.wikipedia.org/wiki/John_von_Neumann
2 – Paul-André Melliès [Google can translate French into English] uses Conway semantics in linking game theory to traces used in physics.
http://www.pps.jussieu.fr/~mellies/
In the section ‘Recent and vintage talks’ are two that deal with game theory.
a – Functional boxings in string diagrams. Invited talk At CSL 2006; a discussion of game theory semantics beginning slide 64 of 88.
b – Asynchronous games: fully has supplements model of propositional linear logic. Wednesday talk At LiCS 2005; discusses strategies, lambda and pi calculus in slide 35 of 55.
3 – The ArXiv groups Computer Science and Game Theory as a subset of Computer Science.
http://arxiv.org/
Nice introduction to the topic. In macroeconomics, dynamic optimization is often used to derive intertemporal relationships for economic variable; interesting to see it implemented more theoretically than computationally.
Linear programming is an important part of OR, but it’s far from being the primary subject. Other subjects are prominent in OR are queueing theory and optimal control.
After linear programming, what is the simplest continuous type of optimization problems? Is it something like n-linear programming, where the objective function is n-linear in the variables x(n), or am I completely off track?
Alon Levy: “Quadratic programming (QP) is a special type of mathematical optimization problem…. Quadratic programming is a special case of the more general field of convex optimization…. For positive definite Q, the ellipsoid method solves the problem in polynomial time.[1] If, on the other hand, Q is negative definite, then the problem is NP-hard.[2] In fact, even if Q has only one negative eigenvalue, the problem is NP-hard.[3]”
equations and citations omitted, from
http://en.wikipedia.org/wiki/Quadratic_programming
“not like programming a computer; the term predates the invention of computers”
According to Wiki the term programming in optimization was first used by Danzig in WW II. Babbage was designing and building computers in the first half of the 19th century. Even if we consider the modern compzter Konrad Zuse built the Z1 (a purely mechanical computer)in 1936 and the Z3 an electrical computer in 1941 so I think it is OK to say that the statement quoted above is wrong.
There’s also a purely algebraic method for solving integer programming problems, using objects called Grobner bases. In principle this method can also solve any IP problem, but in practice it becomes an intractable approach even for a moderately large number of variables. I’ve actually got some (poorly-written) C++ code implementing Buchberger’s algorithm for computing Grobner bases, and using that data to solve IP problems.
Then there’s the ill-chosen term optimization in the context computer programs, done either manually or by a compiler. That of course has little to do with the more conventional kind of optimization. Optimizing compiler is quite an oxymoron.
MILP example.
I have $1.35
I line apples 60% more than oranges and plums 40% less than oranges. Apples cost 50c, Oranges cost 30c and plums 20c. I can only carry six fruit.
Which fruit should I buy to maximize my satisfaction given my monetary and carrying constraints?
this is an example only, I’ve not run it / made it up on the fly. Its worst noting little things like you can’t have negative fruit (negative plums to give you extra apples for example)
Negative plums? Maximize my satisfaction? Hmmmmmm.
===============================
This Is Just to Say
by William Carlos Williams
I have eaten
the plums
that were in
the icebox
and which
you were probably
saving
for breakfast
Forgive me
they were delicious
so sweet
and so cold
===============================
Whilst cold water may minimize plums, they cannot go negative. Filthy boy.
Rich – the negative plums that you mention do come up sometimes in similar economics problems when using (relatively) unconstrained optimization setups. They indicate that the solution to the problem lies on a boundary of the feasible set.
Ah, memories. I studied OR in grad school but, alas, have neglected the subject in the twenty+ years since. The Karmarkar algorithm was the new hot thing for solving LPs.
JVP, IIRC, QP is NPC if over Z.
-C
I think that the search space is better defined as the set of tentative solutions for the problem at hand, rather that a subset of some Euclidean space. The main reason is that you do not have topology in the search space until you define a way to connect solutions, and this is not an inherent property of the problem, but depends on the algorithm used to traverse the search space (for example, if solutions are n-bit strings, it is tempting to think the search space is a n-dimensional hypercube, but this does not make sense unless your search algorithm generate a new solution by a 1-bit flip of the current solution). This lead us to the concept of search landscape, of course.
Nice post. Keep on the excellent work!
Hello, i have found this optimization tree http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/index.html , but i need more branches in discrete optimization (there are no mentioned combinatorial optimization and etc.). Could you help me “drawing” the branches till scheduling?
Thank you a lot.
CH: IMHO;)
LBJ took the IRT
down to 4th street USA
When he got there, what did he see?
The youth of America on LSD.
LBJ, IRT
USA, LSD
LSD, LBJ
FBI, CIA
F-B-I-C-I-A
L-S-D;
Eh-eh-el…Be…Jay
[HAiR: The American Tribal Love-Rock Musical
lyrics by James Rado & Gerome Ragni
music by Galt MacDermot]