Nonlinear Programming

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 DoublePositiveInfinity. When a variable is not bounded from below, its lower bound is DoubleNegativeInfinity.

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 DoublePositiveInfinity. When a constraint is not bounded from below, its lower bound is DoubleNegativeInfinity.

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.

A nonlinear program is represented by the NonlinearProgram class. There are two ways to construct NonlinearProgram objects.

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 FuncT, TResult that maps a vector to a real number and represents the objective function. The second argument is a FuncT1, 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 MatrixT that contains the coefficients of the inequalities. It corresponds to the matrix A in the definition. The fourth argument is a VectorT containing the right-hand-sides of the inequalities. The code below creates the following a 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 b = Vector.Create(7.0, 4.0);
var nlp1 = new NonlinearProgram(f, g, A, b, 0);

Dim f = Function(x As Vector(Of Double))
            Return x(0) * x(0) + 4 * x(1) * x(1) - 32 * x(1) + 64
        End Function
Dim g = Function(x As Vector(Of Double), y As Vector(Of Double))
            y(0) = 2 * x(0)
            y(1) = 8 * x(1) - 32
            Return y
        End Function
Dim A = Matrix.Create({{1.0, 1.0}, {-1.0, 2.0}})
Dim b = Vector.Create(7.0, 4.0)
Dim nlp1 = New NonlinearProgram(f, g, A, b, 0)

let nlp1 = 
    let f (x : Vector<float>) = x.[0] ** 2.0 + 4.0 * x.[1] ** 2.0 - 32.0 * x.[1] + 64.0
    let g (x : Vector<float>) (y : Vector<float>) = 
        y.[0] <- 2.0 * x.[0]
        y.[1] <- 8.0 * x.[1] - 32.0
        y
    let A = Matrix.Create(array2D [[ 1.0; 1.0 ];[ -1.0; 2.0 ]])
    let b = Vector.Create(7.0, 4.0)
    NonlinearProgram(Func<_,_>(f), Func<_,_,_>(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.

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);

Dim f = Function(x As Vector(Of Double))
            Return x(0) * x(0) + 4 * x(1) * x(1) - 32 * x(1) + 64
        End Function
Dim g = Function(x As Vector(Of Double), y As Vector(Of Double))
            y(0) = 2 * x(0)
            y(1) = 8 * x(1) - 32
            Return y
        End Function
Dim A = Matrix.Create({{1.0, 1.0}, {-1.0, 2.0}})
Dim lc = Vector.CreateConstant(2, Double.NegativeInfinity)
Dim uc = Vector.Create(7.0, 4.0)
Dim lv = Vector.CreateConstant(2, 0.0)
Dim uv = Vector.CreateConstant(2, Double.PositiveInfinity)
Dim nlp2 = New NonlinearProgram(f, g, A, lc, uc, lv, uv)

let nlp2 = 
    let f (x : Vector<float>) = x.[0] ** 2.0 + 4.0 * x.[1] ** 2.0 - 32.0 * x.[1] + 64.0
    let g (x : Vector<float>) (y : Vector<float>) = 
        y.[0] <- 2.0 * x.[0]
        y.[1] <- 8.0 * x.[1] - 32.0
        y
    let A = Matrix.Create(array2D [[ 1.0; 1.0 ];[ -1.0; 2.0 ]])
    let lc = Vector.CreateConstant(2, -infinity)
    let uc = Vector.Create(7.0, 4.0)
    let lv = Vector.CreateConstant(2, 0.0)
    let uv = Vector.CreateConstant(2, +infinity)
    NonlinearProgram(Func<_,_>(f), Func<_,_,_>(g), A, lc, uc, lv, uv)

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 VectorT 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.

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);

Dim nlp3 = New NonlinearProgram()
nlp3.AddVariable("x1", 0.0, Double.PositiveInfinity)
nlp3.AddVariable("x2", 0.0, Double.PositiveInfinity)
Dim f = Function(x As Vector(Of Double))
            Return x(0) * x(0) + 4 * x(1) * x(1) - 32 * x(1) + 64
        End Function
nlp3.ObjectiveFunction = f
Dim g = Function(x As Vector(Of Double), y As Vector(Of Double))
            y(0) = 2 * x(0)
            y(1) = 8 * x(1) - 32
            Return y
        End Function
nlp3.ObjectiveGradient = g
nlp3.AddLinearConstraint("c1", {1.0, 1.0},
    ConstraintType.LessThanOrEqual, 7.0)
nlp3.AddLinearConstraint("c1", {-1.0, 2.0},
    ConstraintType.LessThanOrEqual, 4.0)

let nlp3 = new NonlinearProgram()
nlp3.AddVariable("x1", 0.0, +infinity) |> ignore
nlp3.AddVariable("x2", 0.0, +infinity) |> ignore
nlp3.ObjectiveFunction <-
    fun x -> x.[0] ** 2.0 + 4.0 * x.[1] ** 2.0 - 32.0 * x.[1] + 64.0
nlp3.ObjectiveGradient <-
    fun x y ->
        y.[0] <- 2.0 * x.[0]
        y.[1] <- 8.0 * x.[1] - 32.0
        y
nlp3.AddLinearConstraint("c1", [| 1.0; 1.0 |],
    ConstraintType.LessThanOrEqual, 7.0) |> ignore
nlp3.AddLinearConstraint("c1", [| -1.0; 2.0 |],
    ConstraintType.LessThanOrEqual, 4.0) |> ignore

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.

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 VectorT as its input. To define nonlinear constraints, call one of the overloads of AddSymbolicConstraint.

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 VectorT 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:

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);

Dim solution = nlp3.Solve()
Console.WriteLine(solution)

let solution = nlp3.Solve()
Console.WriteLine(solution)