1.2 Classifications



next up previous
Next: 1.3 Optimality Conditions Up: 1 Introduction Previous: 1.1 Definitions

1.2 Classifications

 

There are many optimization algorithms available to the computational scientist. Many methods are appropriate only for certain types of problems. Thus, it is important to be able to recognize the characteristics of a problem in order to identify an appropriate solution technique. Within each class of problems there are different minimization methods, varying in computational requirements, convergence properties, and so on. A discussion on the relative strengths and weaknesses of available techniques within a given class of problems will be the focus of the following sections. Optimization problems are classified according to the mathematical characteristics of the objective function, the constraints, and the control variables.

Probably the most important characteristic is the nature of the objective function. A function is linear if the relationship between and the control variables is of the form

 

where is a constant-valued vector and is a constant; a function is quadratic if

 

where is a constant-valued matrix. Special methods can locate the optimal solution very efficiently for linear and quadratic functions, for example.

There is a special class of problems, examples of which are particularly common in the fields of operations research and engineering design, in which the task is to find the optimum permutation of some control variables. These are known as combinatorial optimization problems. The most famous example is the traveling salesman problem (TSP) in which the shortest cyclical itinerary visiting cities is sought. The solutions to such problems are usually represented as ordered lists of integers (indicating, for example in the TSP, the cities in the order they are to be visited), and they are, of course, constrained, since not all integer lists represent valid solutions. These and other classifications are summarized in Table 1. Table 2 lists application examples from the wide range of fields where optimization is employed and gives their classifications under this taxonomy.

Section 2 details methods appropriate to unconstrained continuous univariate/multivariate problems, and Section 3 mentions methods appropriate to constrained continuous multivariate problems. Section 4 considers methods appropriate to (mixed) integer multivariate problems, and Section 5 discusses what to do if none of these methods succeed. In general, the optimization of the complex functions that occur in many practical applications is difficult. However, with persistence and resourcefulness solutions can often be obtained.


Table 1 Optimization Problem Classifications. View Table


Table 2 Examples of Optimization Applications. View Table



next up previous
Next: 1.3 Optimality Conditions Up: 1 Introduction Previous: 1.1 Definitions



verena@csep1.phy.ornl.gov