Optimization

LCD
We analytically derived the optimal drive waveform for an electroluminescent display.

There are a wide variety of problems where it is easy to find solutions, but difficult to find solutions of high quality. The difficulty comes not from evaluating a particular solution, which is often fairly easy, but from the enormity of the space of possible solutions. Examples of these problems include echo cancellers in phone systems (where a solution is a filter and the goal is to minimize the echo), setting up delivery routes (where a solution is an ordering in which to visit the targets and the goal is to travel the shortest distance while doing it), and packing boxes onto a train (where a solution is an arrangement of boxes and the goal is to fit as many as possible).

An optimization problem always comes with a notion of what the goal is, but in order to actually optimize it, there needs to be a way to assign a single number (a cost) to any solution. The lower the cost is, the better the solution is (although sometimes the problem is defined so that the goal is to maximize the number instead of minimize it). This assignment from solution to cost is called the cost function. Sometimes it is obvious what the right cost function is (shortest time, most boxes in the train, etc), and sometimes the design of a good cost function is one of the major challenges in the problem. This can happen when there are several competing objectives or when an objective is fuzzy (e.g. make sure X doesn’t happen very often).

Some optimization problems have a large number of constraints or some very stringent contraints on the solution, so although it is easy to find an answer, it is difficult to find a valid solution. A common approach to these problems is to treat them like normal optimization problems, but assign a high cost to any answer that does not meet the constraints. This ensures that low cost solutions will meet the constraints and optimize the goal.

There are many techniques used for optimization. Some optimization problems have exact mathematical solutions, some can be exactly solved using a computer, and good solutions can be found for others using computer algorithms based on analogies to such varied things as bird flocking, metallurgy, and hill climbing. The techniques which work well for a particular problem are very dependent on the problem itself. However, the available techniques are powerful enough and cover a broad enough range of problems that very good solutions can be achieved for many optimization problems.

If you have an optimization problem of any sort, please contact us, and we will be glad to help you with it.