Nonlinear Programming
The goal of nonlinear programming is to optimize a possibly nonlinear function subject to linear or nonlinear constraints. In its most general form, a nonlinear program is an optimization problem
Minimize | f(x) |
|---|---|
subject to | lhsi ≤ Aix ≤ rhsi |
lhsj ≤ gj(x) ≤ rhsj | |
li ≤ xi ≤ ui |
The function f is a nonlinear function of the xi. The matrix A contains the coefficients of the linear constraints. The functions gj represent nonlinear constraint functions.
Most nonlinear programs are relatively small, but some have hundreds or thousands of variables and constraints.
Variables and Constraints
The DecisionVariable class is used to represent variables in a nonlinear program. Each variable has a unique name, available through the Name property. The variables are the unknowns in the optimization problem. The objective function is a nonlinear function of the variables.
The LowerBound and UpperBound properties define constraints on the values of a variable. Standard variables have no lower or upper bound. When a variable is not bounded from above, its upper bound is Double.PositiveInfinity. When a variable is not bounded from below, its lower bound is Double.NegativeInfinity.
The Constraint class is the abstract base class used to represent constraints in a nonlinear program. Every constraint must have a unique name, which can be accessed through the Name property. The LowerBound and UpperBound properties define these boundaries. When a constraint is not bounded from above, its upper bound is Double.PositiveInfinity. When a constraint is not bounded from below, its lower bound is Double.NegativeInfinity.
A linear constraint is a linear combination of variables that is required to lie between specified boundaries. Linear constraints are represented by the LinearConstraint class.
A nonlinear constraint is a (possibly) nonlinear function that is required to lie between specified boundaries. Nonlinear constraints are represented by the NonlinearConstraint class.
Variables and constraints can be accessed through the nonlinear program's Variables and Constraints collections. These collections are indexed by position and by name.
Defining nonlinear programs
A nonlinear program is represented by the NonlinearProgram class. There are two ways to construct NonlinearProgram objects.
Defining nonlinear programs using constructors
The quickest way to define a nonlinear program is by passing the vectors and matrices that appear in the definition above to a constructor. There are three constructors that can be used in this way.
The first constructor defines a nonlinear program with only linear constraints in standard form. This is a nonlinear program where variables are constrained to be positive, and all constraints are inequalities with an upper bound. It takes four arguments. The first argument is a Func<T, TResult> that maps a vector to a real number and represents the objective function. The second argument is a Func<T1, T2, TResult> that represents the gradient of the objective function. The first argument is a vector containing the x values. The second argument is a vector that is to hold the result.
The third argument is a Matrix<T> that contains the coefficients of the inequalities. It corresponds to the matrix A in the definition. The fourth argument is a Vector<T> containing the right-hand-sides of the inequalities. The code below creates the following a nonlinear program:
Minimize | x2 + 4y2 - 32y + 64 |
|---|---|
s.t. | x + y ≤ 7 |
-x + 2y ≤ 4 | |
x ≥ 0 | |
y ≥ 0 |
Func<Vector<double>, double> f = x =>
x[0] * x[0] + 4 * x[1] * x[1] - 32 * x[1] + 64;
Func<Vector<double>, Vector<double>, Vector<double>>
g = (x, y) =>
{
y[0] = 2 * x[0];
y[1] = 8 * x[1] - 32;
return y;
};
var A = Matrix.Create(new[,] { { 1.0, 1.0 }, { -1.0, 2.0 } });
var b = Vector.Create(7.0, 4.0);
var nlp1 = new NonlinearProgram(f, g, A, b, 0);The third constructor is the most flexible. It has seven parameters in all. The first two are once again the objective function and its gradient. The third argument is the coefficient matrix. The fourth and fifth parameters are vectors that contain the lower and upper bounds of the constraints. Each type of constraint can be expressed using a lower and upper bound, as shown in the table below.
Constraint | Lower bound | Upper bound |
|---|---|---|
c ≤ rhs | -infinity | rhs |
c ≥ rhs | rhs | +infinity |
c = rhs | rhs | rhs |
lhs ≤ c ≤ rhs | lhs | rhs |
The sixth and seventh parameters are vectors that contain the lower and upper bound for the variables. The different types of constraints on variables can be expressed the same way as for constraints. The following code sample builds the same nonlinear program:
Func<Vector<double>, double> f = x =>
x[0] * x[0] + 4 * x[1] * x[1] - 32 * x[1] + 64;
Func<Vector<double>, Vector<double>, Vector<double>>
g = (x, y) =>
{
y[0] = 2 * x[0];
y[1] = 8 * x[1] - 32;
return y;
};
var A = Matrix.Create(new[,] { { 1.0, 1.0 }, { -1.0, 2.0 } });
var lc = Vector.CreateConstant(2, double.NegativeInfinity);
var uc = Vector.Create(7.0, 4.0);
var lv = Vector.CreateConstant(2, 0.0);
var uv = Vector.CreateConstant(2, double.PositiveInfinity);
var nlp2 = new NonlinearProgram(f, g, A, lc, uc, lv, uv);Building nonlinear programs from scratch
The NonlinearProgram class also has two constructors that creates an empty nonlinear program. If you don't pass any arguments, the model is completely empty and you have to explicitly add variables to it. You can then call the nonlinear program's AddVariable methods to define variables. You may also pass in the number of variables, and a set of standard variables will be created automatically.
The AddVariable method has two overloads. The first has one parameter: the name of the variable. The second overload has two additional parameters that specify the lower and upper bound of the variable. If no values are specified, a lower bound of negative infinity and an upper bound of infinity are assumed.
The AddLinearConstraint method has four overloads. The first takes four parameters. The first is the name of the constraint. The second is a Vector<T> that contains the coefficients of the variables. The third parameter is a ConstraintType value that specifies the type of constraint. The possible values are listed in the table below. The last parameter is the right-hand side of the constraint.
Value | Description |
|---|---|
Equal | c = rhs |
GreaterThanOrEqual | c ≥ rhs |
LessThanOrEqual | c ≤ rhs |
The second overload also takes four parameters. The first two are the same as before. The third and fourth parameters are the lower and upper bound of the constraint. The different types of constraints can be specified according to the examples in Table 1.
The third and fourth overloads are similar to the first two. The only difference is that the coefficients are specified using a Double array instead of a vector.
The following example creates a nonlinear program that is identical to the last example:
var nlp3 = new NonlinearProgram();
nlp3.AddVariable("x1", 0.0, double.PositiveInfinity);
nlp3.AddVariable("x2", 0.0, double.PositiveInfinity);
nlp3.ObjectiveFunction =
x => x[0] * x[0] + 4 * x[1] * x[1] - 32 * x[1] + 64;
nlp3.ObjectiveGradient =
(x, y) =>
{
y[0] = 2 * x[0];
y[1] = 8 * x[1] - 32;
return y;
};
nlp3.AddLinearConstraint("c1", new[] { 1.0, 1.0 },
ConstraintType.LessThanOrEqual, 7.0);
nlp3.AddLinearConstraint("c1", new[] { -1.0, 2.0 },
ConstraintType.LessThanOrEqual, 4.0);Although not strictly necessary, it is advisable to create the variables first, followed by the constraints. If the vector containing the coefficients for a constraint is longer than the number of variables that have been defined, additional variables are added automatically. The kth variable is given the name x<k>.
Whenever possible, constraints on variables should be preferred over explicit nonlinear program constraints. The time to solve a nonlinear program depends most heavily on the number of constraints.
Using Automatic Differentiation
The gradient of the objective function and nonlinear constraints are needed during the solution process. When using .NET 4.0, it is possible to have these computed automatically using a symbolic representation of the objective function or constraint.
To do so, create the nonlinear program, and then set its SymbolicObjectiveFunction to a lambda expression that represents the objective function. The lambda expression should take a Vector<T> as its input. To define nonlinear constraints, call one of the overloads of AddSymbolicConstraint.
Solving nonlinear programs
Once a nonlinear program has been defined, solving it is very straightforward. The Solve method does all the work. A Sequential Quadratic Programming method is used. Depending on the size of the nonlinear program, this method may take a very long time to complete. Most problems with of the order of dozens of variables and constraints are typically solved in a fraction of a second. Very large problems, with many hundreds or thousands of variables and constraints, may take many minutes to solve.
The Solve method returns a Vector<T> containing the optimal solution. You should inspect the Status property to make sure an optimal solution was indeed found. This property is of type OptimizationModelStatus and can take on the following values:
Value | Description |
|---|---|
Unknown | Nothing is known about the solution. This is the status returned before the SolveModel method is called. |
Optimal | The nonlinear program was solved successfully and the solution that was returned is the optimal solution. |
Infeasible | The nonlinear program does not have a solution because some of the constraints conflict with each other. |
Unbounded | The nonlinear program does not have a finite solution. The cost function can be made arbitrarily small. |
Finally, the OptimalValue property returns the value of the cost function at the solution.
The code below solves the nonlinear program defined earlier:
var solution = nlp3.Solve();
Console.WriteLine(solution);