Nonlinear Programming | Extreme Optimization Numerical Libraries for .NET Professional |

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 |
lhs |

lhs | |

l |

The function f is a nonlinear function of the
x_{i}.
The matrix A contains the coefficients of the linear constraints.
The functions g_{j} represent nonlinear constraint functions.

Most nonlinear programs are relatively small, but some have hundreds or thousands of 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

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

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 Func

The third argument is a
Matrix

Minimize |
x |
---|---|

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

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

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.

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

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

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:

Copyright © 2004-20116,
Extreme Optimization. All rights reserved.

*Extreme Optimization,* *Complexity made simple*, *M#*, and *M
Sharp* are trademarks of ExoAnalytics Inc.

*Microsoft*, *Visual C#, Visual Basic, Visual Studio*, *Visual
Studio.NET*, and the *Optimized for Visual Studio* logo

are
registered trademarks of Microsoft Corporation.