Optimization

From NEOS

Optimization problems are made up of three basic ingredients:

• An objective function which we want to minimize or maximize. For i nstance, in a manufacturing process, we might want to maximize the profit or mi nimize 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 th e 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 va lues but exclude others. For the manufacturing problem, it does not make sense to sp end 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 constrainits shape.

The optimization problem is then:

Find values of the variables that minimize or maximize the objective function while satisfying the constraints.

Contents 1 Are All these ingredients necessary? 1.1 Objective Function 1.2 Variables 1.3 Constraints

Are All these ingredients necessary?

Objective Function

Almost all optimization problems have a single objective function. (When the y 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 integ rated circuit layouts), the goal is to find a set of variables that satisfies the constra ints 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 p roblem, it would be nice to minimize weight and maximize strength simult aneously. Usually, the different objectives are not compatible; the variables that op timize one objective may be far from optimal for the others. In practice, problems wit h multiple objectives are reformulated as single-objective problems by either forming a weighted combination of the different objectives or else replacing some of the objec tives 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 obectiv e 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 be en 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.