The optimization algorithms we have discussed so far are all unconstrained
problems. The next three sections deal with constrained problems.
Many of the constrained problems are derived from theoretical models
where the solution is found by finding the configuration where a certain
quantity reaches a maximum or a minimum.
In order to facilitate working with such models, the
Extreme Optimization
Numerical Libraries for .NET
includes a framework for defining
such models that allows for easier bookkeeping and managing the results.
Components of an Optimization Model
All classes that implement optimization problems with constraints inherit from
an abstract base class, OptimizationModel.
An optimization model has three main components:
An objective function. This is the function that needs to be optimized.
A collection of decision variables. The solution to the optimization problem
is the set of values of the decision variables for which the objective function
reaches its optimal value.
A collection of constraints that restrict the values of the decision variables.
The OptimizationModel
class provides a common API for defining and accessing variables and constraints,
as well as other properties of each model.
We will now discuss each of these components in more detail.
Types of Optimization Models
Optimization problems can be classified in terms of the nature of the objective function
and the nature of the constraints. Special forms of the objective function and
the constraints give rise to specialized algorithms that are more efficient.
From this point of view, there are four types of optimization problems, of increasing complexity.
An Unconstrained optimization problem is an optimization problem
where the objective function can be of any kind (linear or nonlinear) and
there are no constraints. These types of problems are handled by the classes
discussed in the earlier sections.
A linear program is an optimization problem with an objective function that is
linear in the variables, and all constraints are also linear.
Linear programs are implemented by the
LinearProgram
class.
A quadratic program is an optimization problem with an objective function that is
quadratic in the variables (i.e. it may contain squares and cross products of the decision variables),
and all constraints are linear. A quadratic program with no squares or cross products in the objective
function is a linear program.
Quadratic programs are implemented by the
QuadraticProgram
class.
A nonlinear program is an optimization problem with an objective function that is
an arbitrary nonlinear function of the decision variables,
and the constraints can be linear or nonlinear.
Nonlinear programs are implemented by the
NonlinearProgram
class.
Finding the optimal values of the decision variables is the goal of
solving an optimization model. In the optimization framework,
variables are implemented by the
DecisionVariable
class.
Each variable has a
Name,
which may be generated automatically.
The LowerBound
and UpperBound properties
specify lower and upper bounds for the values the variable can take.
After the solution of the model has been computed, the
Value
property returns the value of the variable in the optimal solution.
DecisionVariable objects are created by calling one of the overloads of the optimization model's
AddVariable
method. In some cases, they may also be created automatically.
An optimization model's variables can be accessed through its
Variables
property. Individual variables can be accessed by name or by position.
The variable's Position
property returns the variable's index in the collection.
Specific models may have specialized versions of the decision variables. For example, both linear and quadratic programs
use variables of type LinearProgramVariable,
which inherits from DecisionVariable
and has an extra Cost
property that represents the coefficient of the variable in the linear portion of the objective function.
Constraints limit the possible values for the decision variables in an optimization model.
There are several types of constraints. The classes that implement them all inherit from the
Constraint
class.
Each constraint also has a
Name,
which may again be generated automatically.
The LowerBound
and UpperBound properties
specify lower and upper bounds for the value of the constraint.
After the solution of the model has been computed, the
Value
property returns the value of the constraint in the optimal solution.
There are two types of constraints: linear and nonlinear.
Linear constraints express that a linear combination of the decision variables must lie within a certain range.
They are implemented by the
LinearConstraint
class. The coefficients can be accessed through the
Gradient
property.
LinearConstraint
objects are created by calling one of the overloads of the optimization model's
AddLinearConstraint
method. In some cases, they may also be created automatically.
Nonlinear constraints express that the value of some arbitrary function of the decision variables must
lie within a certain range. They are implemented by the
NonlinearConstraint
class. The constraint function can be accessed through the
ConstraintFunction.
The gradient of this function, which is needed during the optimization process,
is the FastConstraintGradient
If it is not supplied, a numerical approximation is used.
NonlinearConstraint
objects are created by calling one of the overloads of the optimization model's
AddNonlinearConstraint
method.
An optimization model's constraints can be accessed through its
Constraints
property. Individual constraints can be accessed by name or by position.
The variable's Position
property returns the constraint's index in the collection.
Reference
Other Resources