Optimization problems are made up of three basic ingredients:
- An objective function which we want to minimize or maximize. For instance, in a
manufacturing process, we might want to maximize the profit or minimize the
cost. In fitting experimental data to a user-defined model, we might minimize the
total deviation of observed data from predictions based on the model. In designing an
automobile panel, we might want to maximize the strength.
- A set of unknowns or variables which affect the value of the objective
function. In the manufacturing problem, the variables might include the amounts of
different resources used or the time spent on each activity. In
fitting-the-data problem, the unknowns are the parameters that define the model. In
the panel design problem, the variables used define the shape and dimensions of the
panel.
- A set of constraints that allow the unknowns to take on certain values but
exclude others. For the manufacturing problem, it does not make sense to spend a negative
amount of time on any activity, so we constrain all the "time" variables to be
non-negative. In the panel design problem, we would probably want to limit the weight of
the product and to constrain its shape.
The optimization problem is then:
Find values of the variables that minimize or maximize the objective function while
satisfying the constraints.
Are All these ingredients necessary?
Almost all optimization problems have a single objective function. (When they don't
they can often be reformulated so that they do!) The two interesting exceptions are:
- No objective function. In some cases (for example, design of integrated circuit
layouts), the goal is to find a set of variables that satisfies the constraints of the
model. The user does not particularly want to optimize anything so there is no reason to
define an objective function. This type of problems is usually called a feasibility
problem.
- Multiple objective functions. Often, the user would actually like to optimize a
number of different objectives at once. For instance, in the panel design problem, it
would be nice to minimize weight and maximize strength simultaneously.
Usually, the different objectives are not compatible; the variables that optimize one
objective may be far from optimal for the others. In practice, problems with multiple
objectives are reformulated as single-objective problems by either forming a weighted
combination of the different objectives or else replacing some of the objectives by
constraints. These approaches and others are described in our section on multi-objective optimization.
These are essential. If there are no variables, we cannot define the obective function
and the problem constraints.
Constraints are not essential. In fact, the field of unconstrained optimization is a large and
important one for which a lot of algorithms and software are available. It's been argued
that almost all problems really do have constraints. For example, any variable
denoting the "number of objects" in a system can only be useful if it is less
than the number of elementary particles in the known universe! In practice though, answers
that make good sense in terms of the underlying physical or economic problem can often be
obtained without putting constraints on the variables.
Up To:
NEOS Guide Optimization Tree.
Down To:
Continuous Optimization, in which all the variables are allowed to
take values from subintervals of the real line;
Discrete Optimization, in which you require some or all of the
variables to have integer values.
Multi-Objective Optimization, where you would like to simultaneously
optimize a number of different objectives.
[ OTC Home Page | NEOS
Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996