--------------------------------------------------------------------------------
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?
Objective Function
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.
Variables
These are essential. If there are no variables, we cannot define the obective function and the problem constraints.
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